Đại học Lê Quý Đôn - 236 Hoàng Quốc Việt - Hà Nội

Chia sẻ kiến thức mọi mặt của các lớp cao học CNTT, Học viện Kỹ thuật Quân sự




Chào mừng đã đến với forum khmt.123.st
  • Bạn chưa đăng kí (hoặc chưa đăng nhập) nên quyền lợi của bạn sẽ bị hạn chế. Việc đăng kí làm thành viên hoàn toàn miễn phí, sau khi đăngkí bạn có thể post bài, tham gia thảo luận , nhìn thấy link ở những box hạn chế ... và rất nhiều quyền lợi khác. Thủ tục đăng kí rất nhanh chóng và đơn giản, hãy Đăng kí làm thành viên !
  • Nếu bạn quên mật khẩu, xin nhấn vào đây !
  • Nếu bạn gặp trục trặc trong vấn đề đăng kí hoặc không thể đăng nhập, hãy liên hệ với chúng tôi.




  • Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down  Thông điệp [Trang 1 trong tổng số 1 trang]

    mrP


    Thành viên cao cấp
    Thành viên cao cấp
    Bài tập Đồ thị - Tìm đường đi ngắn nhất (bài 3 - trang 124)
    Đồ thị G vô hướng, không trọng số được cho bởi danh sách cạnh:

    a, b

    d, k

    e, h

    b, c

    c, e

    e, d

    c, d

    b, f

    d, g

    a, f

    f, e

    g, k

    b, e

    e, g

    h, g

    c, k

    f, h

    h, k
    a) Lập danh sách kề của đồ thị, trong đó các đỉnh được sắp xếp theo thứ tự xuất hiện trong danh sách cạnh.
    b) Tìm đường đi ngắn nhất của (a,k).


    ================
    [You must be registered and logged in to see this image.]

    2 Đề các năm trước on Sat Jun 18, 2011 10:15 am

    Admin


    Quản trị viên
    Quản trị viên
    Câu 3. Đề năm 2009:
    a. Cho đồ thị G{V, E} vô hướng, liên thông, không trọng số, có n đỉnh 1-n cho bởi ma trận kề A[1..n, 1..n]. Viết thủ tục chi tiết tìm đường đi từ đỉnh u đến đỉnh v sao cho qua ít cạnh nhất.

    b. Đồ thị G có hướng, liên thông được cho bởi danh sách cạnh sau:
    Nháy vào phần hồng hồng này để ẩn hiện:

    TT
    Đầu
    Cuối
    Trọng số
    1
    a
    b
    5
    2
    f
    e
    2
    3
    g
    h
    2
    4
    m
    k
    2
    5
    k
    j
    1
    6
    h
    i
    1
    7
    i
    e
    2
    8
    e
    d
    1
    9
    b
    c
    2
    10
    a
    f
    6
    11
    f
    g
    6
    12
    g
    m
    6
    13
    e
    b
    3
    14
    g
    k
    5
    15
    h
    e
    4
    16
    k
    h
    4
    17
    d
    c
    6
    18
    i
    d
    6
    19
    j
    i
    6
    20
    a
    e
    1
    21
    m
    h
    6
    22
    f
    b
    5
    23
    e
    c
    2
    24
    d
    b
    5
    25
    h
    f
    5
    26
    h
    d
    5
    27
    e
    g
    3
    28
    j
    h
    2
    29
    k
    i
    5
    Tìm đường đi ngắn nhất từ đỉnh k đến đỉnh e theo thuật toán Dijkastra.

    Câu 3b. Đề năm 2007:
    b. Đồ thị G có hướng, liên thông được cho bởi danh sách cạnh sau:
    Nháy vào phần hồng hồng này để ẩn hiện:

    TT
    Đầu
    Cuối
    Trọng số
    1
    a
    b
    5
    2
    f
    e
    2
    3
    g
    h
    2
    4
    m
    k
    2
    5
    k
    j
    1
    6
    h
    i
    1
    7
    i
    e
    2
    8
    e
    d
    1
    9
    b
    c
    2
    10
    a
    f
    6
    11
    f
    g
    6
    12
    g
    m
    6
    13
    e
    b
    3
    14
    g
    k
    5
    15
    h
    e
    4
    16
    k
    h
    4
    17
    d
    c
    6
    18
    i
    d
    6
    19
    j
    i
    6
    20
    a
    e
    1
    21
    m
    h
    6
    22
    f
    b
    5
    23
    e
    c
    2
    24
    d
    b
    5
    25
    h
    f
    5
    26
    h
    d
    5
    27
    e
    g
    3
    28
    j
    h
    2
    29
    k
    i
    5
    Tìm đường đi ngắn nhất từ đỉnh m đến đỉnh c theo thuật toán Dijkastra.


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    Admin


    Quản trị viên
    Quản trị viên
    Giải thuật Dijkstra là một giải thuật để giải bài toán đường đi ngắn nhất nguồn đơn trên một đồ thị có trọng số cạnh mà tất cả các trọng số đều không âm. Nó xác định đường đi ngắn nhất giữa hai đỉnh cho trước, từ đỉnh a đến đỉnh b.
    Ở mỗi đỉnh v, giải thuật Dijkstra xác định 3 thông tin: Sv, λvαv.
    S
    v: mang giá trị boolean xác định trạng thái được chọn của đỉnh v.
    Ban đầu ta khởi tạo tất cả các đỉnh v chưa được chọn, nghĩa là: Sv = false, [You must be registered and logged in to see this image.]V.
    λv: là chiều dài đường đi mà ta tìm thấy cho đến thời điểm đang xét từ a đến v.
    Khởi tạo, λv = ∞ ,[You must be registered and logged in to see this image.]v Э V \{a}, λa = 0.
    p
    v: là đỉnh trước của đỉnh v trên đường đi ngắn nhất từ a đến b.
    Đường đi ngắn nhất từ a đến b có dạng {a,...,αv,v,...,b}.
    Khởi tạo, pv = null, [You must be registered and logged in to see this image.]v Э V.

    Sau đây là các bước của giải thuật Dijkstra:
    B1. Khởi tạo: Đặt Sv: = false [You must be registered and logged in to see this image.]v Э V; λv: = ∞ ,[You must be registered and logged in to see this image.]v Э V \ {a}, λa: = 0.
    B2. Chọn v Э V sao cho Sv = false và λv = min t / t Э V, St = false}
    Nếu λv = thì Kết thúc, không tồn tại đường đi từ a đến b.
    B3. Đánh dấu đỉnh v, Sv: = true.
    B4. Nếu v = b thì Kết thúc và λb là độ dài đường đi ngắn nhất từ a đến b.
    Ngược lại nếu v ≠ b sang B5.
    B5. Với mỗi đỉnh u kề với vSu = false, kiểm tra
    Nếu λu > λv f(v,u) thì λu: = λv + f(v,u)
    Ghi nhớ đỉnh v: αu: = v.
    Quay lại B2.



    Được sửa bởi Admin ngày Sat Aug 06, 2011 6:51 am; sửa lần 1.


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    4 Giải đề thi năm 2007 on Mon Jun 20, 2011 11:19 am

    Admin


    Quản trị viên
    Quản trị viên
    Trước khi các thành viên giải bài này bằng viết thủ tục, chúng ta sẽ nghiên cứu từng bước làm bằng tay để hiểu thuật toán. Thông thường, trong bài thi việc trình bày bằng tay cũng được số điểm không phải là quá ít (bao giờ cũng có 1 phần, dành cho việc làm bằng tay này). Chúng ta phải làm như thế nào.
    Làm mẫu cái đề thi năm 2007 theo cách làm mà sách hướng dẫn (trang 95, 96, sách ôn thi Cao học ngành CNTT, HV KTQS năm 2005).

    Đầu tiên là các ký hiệu:
    U: Đỉnh hiện tại. Việc xét khoảng cách từ một đỉnh gốc (trong đề này là m) đến một đỉnh đích (trong đề này là c), được chia ra các công đoạn (bước). Mỗi bước, ta có 1 đỉnh hiện tại làm căn cứ, phải chọn trong số các đỉnh kề của nó mà chưa có trong tập V*, đỉnh nào có trọng số ít nhất. Tính khoảng cách từ đỉnh gốc (là m) đến đỉnh này. Đưa đỉnh này vào tập V* để các lần tính sau không xét khoảng cách quay lại đỉnh này nữa.
    Giá trị từng ô của bảng này là khoảng cách từ đỉnh gốc m tới đỉnh cần xét.
    Nếu đề thi cho ở dạng danh sách kề, thì làm luôn bước này, nhưng nếu đề thi cho ở dạng đồ hình, ta phải lập danh sách kề trước.
    Làm bằng tay, đầu tiên ta viết vào bài làm:
    Tìm đường đi ngắn nhất P* (m, c)
    Sau đó kẻ bảng có n 4 cột (n là số đỉnh của đồ thị). Cột 1 ghi “Bước”, cột 2 ghi “U”, cột 3 bỏ trống cho đẹp, tránh lẫn dữ liệu. Từ cột 4 trở đi ghi lần lượt các đỉnh, nên ghi theo thứ tự đường đi (đừng có ghi lung tung kẻo khó khăn trong việc xét và nhầm lẫn), cột đầu tiên là cột gốc, cột sau cuối của các đỉnh là đích. Cột cuối cùng của bảng ghi “Tập V*
    Trong bài này ta có 12 đỉnh a, b, c, d, e, f, g, h, i, j, k, m nên phải kẻ tới 16 cột.
    Tại bước 0, xác định U chính là m nên ta điền vào bảng tại đỉnh m là 0. Các đỉnh còn lại điền thành ∞. Đưa m vào tập V*.


    Bước

    U


    m

    k

    j

    h

    i

    e

    c

    a

    b

    d

    f

    g

    Tập V*




    0










    Bước 1. Chọn đỉnh U chính là m, nên ta điền tại m khoảng cách là 0. Kiểm tra danh sách đỉnh kề của m xem bằng bao nhiêu thì điền vào. Nếu không phải danh sách kề của m, điền ∞. Do các khoảng cách từ m chỉ có tới k là nhỏ nhất (bằng 2) nên ta sẽ chọn k làm U ở bước kế tiếp. Đưa k bổ sung vào tập V*.

    Bước

    U


    m

    k

    j

    h

    i

    e

    c

    a

    b

    d

    f

    g

    Tập V*

    0



    0
























    1

    m


    0

    2



    6















    6

    m
    Bước 2. Chọn đỉnh U là k, lại kiểm trong danh sách đỉnh kề của k. Lấy trọng số của các đỉnh kề này, cộng với khoảng cách từ m tới k (chính là số 2), được bao nhiêu điền vào. Nếu không phải danh sách kề của k, điền ∞. Nếu đỉnh đã có trong tập V*, bỏ trống (Vì không ai điên mà tính quay lại các đỉnh đã đi qua làm gì). Do các khoảng cách từ m chỉ có tới j là nhỏ nhất (bằng 3) nên ta sẽ chọn j làm U ở bước kế tiếp. Đưa j bổ sung vào tập V*.

    Bước

    U


    m

    k

    j

    h

    i

    e

    c

    a

    b

    d

    f

    g

    Tập V*

    0



    0
























    1

    m


    0

    2



    6















    6

    m

    2

    k



    2

    3

    6

    7













    7

    m, k
    Bước 3, 4, 5... Tương tự lập luận như bước 2.
    Bước 6. Do đỉnh e là đỉnh kề với c nên kết thúc luôn.

    Bước

    U


    m

    k

    j

    h

    i

    e

    c

    a

    b

    d

    f

    g

    Tập V*

    0



    0
























    1

    m


    0

    2



    6















    6

    m

    2

    k



    2

    3

    6

    7













    7

    m, k

    3

    j




    3

    5

    9















    m, k, j

    4

    h





    5

    6

    9









    10

    7

    m, k, j, h

    5

    i






    6

    8







    12





    m, k, j, h, i

    6

    e







    8

    10

    9

    11

    9

    10



    m, k, j, h, i, e

    7

    c








    10






    m, k, j, h, i, e, c

    Vậy đường đi ngắn nhất từ m đến c theo thuật toán Dijkastra là (m, k, j, h, i, e, c)


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    5 Giải đề thi năm 2007 on Mon Jun 20, 2011 1:41 pm

    mrP


    Thành viên cao cấp
    Thành viên cao cấp
    @ đ/c Admin: v/v Giải đề thi năm 2007.
    - Cách giải còn thiếu bước duyệt ngược lại để kết luận đó là đường đi ngắn nhất.
    - Chẳng hạn có ví dụ: Cho danh sách cạnh (a, b, 5); (a, c, 7); (b, c, 3); (c, d, 1). Tìm đường đi ngắn nhất từ a-->d.
    - Theo các bước: thứ tự các đỉnh được lấy vào S là: a, b, c, d. Nhưng đường đi ngắn là a, c, d.


    ================
    [You must be registered and logged in to see this image.]

    hungbeo_fm2008


    Chuyên viên
    Chuyên viên
    Bước lập bảng là để tìm độ dài đường đi ngắn nhất và thứ tự các nút nó sẽ đi qua. Nhưng để đầy đủ thì ta phải thử lại.
    Trong sgk viết thiếu đoạn thủ tục này.
    @All: các bác thử đọc cái ví dụ trong SGK xem thế nào, chứ bản thân em thấy danh sách kề trước của nó bị sai (nó lấy danh sách kề trước = danh sách kề sau).
    Ví dụ: đối với đỉnh a, danh sách kề sau của a là hai đỉnh {b,c}, còn nó làm gì có danh sách kề trước, thế mà sgk lại lấy hai đỉnh b,c
    → dẫn đến nó tìm sai đường đi ngắn nhất và độ dài đường đi ngắn nhất.


    ================
    Phong độ là nhất thời, đẳng cấp mới là mãi mãi. [You must be registered and logged in to see this image.]

    Admin


    Quản trị viên
    Quản trị viên
    Đây là đường đi ngắn nhất theo thuật toán Dijkastra, chứ không phải đường đi ngắn nhất trên thực tế.

    Xét đồ thị sau:
    [You must be registered and logged in to see this image.]
    Nhìn cái đồ thị ta nhận thấy đường đi ngắn nhất từ A đến D sẽ là đường A → B → C → D sẽ có tổng trọng số là 3 + 1 + 3 = 7.
    Nhưng theo thuật toán Dijkastra thì nó cứ chọn đoạn có trọng số bé nhất trước. Tức là nó sẽ phải đi A → H → I → J → K → L → D.
    Nếu xét đồ thị trên nó lại là đường đi dài nhất, có tổng trọng số bằng 26, nó dài hơn cả A → E → F → G → D (có tổng trọng số = 22).

    Cho nên thuật toán là thuật toán, thực tế là thực tế.


    Bác Phương nói đúng đấy: A Admin hiểu sai thuật toán. Sonld


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    mrP


    Thành viên cao cấp
    Thành viên cao cấp
    @ Admin:

    - Thứ nhất: Hiểu sai thuật toán.
    - Thứ hai: Thuật toán phải đúng thực tế.

    + Lý do sai thứ nhất: bỏ qua câu lệnh if L(x)> L(a) + f(a, x)... và không xét ngược để tìm ra đường đi ngắn nhất. Trong thuật toán đỉnh x nào có f(x) nhỏ thì được xét trước, chứ không bắt buộc đỉnh tiếp theo phải nằm trên một nhánh của đỉnh trước. Khi kiểm tra tất cả đỉnh kề x, nếu trọng số mới của nó nhỏ hơn trọng số cũ (khi chưa xét x) thì đổi lại trọng số, còn không thì giữ nguyên.

    + Lý do thứ hai: Không biết.


    Về thuật toán dựa trên bài toán đ/c vừa nêu ra, tôi tóm lược lời giải thế này:

    B1: chọn A
              f(H)= 1, f(E)= 2, f(B)= 3

    B2: chọn H, vì f(H)= 1 < f(E)= 2 < f(B)= 3
              f(I) = 2

    B3: chọn I (hoặc E cũng được) vì f(E) = f(I) = 2 < f(B)= 3
              f(J)= 10

    B4: chọn E (nếu B3 chọn I), vì f(E) = f(I) = 2 < f(B)= 3 < f(J)= 10
              f(F)= 11

    B5: chọn B, vì f(B)= 3 < f(J)= 10 < f(B)= 3 < f(F)= 11
              f(C)= 4

    B6: chọn C, vì f(C)= 4 < f(J)= 10 < f(F)= 11
              f(D)= 7

    B7: chọn D
              f(G)= 9, f(L)= 8

    Thoát khỏi vòng lặp, quay ngược lại để tìm đường đi ngắn nhất.

    gán x1= D

    B1: x2= C, vì C kề D và f(C)+ f(C,D)= 4 + 3 = 7 = f(D)

    B2: x3= B, vì B kề C và f(B)+ f(B,C)= 3 + 1 = 4 = f(C)

    B3: x4= A, vì A kề B và f(A)+ f(A,B)= 0 + 3 = 3 = f(B)

    Vòng lặp dừng.

    Output x4, x3, x2, x1.


    ================
    [You must be registered and logged in to see this image.]

    Admin


    Quản trị viên
    Quản trị viên
    Nghiên cứu thuật toán Dijkstra trên lớp để có thể viết cho mọi cấu trúc dữ liệu.
    Phần không có trọng số.
    Hình dung về số mức. Điểm xuất phát mức 0. Các đỉnh kề với mức 0 là mức 1. Các đỉnh kề với các đỉnh mức 1 (mà các đỉnh kề này chưa có dấu mức) sẽ là mức 2. Cứ như thế loang dần ra. Mức nào chứa được đỉnh đích, thì dừng lại. Và đoạn đường đi sẽ có độ dài chính là mức. Đỉnh u là đỉnh xuất phát, đỉnh v là đỉnh đích. Việc chúng ta là tìm khoảng cách u đến v.

    A. Khởi tạo:
    for all x Э V λ(x): = + ∞;// Đưa tất cả khoảng cách các đỉnh với đỉnh xuất phát là vô cùng.
    m: = 0; //Đặt mức để cho dễ trình bày
    λ (u): = m;// Đặt nhãn của điểm u chính là m.
    A(m): = {u}//Khởi tạo tập A chứa một phần tử u.

    B. Chọn đỉnh
    While λ (v) = + ∞
              1) A(m+1) := Ø;
              2) for each a Э A(m)
                        for each x Э V+ (a) //x thuộc tập đỉnh kề
                                  if λ (x) = + ∞
                                            λ (x) := m + 1;
                                            A(m+1): = A(m+1) U {x} //Thêm vào A(m+1) đỉnh {x}
              3) m:= m+1;

    C. Xác định đường đi
    Um: = v
    for j := m - 1 downto 1
              Uj Э V-(Uj+1) ∩ Aj;
    U0 : =U;

    D. Output (U0, ..., Um), λ (v)


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    Admin


    Quản trị viên
    Quản trị viên
    Phần có trọng số.
    Hình dung về số mức. Sử dụng một tập S để lưu các đỉnh có dấu hiệu tốt.
    A. Khởi tạo:
    for all x Э V λ(x): = + ∞;// Đưa tất cả khoảng cách các đỉnh với đỉnh xuất phát là vô cùng.
    λ (u): = 0;// Đặt nhãn của điểm u chính là m.
    S:= Ø //Khởi tạo tập S ban đầu rỗng, cho dễ viết ở phần sau.

    B. Chọn đỉnh
    While v ! Э S
              1) Tìm a sao cho λ (a)= min { λ (x) : x Э V\S} // x ngoài S
                        S := S U {a} //đưa {a} vào tập S
              2) for each x Э V+ (a) //xét tất cả các đỉnh kề sau của đỉnh này
                        if λ (a) + f(a, x) < λ (x)
                                  λ (x) := λ (a) + f(a, x);

    C. Xác định đường đi
    Uo: = v; j := 0;
    while Uj ≠ u
              Tìm x Э V-(Uj); sao cho // Kề với trước Uj
              λ (x) + f(x, Uj) = λ (Uj)
              Uj+1 : = x; j := J+1;

    D. Output
    (Uj, Uj-1..., Uo), λ (v)


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    Admin


    Quản trị viên
    Quản trị viên
    Một số cách viết hàm để sử dụng:
    Giả sử đồ thị có hướng, cho bởi danh sách kề từ 1 đến n. Có m cạnh cho bởi danh sách cạnh
    D: array (1..m) of Cạnh;
    Cạnh = Record
              d, c: Tên đỉnh;
              t: giá trị trọng số;
              End.

    1. Hàm Kề (u, v: Tên đỉnh), cho giá trị TRUE nếu 2 đỉnh kề nhau hay (u, v) Э E
    Func. Kề (u, v: tên đỉnh) Boolean;
    i: = 1
    WHILE (i ≤ m) AND (D (i).đ ≠ u OR D(i).c ≠ v) DO i++;
    Kề := (i ≤ m)

    2. Hàm f(u, v: Tên đỉnh): Giá trị là trọng số của 2 đỉnh, hoặc ∞ nếu 2 đỉnh không kề nhau.
    Func. f (u, v: tên đỉnh): Giá trị;
    i: = 1
    WHILE (i ≤ m) AND (D (i).đ ≠ u OR D(i).c ≠ v) DO i++;
    IF i ≤ m THEN f := D(i).t
              ELSE f:= ∞;

    3. Viết một thủ tục tìm đường đi ngắn nhất tới 2 đỉnh u, v cho trước

    Proc. ShortPath (u, v: tên đỉnh);
    1. FOR x := 1 TO n DO λ(x) := ∞; λ(u) := 0; s(x): = 0;
    stop := false;
    2. WHILE s(v) := 0 & !Stop DO
              a) a:= v;
              FOR x := 1 TO n DO
                        IF (s(a) := 0) & (λ(a) > λ(x)) THEN a := x;
              s(a) := 1;
              IF λ(a) := ∞ THEN stop := TRUE;
              b) FOR x := 1 TO n DO
                        IF Kề(a, x) & (λ(x) > λ (a)+ f(a, x)) THEN λ(x) := λ(a) + f(a, x)
    3. IF stop := false THEN
    k := 1; α (k) := v;
    WHILE α(k) ≠ u DO
              x := 1;
              WHILE !Kề( x, α(k)) OR (λ(x) ≠ (λ(α(k) + f(α(k), x)) DO x++;
              k++; α(k) := x;
    4. IF !Stop THEN Output (λ(v) , α(k), α(k-1),..., α(1);
              ELSE Output("Hai đỉnh không thuộc vùng liên thông, không có đường đi từ u đến v")


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    Admin


    Quản trị viên
    Quản trị viên
    Một dạng dữ liệu khác là danh sách liên kết.
    Cho đồ thị G liên thông có n đỉnh đánh số từ 1 đến n cho bởi danh sách kề.
    V: array (1..n) of DanhSach
    DanhSach = ^Đỉnh;
    Đỉnh = record
              t: tên đỉnh
              Next: DanhSach;
              End

    Viết thủ tục tìm đường đi ngắn nhất nối u, v


    PROC DuongDiNganNhat (u, v: Tên đỉnh)
    1. FOR i := 1 to n DO λ(i) := ∞;
    λ(u) := 0; kc := 0;
    2. WHILE λ(v) ≠ ∞ DO
              a) FOR j := 1 TO n DO
                        IF λ(j) = kc THEN
                                  p := V(j);
                                  WHILE p ≠ Nil DO
                                            IF λ(p^.t) = ∞ THEN λ(p^.t) := kc + 1;
              b) kc := kc +1;
    3. α(kc) : = v
    FOR i := kc - 1 DOWNTO 1 DO
              P := V(α(i + 1))
              WHILE λ(p^.t) ≠ i THEN p := p^.Next
              α(i) := p^.t
    α(0) := u;
    4. Output (kc, α(0), α(1)... α(kc))


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    vt17936


    Thành viên chưa phát huy chia sẻ
    Thành viên chưa  phát huy chia sẻ
    Anh/chị giải thích kỹ đoạn này cho e hiểu rõ hơn,cố gắng để hiểu mà mãi k hiểu.
    3. IF stop := false THEN
    k := 1; α (k) := v;
    WHILE α(k) ≠ u DO
    x := 1;
    WHILE !Kề( x, α(k)) OR (λ(x) ≠ (λ(α(k) + f(α(k), x)) DO x++;
    k++; α(k) := x;

    Admin: Đoạn này là đoạn kiểm tra xem đúng đỉnh kề có nhãn cần chọn không, đúng rồi thì đưa vào danh sách đỉnh thôi.

    markq9x


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    cho mình hỏi toán tử stop ở đây là gì vậy?
    Code:

    Proc. ShortPath (u, v: tên đỉnh);
    1. FOR x := 1 TO n DO λ(x) := ∞; λ(u) := 0; s(x): = 0;
    stop := false;
    2. WHILE s(v) := 0 & !Stop DO
              a) a:= v;
              FOR x := 1 TO n DO
                        IF (s(a) := 0) & (λ(a) > λ(x)) THEN a := x;
              s(a) := 1;
              IF λ(a) := ∞ THEN stop := TRUE;
              b) FOR x := 1 TO n DO
                        IF Kề(a, x) & (λ(x) > λ (a)+ f(a, x)) THEN λ(x) := λ(a) + f(a, x)
    3. IF stop := false THEN
    k := 1; α (k) := v;
    WHILE α(k) ≠ u DO
              x := 1;
              WHILE !Kề( x, α(k)) OR (λ(x) ≠ (λ(α(k) + f(α(k), x)) DO x++;
              k++; α(k) := x;
    4. IF !Stop THEN Output (λ(v) , α(k), α(k-1),..., α(1);
              ELSE Output("Hai đỉnh không thuộc vùng liên thông, không có đường đi từ u đến v")

    markq9x


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    bài này khó hiểu quá, có bài nào bằng C thì cho mình với!

    trangmeomeo


    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    Admin đã viết:
    Bước 1. Chọn đỉnh U chính là m, nên ta điền tại m khoảng cách là 0. Kiểm tra danh sách đỉnh kề của m xem bằng bao nhiêu thì điền vào. Nếu không phải danh sách kề của m, điền ∞. Do các khoảng cách từ m chỉ có tới k là nhỏ nhất (bằng 2) nên ta sẽ chọn k làm U ở bước kế tiếp. Đưa k bổ sung vào tập V*.

    Bước

    U


    m

    k

    j

    h

    i

    e

    c

    a

    b

    d

    f

    g

    Tập V*

    0



    0
























    1

    m


    0

    2



    6















    6

    m
    Admin cho em hỏi chút. Theo đầu bài là cho Đồ thị G có hướng,nhưng trong các bước xét em thấy anh admin xét đồ thị vô hướng thì phải.
    Như trong bước 1 này anh xét m kề với đỉnh k, h, g. Nhưng đầu bài đưa ra thì m → k, m → h, còn m !→ g.
    Mọi người xem lại giúp em với. Thanks.


    ================
    Gà Công Nghiệp..................

    Sponsored content


    Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang  Thông điệp [Trang 1 trong tổng số 1 trang]

    Permissions in this forum:
    Bạn không có quyền trả lời bài viết

     

    Ghi rõ nguồn khi copy các bài viết từ Website này.
    Bản quyền thuộc Khoa học Máy tính. Số lượt truy cập tính đến hiện tại:Website counter
    Modified skin by Nguyễn Anh Cường. Developed by Members of http://khmt.123.st

    Free forum | © PunBB | Free forum support | Liên hệ | Report an abuse | Create a blog