Đạ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]

    Admin


    Quản trị viên
    Quản trị viên
    Bài toán tìm cây khung bé nhất của đồ thị
    Cho đồ thị G = (V, E) vô hướng, có trọng số f. T là cây khung của đồ thị G. Tổng các trọng số trên các cạnh của T ký hiệu:
    [You must be registered and logged in to see this image.]
    ح(G) là tập các cây khung cua đồ thị G. Tìm T* Э ح(G) sao cho [You must be registered and logged in to see this image.] đạt nhỏ nhất.

    Thuật toán Prim:
    1. T = {e: f(e) = min f(e) | e Э E}
    2. while số_cạnh (T) < n-1 do
                        a. Tìm e Э E sao cho:
                                            a1. e liên thuộc với 1 đỉnh trong T
                                            a2. Thêm e vào T không tạo thành chu trình
                                            a3. f(e) min | e thoả mãn a1, a2.
                        b. Thêm e vào T

    Thuật toán Kruskal
    1. T : = Ø
    2. while số_cạnh (T) < n-1 do
                        a. Tìm e Э E sao cho:
                                            a1. Thêm e vào T không tạo thành chu trình
                                            a2. f(e) min | e thoả mãn a1.
                        b. Thêm e vào T



    Được sửa bởi Admin ngày Thu Jun 16, 2011 9:04 pm; 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

    2 Cây khung nhỏ nhất của đồ thị on Tue Jun 14, 2011 7:25 pm

    hienha


    Chuyên viên
    Chuyên viên
    Xây dựng cây khung bé nhất của đồ thị liên thông được cho bởi danh sách cạnh theo thuật toán PRIM:
    1. Sắp xếp các danh sách cạnh sao cho:
    ds[1].t ≤ ds[2].t ≤ ... ≤ ds[m].t
    2. FOR i := 1 TO n DO
    VT[i] := 0;
    3. k := 1; E'[k] = ds[1]; m = m + ds[1].t; VT[ds[1].d] := 1; VT[ds[1].c] := 1;
    4. WHILE (k< n-1) DO
              stop := false;
              j := 2; (sau mỗi lần thêm được 1 cạnh lại phải xét lại từ pt thứ 2)
              WHILE (!stop) DO
                        IF (VT[ds[j].d] != VT[ds[j].c]) THEN
                                  k++;
                                  E'[k] := ds[j]; m = m + ds[j].t;
                                  VT[ds[j].d] := 1; VT[ds[j].c] := 1;
                                  stop := true;
                        ELSE
                                  j++;
    5. OUTPUT E', m

    Vì khi hiển thị không thấy căn lề của từng đoạn mã nên em NÊN DÙNG CHỮ C A C H để TẠO KHOẢNG TRỐNG biết đoạn nào thuộc vòng lặp nào.



    Được sửa bởi hienha ngày Wed Jun 15, 2011 4:56 pm; sửa lần 2.


    ================

    mrP


    Thành viên cao cấp
    Thành viên cao cấp
    - Ở 3 chưa gán T[ds[1].d]:=1; VT[ds[1].c]:=1; nhé.
    - Ở 4 gán j:=2; trước vòng while (!stop)

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


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

    Admin


    Quản trị viên
    Quản trị viên
    Chương trình giả mã của Hà Thị có thể trình bày lại theo đúng dạng mẫu của thầy, như sau:
    Nháy vào khung màu hồng này để hiện, ẩn:

    1. Sắp xếp các danh sách cạnh sao cho:
    ds[1].t ≤ ds[2].t ≤...≤ ds[m].t
    2. FOR i := 1 TO n DO
    VT[i]:=0;




    3. k := 1;
    T[ds[1].d] := 1;
    E'[k] = ds[1];
    T[ds[1].c]:=1;
    m = m + ds[1].t;


    4. WHILE (k < n - 1) DO





    j: = 2;
    stop := false;






    WHILE (!stop) DO






    j: = 2;
    IF (VT[ds[j].d] != VT[ds[j].c]]) THEN




    k++;






    E'[k] := ds[j];






    m = m + ds[j].t;






    VT[ds[j].d] := 1;






    VT[ds[j].c] := 1;






    stop := true;




    ELSE
    j++;


    5. OUTPUT E', m






    Để làm rõ từng dòng lệnh, ta sẽ xem xét căn cứ vào thực tế nha.
    1. Đầu tiên đề bài cho cấu trúc dữ liệu được lưu trữ dưới dạng record có tên là DS. Nó có 3 trường gồm d: đỉnh đầu, c: đỉnh cuối và t là trọng số. Khi sắp xếp ds[1].t <= ds[2].t<=...<= ds[m].t có nghĩa là sắp trọng số tăng dần. Quá dễ hiểu, thôi đoạn này bỏ qua nha.
    2. Tiếp theo đoạn: for i:=1 to n rồi đặt VT[i]:=0; là Hà Thị đã reset đặt lại tất cả cái mảng theo dõi trạng thái của các đỉnh về 0. Uh, lẽ ra đặt tên dễ gợi nhớ đi 1 chút thì khó quên hơn, ví dụ như TD là theo dõi chẳng hạn. Thôi, không sao, VT thì VT. Nhớ VT là theo dõi đó nhen, i là đỉnh thứ mấy đó.
    3. Dòng này đặt k = 1 để đánh dấu rằng, bắt đầu lấy cạnh đầu tiên, k này vừa là số thứ tự, vừa là cạnh thứ mấy đó nhen.
    Đặt E'[k]=ds[1]; nghĩa là cạnh thứ k (vừa gán = 1 ở trên) bằng cạnh 1 trong danh sách ds. Đã đặt cả cạnh là 2 đầu mút rồi, Mrp nói cần đánh dấu 2 đỉnh này, nên cần thêm dòng đánh dấu 1 đầu này, T[ds[1].d]:=1; VT[ds[1].c]:=1;. quên đánh dấu 2 đỉnh này sẽ bị biến thành chu trình phần sau, OK.
    Đặt m= m+ ds[1].t; là nàng đo độ dài của cạnh thứ nhất (lấy trọng số ds[1].t), đưa vào tổng độ dài của cây khung. Việc đặt tên biến cũng không được rõ ràng tường minh cho lắm, ví dụ đặt là daick (dài cây khung chẳng hạn) thì có lẽ dễ theo dõi hơn. Nhưng thôi, bỏ qua tiểu tiết, nhớ là m là đo độ dài cây khung đó nhen.
    4. while (k< n-1) do: Câu này quá dễ, chừng nào cây khung chưa đủ số cạnh = n-1 thì quyết kiếm cho đủ ! Tạm gọi vòng lặp này là vòng kiếm đủ số cạnh cho cây khung.
    j:=2 Xét từ cặp thứ 2: Rất khôn. Xem bình luận dưới.
    stop:= false; khởi tạo biến cờ, không có thôi gì cả, bao giờ xong, báo thôi thì mới thôi. Biến này dùng cho vòng for ở trong.
    while (!stop) do: Chừng nào chưa thôi thì cứ làm! Tạm gọi vòng này là vòng kiếm cho được 1 cạnh mới thôi.
    if (VT[ds[j].d] != VT[ds[j].c]]) then Nếu đỉnh đầu và đỉnh cuối của phần tử thứ j trong danh sách, đánh dấu khác nhau thì:
    k++ đếm luôn: thêm 1 đỉnh
    E'[k]:= ds[j]; Cạnh thứ k bằng phần tử thứ j trong (danh sách cạnh đã sắp xếp ở đầu rồi)
    m = m + ds[j].t; Đo luôn trọng số, đưa vào độ dài cây khung.
    VT[ds[j].d]:=1; VT[ds[j].c]] = 1: Đánh dấu luôn 2 đỉnh này là 1.
    Chả sao cả, vì chẳng biết được đỉnh nào chưa đánh dấu, nếu nó đã được đánh dấu là 1 ở vòng trước rồi thì đánh lại chẳng sao, đỡ phải kiểm tra. Lưu ý là bên trên đã If (VT[ds[j].d] != VT[ds[j].c]]) có nghĩa là kiểm tra một đỉnh đã có dấu (1) và một đỉnh chưa có dấu (0) mới làm các bước trên. Ở đây không phải xét lung tung mà bản chất là xét phần tử thứ j của danh sách cạnh đã sắp xếp, xét 2 đỉnh đầu cuối của nó.
    stop = true: Đặt biến cờ cho vòng lặp này thôi. Nghĩa là đặt được thì thôi luôn, còn chưa đặt được thì xét cặp đỉnh khác.
    else j++ Còn trường hợp khác, tăng j lên để xét phần tử kế tiếp trong danh sách cạnh đã sắp xếp.
    Thoát khỏi vòng lặp kiếm 1 cạnh, quay lại đầu vòng lặp kiếm đủ số cạnh, thấy ngay j: = 2, nhiều người bỏ quên cái câu j = 2 là chết oan ngay, vì phải xét lại từ đầu danh sách, để tránh bỏ sót. Khi làm bằng tay, ta để ý là có chỗ nhảy cách xuống phần kế danh sách, mà bên trên có phần tử lúc ý chưa thoả mãn, nhưng bây giờ nó mới thoả mãn thì ta lại lấy vào. Nghĩa là luôn luôn xét từ đầu danh sách, mỗi khi lấy xong một cạnh.
    5. Xong thì đưa nó ra bằng output, đưa ra các cạnh của cây khung E' và độ dài của cả cây khung m.
    Khách viếng thăm xem lại bình luận xem có cần thiết phải bổ sung không nha!
    [You must be registered and logged in to see this link.]



    Được sửa bởi Admin ngày Thu Jul 21, 2011 5:24 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

    hienha


    Chuyên viên
    Chuyên viên
    @Mr Phương: uh, em viết hơi ẩu (đang đói mừ :)). Em sửa lại rùi đó


    ================

    Tongmanhcuong


    Thành viên cao cấp
    Thành viên cao cấp
    Ý kiến của tôi:
    - Các đồng chí nên viết giả mã có trường hợp đồ thị không liên thông. Vì trường hợp liên thông chỉ là một trường hợp
    - Giả mã nên tinh xảo hơn (tôi thấy giả mã em hiền viết chưa khôn, sorry nha anh không biết nên dùng từ nào cho hợp). Tôi mong em Hiền và Hồng và mọi người cố viết lại đi. Tôi có đòi hỏi cao quá không nhỉ. Nếu không viết được anh sẽ gợi ý.





    @Mr. Tống:
    - Bài toán được xây dựng trên cơ sở đồ thị liên thông.
    - Nếu Mr. Tống viết được, sao không share cho mọi người??


    ================

    haihonglyk6


    Chuyên viên
    Chuyên viên
    ở phần 4 của Hiền nên sửa lại thế này hay hơn
    4. while (k< n-1)
    {
    j:=2;(sau mỗi lần thêm được 1 cạnh lại phải xét lại từ pt thứ 2)
    while (VT[ds[j].d] = VT[ds[j].c]) j=j+1
    k++;
    E'[k]:= ds[j]; m = m + ds[j].t;
    VT[ds[j].d]:=1; VT[ds[j].c]:=1;
    }


    ================
    Chúc Khách viếng thăm một ngày vui vẻ!

    Admin


    Quản trị viên
    Quản trị viên
    Bình luận một chút
    Tại sao PTHH nói ở phần 4 của Hiền nên sửa lại thế này hay hơn
    Nháy vào chỗ hồng hồng này để ẩn hiện: :

    4. WHILE (k < n -1) DO
              j := 2;(sau mỗi lần thêm được 1 cạnh lại phải xét lại từ pt thứ 2)
              WHILE (VT[ds[j].d] = VT[ds[j].c]) DO j = j +1
              k++;
              E'[k] := ds[j];
              m = m + ds[j].t;
              VT[ds[j].d] := 1;
              VT[ds[j].c] := 1;
    Thực ra bản chất vẫn là dùng 2 vòng lặp. Một vòng ngoài để kiếm đủ số cạnh, một vòng trong để kiếm bằng được một cạnh. Nhưng ở đây được đặt vấn đề khác hoàn toàn.
    Thứ nhất: Đặt j := 2 để khẳng định rằng, mỗi lần tìm một cạnh thì phải tìm từ đầu danh sách (Bởi ds[1] đã lấy làm cạnh đầu tiên rồi, nêu bỏ nó ra. Danh sách còn lại đối với tất cả các cạnh khác đều chỉ dược lấy từ phần tử thứ 2. OK, cái này nói rõ trong bài bình luận của HTH rồi.
    Thứ hai. PTHH dùng vòng lặp WHILE (VT[ds[j].d] = VT[ds[j].c]) DO j = j + 1 là cũng khôn.
    Nghĩa là phần tử hiện tại nào mà 2 đầu đỉnh có giá trị đánh dấu như nhau (hoặc cùng 1 hoặc cùng 0), không xét phần tử đó → nhảy xuống xét phần tử tiếp. Nghĩa là khi hai đầu mà khác nhau, tự thoát luôn, không phải bật cờ stop để thoát nữa. → Tức là đỡ tốn một biến cờ.
    Ngay sau khi thoát khỏi vòng lặp tức là phần tử hiện tại thoả mãn → nàng nạp luôn cái cạnh đó vào E' đồng thời làm các thủ tục khác như cộng độ dài cây khung và đánh dấu lại 2 đầu.
    Có nghĩa việc cải tiến này giảm đi được một biến cờ và một dòng lệnh IF.
    Chốt lại, tổng hợp cách viết của HTH (nòng cốt) + đóng góp sửa chữa của MRP + Cải tiến điều chỉnh thêm của PTHH ta sẽ được một chương trình chuẩn, tối ưu.
    Nháy vào đây để ẩn/hiện chương trình chuẩn tối ưu có công của cả 3 chuyên gia:

    1) Sắp xếp các danh sách cạnh sao cho:
    ds[1].t ≤ ds[2].t ≤...≤ ds[m].t
    2) FOR i := 1 TO n DO
              VT[i] := 0;
    3) k := 1;
    E'[k] = ds[1];
    T[ds[1].d] := 1;
    T[ds[1].c] := 1;
    m = m + ds[1].t;
    4) WHILE (k< n-1) DO
    j: = 2;
              WHILE (VT[ds[j].d] = VT[ds[j].c]) DO j = j + 1
    k++;
    E'[k] := ds[j];
    m = m + ds[j].t;
    VT[ds[j].d] := 1 ;
    VT[ds[j].c] := 1;
    5) output E', m
    Đúng là cờ ngoài, bài trong, làm việc tập thể và Internet có lợi thật.


    Đề nghị không mạo nhận Admin viết vào như thế này:
    Các bạn làm tập thể , tôi rất hoan nghênh.
    Nhưng Tôi thấy vòng lặp này chưa ổn, có thể sẽ chạy lỗi và không thoát được đó là vòng lặp
    WHILE (VT(ds[j].d) = VT(ds[j].c)) DO j++;
    thực tế vòng này không kiểm soát j, cho nên j = m + 1 là chắc chắn lỗi.
    vậy sửa lại như sau:
    WHILE (VT(ds[j].d) = VT(ds[j].c) and j < m) j++;
    điểm nữa là đánh dấu đỉnh đã xét thì nên dùng một loại, lúc T , lúc VT thì rất khó để đọc chương trình.
    Tôi đóng góp vậy thôi.
    (Có thể viết xuống dưới, không sửa vào bài bình luận, nên ghi tên người bình luận, không tự viết vào bài tên người khác khi nội dung không đúng với bài viết, có thể biên tập để rõ hơn, nhưng không được thay toàn bộ sang nội dung hoàn toàn khác)



    Được sửa bởi Admin ngày Thu Jul 28, 2011 5:48 am; sửa lần 4.


    ================
    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

    Tongmanhcuong


    Thành viên cao cấp
    Thành viên cao cấp
    Tôi rất vui khi một số thành viên có quan điểm giống tôi (Luôn luôn cố gắng để có được sản phẩm tốt). Nguyện theo nguyện vọng của anh Admin, tôi Post lên. Có gì góp ý nha. Bài của tôi là trường hợp Tổng quát.
    Thank Mrs Hồng for giving a happy.



    1) Sắp xếp danh sách Ds không giảm theo trường t (trọng số);

    For i:= 1 To n Do Chưa_xét[i]:= 0;

    k:= 1; E[k]:= Ds[1]; ts:= E[k].t;

    Chưa_xét[E[k].d]:=1; Chưa_xét[E[k].c]:=1;

    j:=1;

    2) While j <= m Do

              j:= j + 1;

              If (Chưa_xet[Ds[j].d]<>Chưa_xét[Ds[j].c]) Then

                        k:=k+1;

                        E[k]:=Ds[j]

                        Chưa_xét[E[k].d]:= 1; Chưa_xét[E[k].c]:=1;

                        ts:= ts+ E[k].t;

              If k=n-1 Then Break Else j:=1;

    3) If k < n-1 Then Output “Đồ thị không liên thông”

    Else Output ts, E;


    Anh Admin chỉnh lại cho đúng Hàng cột nhé.


    ================

    hungbeo_fm2008


    Chuyên viên
    Chuyên viên
    haihonglyk6 đã viết:ở phần 4 của Hiền nên sửa lại thế này hay hơn
    4. while (k< n-1)
    {
    j:=2;(sau mỗi lần thêm được 1 cạnh lại phải xét lại từ pt thứ 2)
    while (VT[ds[j].d] = VT[ds[j].c]) j=j+1
    k++;
    E'[k]:= ds[j]; m = m + ds[j].t;
    VT[ds[j].d]:=1; VT[ds[j].c]:=1;
    }
    Viết như em Hồng thế này dễ hiểu hơn.


    ================
    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.]

    hungbeo_fm2008


    Chuyên viên
    Chuyên viên
    Tôi đưa ra ý kiến thế này. Chúng ta giải quyết triệt để luôn bài toán: Viết giải thuật trong trường hợp đồ thị không liên thông (dùng prim) và dùng Kruskal để viết (liên thông + ko liên thông). Hai nữ cao thủ giải quyết luôn nhá. He he.


    ================
    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.]

    mrP


    Thành viên cao cấp
    Thành viên cao cấp
    - Chúng ta bị nhầm lẫn khi đặt biến m là tổng trọng số → đổi là ts.

    - Giải thuật PRIM nếu đồ thị G chưa cho biết có liên thông hay không thì đúng là có thể sinh ra lỗi trong câu lệnh WHILE (VT[ds[j].d] = VT[ds[j].c]) DO j = j + 1, vì xảy ra trường hợp j = m + 1. Vậy trong trường hợp G không nói gì về liên thông hay không, biết danh sách cạnh, tôi sửa lại phần 4 và 5 như thế này nhé. Các bạn đọc và cho ý kiến.

    4.
    WHILE (k < n - 1) DO
              j: = 2;
              WHILE (j ≤ m) & (VT[ds[j].d] = VT[ds[j].c]) DO j = j + 1;
              IF j = m + 1 THEN k := n //đồ thị không liên thông
              ELSE
                        k := k + 1;
                        E'[k] := ds[j];
                        ts := ts + ds[j].t;
                        VT[ds[j].d] := 1;
                        VT[ds[j].c] := 1;

    5.
    IF k = n - 1 THEN output E', ts
    ELSE
              Output "G không liên thông"


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

    mrP


    Thành viên cao cấp
    Thành viên cao cấp
    Giải thuật PRIM, biết ma trận kề, trọng số D[i,j]. Nếu đỉnh i không nối với đỉnh j thì D[i,j]=+∞.




    E': array [1...n-1] of cạnh;
    cạnh = record
                        đ, c: tên đỉnh;
              end;

    1.
    for i:=1 to n do Đx(i)=0;

    2.
    tmin:=+∞; i0=1; j0:=1;
    for i:=1 to n-1 do
              for j:=i+1 to n do
                        if tmin > D[i,j] then
                                  i0:=i; j0:=j; tmin:=D[i0,j0];

    k:=1; ts:= tmin;
    E'[k].đ :=i0; E'[k].c :=j0;
    Đx(io):=1; Đx(jo):=1;

    3.
    While k < n-1 do
              tmin:=+∞; i0=1; j0:=1;
              for i:=1 to n-1 do
                        for j:=i+1 to n do
                                  if (Đx(i)≠ Đx(j) and tmin > D[i,j]) then
                                            i0:=i; j0:=j; tmin:=D[i0,j0];

              if tmin = +∞ then k:= n //đồ thị không liên thông
              else
                        k:=k+1;
                        E'[k].đ :=i0; E'[k].c :=j0;
                        Đx(io):=1; Đx(jo):=1;
                        ts:= ts + tmin;

    4.
    If k=n-1 then output E', ts
    else
              Output "G không liên thông"



    Được sửa bởi mrP ngày Fri Jun 17, 2011 12:35 pm; sửa lần 1.


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

    hienha


    Chuyên viên
    Chuyên viên
    mrP đã viết:Giải thuật PRIM, biết ma trận kề, trọng số D[i,j]. Nếu đỉnh i không nối với đỉnh j thì D[i,j]=+∞.

    1. Đối với đồ thị vô hướng, giải thuật của anh có thể cải tiến 1 chút như thế này: ma trân trọng số có tính chất đối xứng nên ta chỉ cần xét vòng lặp thế này:
    for i:=1 to n
              for j:=i to n

    2. Em đưa ra 1 ý tưởng khác: chuyển ma trận kề về danh sách cạnh, sau đó giải như bài toán đã biết.
    đơn giản, giả sử ban đầu có ma trận trọng số A =(a(i,j)n với a(i,j)=0 nếu i không nối với j

    DS[1..n] of cạnh"
    cạnh = record
              d, c: đỉnh;
              ts: trọng số;
    end;

    k=0;
    for i:=1 to n
              for j:=i to n
                        if (a(i,j)>0)
                                  1. ca= new cạnh(); ca.d=i; ca.c=j; ca.ts=a(i,j);
                                  2. k:= k+1; DS[k] = ca;



    ================

    hienha


    Chuyên viên
    Chuyên viên
    Tongmanhcuong đã viết:Tôi rất vui khi một số thành viên có quan điểm giống tôi (Luôn luôn cố gắng để có được sản phẩm tốt). Nguyện theo nguyện vọng của anh Admin, tôi Post lên. Có gì góp ý nha. Bài của tôi là trường hợp Tổng quát.
    Thank Mrs Hồng for giving a happy.



    1) Sắp xếp danh sách Ds không giảm theo trường t (trọng số);

    For i:= 1 To n Do Chưa_xét[i]:= 0;

    k:= 1; E[k]:= Ds[1]; ts:= E[k].t;

    Chưa_xét[E[k].d]:=1; Chưa_xét[E[k].c]:=1;

    j:=1;

    2) While j <= m Do

              j:= j + 1;

              If (Chưa_xet[Ds[j].d]<>Chưa_xét[Ds[j].c]) Then

                        k:=k+1;

                        E[k]:=Ds[j]

                        Chưa_xét[E[k].d]:= 1; Chưa_xét[E[k].c]:=1;

                        ts:= ts+ E[k].t;

              If k=n-1 Then Break Else j:=1;

    3) If k < n-1 Then Output “Đồ thị không liên thông”

    Else Output ts, E;


    Anh Admin chỉnh lại cho đúng Hàng cột nhé.

    1. Vòng lặp while chỉ có thể đặt j < m. Nếu có dấu '='. khi j=m, vẫn thỏa mãn → j = j+1 = m+1 sẽ báo lỗi ở dòng lệnh Ds[j] tiếp theo
    2. Nếu đã đặt biến có ý nghĩa thì anh nên thay Chưa_xét = Đã_xét :)


    ================

    mrP


    Thành viên cao cấp
    Thành viên cao cấp
    @Hiền: Thanks. Do ma trận kề có tính đối xứng, D(i,i)= +∞, nên duyệt thế này có được không?

    for i:=1 to n-1
              for j:=i+1 to n


    - Ý tưởng chuyển về danh sách cạnh có lẽ tối ưu hơn, nhưng thủ tục em viết có lẽ chưa ổn lắm, vì số cạnh có phải bằng n đâu.


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

    sangminh2009


    Thành viên chưa phát huy chia sẻ
    Thành viên chưa  phát huy chia sẻ
    phần này các anh bàn luận nhiều quá.dẫn tới người đọc rất khó hiểu.em đề nghị BQT biên tập lai bài chuẩn về thủ tục PRIM và KUSRAL rồi đưa lên để cho thống nhất.
    Thanks

    BanBT: Nếu Khách viếng thăm đã điền đủ, đúng và nghiêm túc phần lý lịch, thì hệ thống đã tự bật cho bạn xem được thư mục bài chuẩn.

    18 Giai bai nay xem sao anh em oi! on Thu Jul 21, 2011 1:47 am

    huyenminh


    Thành viên chưa phát huy chia sẻ
    Thành viên chưa  phát huy chia sẻ
    Đồ thị G có n đỉnh U1, U2,..., Un, được cho bởi danh sách cạnh
    Cạnh = Record
    i, j : Tên đỉnh;
    t : Trọng số;
    End;
    D [ 1..M] of Cạnh;
    Viết chi tiết thuật toán PRIM để tìm cây khung bé nhất của G.
    Áp dụng thuật toán để tìm cây khung bé nhất của đồ thị G vô hướng sau:

    1, 2, 3

    2, 3, 3

    1, 6, 2

    2, 7, 1

    3, 8, 4

    5, 1, 3

    6, 2, 2

    7, 3, 5

    8, 4, 2

    5, 6, 4

    9, 5, 1

    10, 6, 3

    6, 11, 3

    6, 7, 4

    11, 7, 2

    7, 12, 2

    12, 8, 2

    9, 10, 4

    10, 11, 4

    11, 12, 5

    3, 4, 4

    5, 10, 4

    7, 8, 2

    4, 1, 7

    12, 9, 2

    Admin


    Quản trị viên
    Quản trị viên
    Về viết lệnh:
    [You must be registered and logged in to see this link.]
    Áp dụng thuật toán để tìm cây khung bé nhất của đồ thị G vô hướng sau:

    1, 2, 3

    2, 3, 3

    1, 6, 2

    2, 7, 1

    3, 8, 4

    5, 1, 3

    6, 2, 2

    7, 3, 5

    8, 4, 2

    5, 6, 4

    9, 5, 1

    10, 6, 3

    6, 11, 3

    6, 7, 4

    11, 7, 2

    7, 12, 2

    12, 8, 2

    9, 10, 4

    10, 11, 4

    11, 12, 5

    3, 4, 4

    5, 10, 4

    7, 8, 2

    4, 1, 7

    12, 9, 2
    Đầu tiên xếp theo thứ tự trọng số các cạnh tăng dần:
    TT đầu cuối trọng số
    1 2 7 1
    2 9 5 1
    3 1 6 2
    4 6 2 2
    5 8 4 2
    6 11 7 2
    7 7 12 2
    8 12 8 2
    9 7 8 2
    10 12 9 2
    11 1 2 3
    12 2 3 3
    13 5 1 3
    14 10 6 3
    15 6 11 3
    16 3 8 4
    17 5 6 4
    18 6 7 4
    19 9 10 4
    20 10 11 4
    21 3 4 4
    22 5 10 4
    23 7 3 5
    24 11 12 5
    25 4 1 7
    Cứ lấy từ trên xuống, cạnh nào mà tạo chu trình thì không lấy, đánh dấu vào bảng đỉnh. Bao giờ lấy đủ 12 đỉnh thì dừng lại. Ở đây đánh thứ tự lấy từng đỉnh, từng dòng để dễ quan sát và trình bày. Cột số thứ tự bên trái để Khách viếng thăm dễ đối chiếu với bảng trên ở thứ tự cạnh đã sắp xếp.
    [You must be registered and logged in to see this image.]


    ================
    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

    thangbom


    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    Admin đã viết:
    Về viết lệnh:
    [You must be registered and logged in to see this link.]
    Áp dụng thuật toán để tìm cây khung bé nhất của đồ thị G vô hướng sau:

    1, 2, 3

    2, 3, 3

    1, 6, 2

    2, 7, 1

    3, 8, 4

    5, 1, 3

    6, 2, 2

    7, 3, 5

    8, 4, 2

    5, 6, 4

    9, 5, 1

    10, 6, 3

    6, 11, 3

    6, 7, 4

    11, 7, 2

    7, 12, 2

    12, 8, 2

    9, 10, 4

    10, 11, 4

    11, 12, 5

    3, 4, 4

    5, 10, 4

    7, 8, 2

    4, 1, 7

    12, 9, 2
    Đầu tiên xếp theo thứ tự trọng số các cạnh tăng dần:
    TT đầu cuối trọng số
    1 2 7 1
    2 9 5 1
    3 1 6 2
    4 6 2 2
    5 8 4 2
    6 11 7 2
    7 7 12 2
    8 12 8 2
    9 7 8 2
    10 12 9 2
    11 1 2 3
    12 2 3 3
    13 5 1 3
    14 10 6 3
    15 6 11 3
    16 3 8 4
    17 5 6 4
    18 6 7 4
    19 9 10 4
    20 10 11 4
    21 3 4 4
    22 5 10 4
    23 7 3 5
    24 11 12 5
    25 4 1 7
    Cứ lấy từ trên xuống, cạnh nào mà tạo chu trình thì không lấy, đánh dấu vào bảng đỉnh. Bao giờ lấy đủ 12 đỉnh thì dừng lại. Ở đây đánh thứ tự lấy từng đỉnh, từng dòng để dễ quan sát và trình bày. Cột số thứ tự bên trái để thangbom dễ đối chiếu với bảng trên ở thứ tự cạnh đã sắp xếp.
    [You must be registered and logged in to see this image.]
    Tại bước thứ 5 có lỗi bạn à, bởi đỉnh vào phải là 7 12 2 không phải là 9 5 1, bởi chưa có đường đi tới 2 đỉnh 9 và đỉnh 5

    ddtbnt


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    Admin đã viết:Chương trình giả mã của Hà Thị có thể trình bày lại theo đúng dạng mẫu của thầy, như sau:
    Nháy vào khung màu hồng này để hiện, ẩn:

    1. Sắp xếp các danh sách cạnh sao cho:
    ds[1].t ≤ ds[2].t ≤...≤ ds[m].t
    2. FOR i := 1 TO n DO
    VT[i]:=0;




    3. k := 1;
    T[ds[1].d] := 1;
    E'[k] = ds[1];
    T[ds[1].c]:=1;
    m = m + ds[1].t;


    4. WHILE (k < n - 1) DO





    j: = 2;
    stop := false;






    WHILE (!stop) DO






    j: = 2;
    IF (VT[ds[j].d] != VT[ds[j].c]]) THEN




    k++;






    E'[k] := ds[j];






    m = m + ds[j].t;






    VT[ds[j].d] := 1;






    VT[ds[j].c] := 1;






    stop := true;




    ELSE
    j++;


    5. OUTPUT E', m






    Để làm rõ từng dòng lệnh, ta sẽ xem xét căn cứ vào thực tế nha.
    1. Đầu tiên đề bài cho cấu trúc dữ liệu được lưu trữ dưới dạng record có tên là DS. Nó có 3 trường gồm d: đỉnh đầu, c: đỉnh cuối và t là trọng số. Khi sắp xếp ds[1].t <= ds[2].t<=...<= ds[m].t có nghĩa là sắp trọng số tăng dần. Quá dễ hiểu, thôi đoạn này bỏ qua nha.
    2. Tiếp theo đoạn: FOR i:=1 to n rồi đặt VT[i]:=0; là Hà Thị đã reset đặt lại tất cả cái mảng theo dõi trạng thái của các đỉnh về 0. Uh, lẽ ra đặt tên dễ gợi nhớ đi 1 chút thì khó quên hơn, ví dụ như TD là theo dõi chẳng hạn. Thôi, không sao, VT thì VT. Nhớ VT là theo dõi đó nhen, i là đỉnh thứ mấy đó.
    3. Dòng này đặt k = 1 để đánh dấu rằng, bắt đầu lấy cạnh đầu tiên, k này vừa là số thứ tự, vừa là cạnh thứ mấy đó nhen.
    Đặt E'[k]=ds[1]; nghĩa là cạnh thứ k (vừa gán = 1 ở trên) bằng cạnh 1 trong danh sách ds. Đã đặt cả cạnh là 2 đầu mút rồi, Mrp nói cần đánh dấu 2 đỉnh này, nên cần thêm dòng đánh dấu 1 đầu này, T[ds[1].d]:=1; VT[ds[1].c]:=1;. quên đánh dấu 2 đỉnh này sẽ bị biến thành chu trình phần sau, OK.
    Đặt m= m+ ds[1].t; là nàng đo độ dài của cạnh thứ nhất (lấy trọng số ds[1].t), đưa vào tổng độ dài của cây khung. Việc đặt tên biến cũng không được rõ ràng tường minh cho lắm, ví dụ đặt là daick (dài cây khung chẳng hạn) thì có lẽ dễ theo dõi hơn. Nhưng thôi, bỏ qua tiểu tiết, nhớ là m là đo độ dài cây khung đó nhen.
    4. WHILE (k< n-1) do: Câu này quá dễ, chừng nào cây khung chưa đủ số cạnh = n-1 thì quyết kiếm cho đủ ! Tạm gọi vòng lặp này là vòng kiếm đủ số cạnh cho cây khung.
    j:=2 Xét từ cặp thứ 2: Rất khôn. Xem bình luận dưới.
    stop:= false; khởi tạo biến cờ, không có thôi gì cả, bao giờ xong, báo thôi thì mới thôi. Biến này dùng cho vòng FOR ở trong.
    WHILE (!stop) do: Chừng nào chưa thôi thì cứ làm! Tạm gọi vòng này là vòng kiếm cho được 1 cạnh mới thôi.
    if (VT[ds[j].d] != VT[ds[j].c]]) THEN Nếu đỉnh đầu và đỉnh cuối của phần tử thứ j trong danh sách, đánh dấu khác nhau thì:
    k++ đếm luôn: thêm 1 đỉnh
    E'[k]:= ds[j]; Cạnh thứ k bằng phần tử thứ j trong (danh sách cạnh đã sắp xếp ở đầu rồi)
    m = m + ds[j].t; Đo luôn trọng số, đưa vào độ dài cây khung.
    VT[ds[j].d]:=1; VT[ds[j].c]] = 1: Đánh dấu luôn 2 đỉnh này là 1.
    Chả sao cả, vì chẳng biết được đỉnh nào chưa đánh dấu, nếu nó đã được đánh dấu là 1 ở vòng trước rồi thì đánh lại chẳng sao, đỡ phải kiểm tra. Lưu ý là bên trên đã If (VT[ds[j].d] != VT[ds[j].c]]) có nghĩa là kiểm tra một đỉnh đã có dấu (1) và một đỉnh chưa có dấu (0) mới làm các bước trên. Ở đây không phải xét lung tung mà bản chất là xét phần tử thứ j của danh sách cạnh đã sắp xếp, xét 2 đỉnh đầu cuối của nó.
    stop = true: Đặt biến cờ cho vòng lặp này thôi. Nghĩa là đặt được thì thôi luôn, còn chưa đặt được thì xét cặp đỉnh khác.
    ELSE j++ Còn trường hợp khác, tăng j lên để xét phần tử kế tiếp trong danh sách cạnh đã sắp xếp.
    Thoát khỏi vòng lặp kiếm 1 cạnh, quay lại đầu vòng lặp kiếm đủ số cạnh, thấy ngay j: = 2, nhiều người bỏ quên cái câu j = 2 là chết oan ngay, vì phải xét lại từ đầu danh sách, để tránh bỏ sót. Khi làm bằng tay, ta để ý là có chỗ nhảy cách xuống phần kế danh sách, mà bên trên có phần tử lúc ý chưa thoả mãn, nhưng bây giờ nó mới thoả mãn thì ta lại lấy vào. Nghĩa là luôn luôn xét từ đầu danh sách, mỗi khi lấy xong một cạnh.
    5. Xong thì đưa nó ra bằng output, đưa ra các cạnh của cây khung E' và độ dài của cả cây khung m.
    Khách viếng thăm xem lại bình luận xem có cần thiết phải bổ sung không nha!
    [You must be registered and logged in to see this link.]

    ddtbnt


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    hienha đã viết:
    Tongmanhcuong đã viết:Tôi rất vui khi một số thành viên có quan điểm giống tôi (Luôn luôn cố gắng để có được sản phẩm tốt). Nguyện theo nguyện vọng của anh Admin, tôi Post lên. Có gì góp ý nha. Bài của tôi là trường hợp Tổng quát.
    Thank Mrs Hồng FOR giving a happy.



    1) Sắp xếp danh sách Ds không giảm theo trường t (trọng số);

    FOR i:= 1 To n Do Chưa_xét[i]:= 0;

    k:= 1; E[k]:= Ds[1]; ts:= E[k].t;

    Chưa_xét[E[k].d]:=1; Chưa_xét[E[k].c]:=1;

    j:=1;

    2) WHILE j <= m Do

              j:= j + 1;

              If (Chưa_xet[Ds[j].d]<>Chưa_xét[Ds[j].c]) THEN

                        k:=k+1;

                        E[k]:=Ds[j]

                        Chưa_xét[E[k].d]:= 1; Chưa_xét[E[k].c]:=1;

                        ts:= ts+ E[k].t;

              If k=n-1 THEN Break ELSE j:=1;

    3) If k < n-1 THEN Output “Đồ thị không liên thông”

    ELSE Output ts, E;


    Anh Admin chỉnh lại cho đúng Hàng cột nhé.
    1. Vòng lặp WHILE chỉ có thể đặt j < m. Nếu có dấu '='. khi j=m, vẫn thỏa mãn → j = j+1 = m+1 sẽ báo lỗi ở dòng lệnh Ds[j] tiếp theo
    2. Nếu đã đặt biến có ý nghĩa thì anh nên thay Chưa_xét = Đã_xét :)

    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 your own blog