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

    sonld1984


    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 Kruskal:
    T[1..n-1] of Edge;
    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):=i;




    3. k=0; ts:=0;






    4. For j=1 to m do







    If VT(ds[j].d) !=
    VT(ds[j].c) Then






    a. k++;






    T[k] := ds[j];






    ts:=ts + ds[j];






    b. tgd:= VT(ds[j].d);






    tgc:= VT(ds[j].c);





    for i:= 1 to n do






    If VT(i) := tgd Then VT(i):=tgc;
    5. output T, m






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

    2 Tìm cây khung nhỏ nhất bằng Kruskal on Thu Jun 16, 2011 8:06 pm

    hienha


    Chuyên viên
    Chuyên viên
    việc chọn cạnh đưa vào cây khung chỉ việc lấy từ trên xuống dưới (sau khi đã sắp xếp theo trọng số tăng dần) sao cho chúng không tạo thành chu trình. Ta sẽ giải quyết vấn đề làm thế nào để kiểm tra cây khung có tạo thành chu trình khi thêm 1 cạnh vào không.
    Tại mỗi bước ta có T là tập các cây khác nhau, nếu cạnh thêm vào có điểm đầu và điểm cuối cùng thuộc một cây thì chúng tạo thành chu trình. ta sẽ dùng mảng VT để đánh dấu đỉnh thuộc cây nào. Lúc đầu VT[i] = 0 với mọi i, tức là đỉnh chưa thuộc cây nào trong T.
    khi xét đến cạnh (d,c) sẽ xảy ra các TH sau:
    1. VT[d] = 0 & VT[c] = 0 → cả 2 đỉnh đều chưa thuộc cây nào trong T, tạo ra cây mới chứa cạnh này.
    2. VT[d] = 0 & VT[c] ≠ 0: cho cạnh vào T, gán lại VT[c] = VT[d];
    3. VT[d] ≠ 0 & VT[c] = 0: tương tự 2
    4. VT[d] ≠ VT[c] và cả 2 ≠ 0: 2 đỉnh đang thuộc 2 cây khác nhau: cho cạnh vào T, hợp nhất 2 cây bằng cách gán VT của các đỉnh của 1 cây = VT đỉnh cây còn lại
    5. VT[d]= VT[c] ≠ 0: 2 đỉnh này thuộc cùng 1 cây trong T, nếu cho vào tạo thành chu trình → bỏ qua.

    Tôi viết giả mã dựa trên ý tưởng đó, có thể chưa tinh, các đ/c cho ý kiến nhé.
    proc KRUSKAL()
    1. Sắp xếp các cạnh sao cho:
    ds[1].t ≤ ds[2].t ≤....≤ ds[m].t;
    2. FOR j := 1 TO n DO VT[j] := 0;
    3. //cho cạnh đầu tiên vào T, gán chỉ số cây 2 đỉnh của cạnh là 1
    k := 1, t := 1 //k: số các cạnh có trong T, t: số các cây có trong T
    VT[ds[1].d] := t; VT[ds[1].c] := t;
    E'[k] =ds[1]; m = ds[1].t ;
    i:= 2;
    4. WHILE k ≤ n -1 DO
              di := ds[i].d; ci := ds[i].c;// cho viết đoạn sau nó gọn thôi, k có mục đích gì khác
              IF (VT[di] ≠ 0 & VT[di] = VT[ci]) THEN // k làm gì cả
              ELSE
                        IF ( VT[di] + VT[ci] = 0) THEN //2 dinh chua Э cay nao
                                  t++;
                                  VT[di] := t; VT[ci] := t;
                        ELSE
                                  IF (VT[di] = 0) THEN
                                            VT[di] := VT[ci];
                                  ELSE IF (VT[di] = 0) THEN
                                            VT[ci] := VT[di];
                                  ELSE // VT[di] ≠ VT[ci] và đều ≠ 0
                                  // gán lại VT của cây chứa đỉnh đầu = VT của cây chứa đỉnh cuối
                                  temp:= VT[di];
                                  FOR s := 1 TO n DO
                                            IF (VT[s] = temp) THEN VT[s]: = VT[ci];
                        //thêm cạnh vào T:
                        k := k+1;
                        E’[k] := ds[i]; m = m + ds[i].t;
              i++;


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

    hienha


    Chuyên viên
    Chuyên viên
    Hi, ý tưởng thuật toán của em cũng tương tự của anh, chỉ khác cách đánh dấu đỉnh thuộc cây nào là khác chút thôi: anh khởi tạo n cây khác nhau rồi xét 2 đỉnh không thuộc cùng 1 cây thì cho cạnh vào T và hợp 2 cây lại. cách viết của anh gọn hơn :)


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

    Tongmanhcuong


    Thành viên cao cấp
    Thành viên cao cấp
    Không biết mọi người nghĩ về ý tưởng trên như thế nào. Nhưng cá nhân tôi thấy phức tập quá. Tôi chỉ cần 3,4 dòng lệnh là xong việc kiểm tra khi thêm một cạnh nó có tạo thành chu trình hay không? Mọi người nghĩ tiếp nha.


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

    Admin


    Quản trị viên
    Quản trị 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 Kruskal:
    T[1..n-1] of Edge;
    Bình luận một chút lời giải của LĐS. Đang đánh dở dang, mất điện lại phải gõ lại.
    1. Sắp xếp các danh sách cạnh sao cho:
    ds[1].t ≤ ds[2].t ≤...≤ ds[m].t

    Cái này theo đúng kiểu của thầy, đã hiểu, khỏi bình luận vì đã nói kỹ trong [You must be registered and logged in to see this link.]
    2. For i:=1 to n do VT(i):=i; Đánh dấu tất cả các đỉnh bằng số thứ tự đỉnh, cái này khác với Prim là đánh dấu 0 toàn bộ.
    3. k=0; ts:=0; Khởi tạo giá trị đầu. k là số thứ tự cạnh của cây T, còn ts là tổng số độ dài của cây.
    4. For j=1 to m do Kiểm tra lần lượt m cạnh hiện có của đồ thị G.
    If VT(ds[j].d) != VT(ds[j].c) Then Nếu hai đầu của cạnh hiện tại đánh dấu không giống nhau: Thực hiện 1 loạt việc:
    a. Các công việc để thêm cạnh hiện tại vào cây khung gồm:
    k ++ Tăng biến đếm cạnh hiện tại của cây khung lên.
    T[k] := ds[j]; Lấy cạnh hiện tại của G đưa vào cạnh của cây khung.
    ts:=ts + ds[j]; Đo độ dài của cây khung bằng cách công thêm cạnh hiện tại vừa thêm vào.
    b.Các công việc để đánh dấu lại
    tgd:= VT(ds[j].d); Ghi lại giá trị đánh dấu của đỉnh đầu cạnh đang xét
    tgc:= VT(ds[j].c); Ghi lại giá trị đánh dấu của đỉnh cuối cạnh đang xét
    for i:= 1 to n do Kiểm tra lần lượt các đỉnh:
    If VT(i) := tgd Then VT(i):=tgc; Nêu đỉnh đầu nào mà có đánh dấu giống như giá trị lưu trong tgd thì thay giá trị đánh dấu bằng giá trị lưu trong tgc. Điều này nghĩa là sẽ đồng nhất các đỉnh đã nối sẽ cùng đánh dấu một giá trị. Khi đó những đỉnh đã nối vào với nhau sẽ không nối nội bộ được nữa, điều này sẽ khiến không thể tạo thành chu trình bởi dòng lệnh
    If VT(ds[j].d) != VT(ds[j].c) chỉ cho phép nối các đỉnh có đánh dấu khác nhau.
    5. output T, m

    Nhận xét:
    Có tạo thành cây khung không? Có vì tạo thành khi đã đánh dấu các đỉnh đã có cạnh cùng một giá trị.
    Có nên duyệt hết tất cả các cạnh không?
    Giả sử: có đồ thị G và cây khung như bên dưới đây:
    [You must be registered and logged in to see this image.]
    Có 5 đỉnh, 10 cạnh. Sao không đếm đủ số cạnh = 4 thì thôi luôn, mà lại cứ phải tìm hết 10 cạnh, thực chất là việc tìm cho đủ số cạnh là không cần thiết, sau khi đã kiếm đủ 4 cạnh rồi. Các bạn nhìn xem, nếu số đỉnh là 100, số cạnh có thể rất lớn... nếu như tất cả các đỉnh được nối với nhau?


    ================
    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
    - Đ/c Admin sửa sai cấu trúc của đ/c Son rồi.

    câu lệnh
    for i:= 1 to n do If VT(i) := tgd Then VT(i):=tgc; phải nằm trong dòng lệnh (b) nhé.



    - Trong trường hợp cạnh thưa, thì việc duyệt cạnh theo như đ/c Son For j=1 to m do .... là tương đối tốt(thủ tục Viết lại 2 - trang 116). Nếu sử dụng vòng while k < n-1(thủ tục Viết lại 1 - trang 116) thì mỗi một giá trị k, ta phải duyệt lại cạnh từ đầu.
    - Trong trường hợp nhiều cạnh như ví dụ đ/c Admin đưa ra thì sử dụng while k < n-1 sẽ tốt hơn. Nhưng nếu trọng số bằng nhau hết thì có khi cũng phải duyệt hết, chẳng bỏ được cạnh nào.


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

    HaiYen


    Thành viên cao cấp
    Thành viên cao cấp
    Việc bây giờ là các anh chị cần giải thêm với cấu trúc dữ liệu cho dưới dạng ma trận kề và cho bởi danh sách liên kết. Em nghĩ nếu không nghĩ cách viết thủ tục riêng để gọi vào thì cũng tương đối rắc rối, ở chỗ rất dễ nhầm lẫn.


    ================
    Nhà em cách 4 quả đồi
    Cách 3 con suối, cách đôi cánh rừng
    Nhà em xa cách quá chừng
    Em van anh đấy, anh đừng yêu em!...

    FaceBook của em

    hienha


    Chuyên viên
    Chuyên viên
    Tongmanhcuong đã viết:Không biết mọi người nghĩ về ý tưởng trên như thế nào. Nhưng cá nhân tôi thấy phức tập quá. Tôi chỉ cần 3,4 dòng lệnh là xong việc kiểm tra khi thêm một cạnh nó có tạo thành chu trình hay không? Mọi người nghĩ tiếp nha.

    cả 2 ý tưởng trên đều giống thuật toán thầy giảng, a có ý tưởng hay hơn, sao k trình bày với thầy xem thầy nghĩ sao.


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

    hienha


    Chuyên viên
    Chuyên viên
    sonld1984 đã viết: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 Kruskal: T[1..n-1] of Edge;

    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):=i;






    3. k=0; ts:=0;








    4. For j=1 to m do










    If VT(ds[j].d) !=

    VT(ds[j].c) Then








    a. k++;








    T[k] := ds[j];








    ts:=ts + ds[j];








    b. tgd:= VT(ds[j].d);








    tgc:= VT(ds[j].c);





    for i:= 1 to n do











    If VT(i) := tgd Then

    VT(i):=tgc;

    5. output T, m








    Đúng là lệnh for i:=1 to n phải nằm trong b. Hơn nữa, với đồ thị liên thông thì không nên xét cả m cạnh (forj:=1 to m) mà nên xét đến khi k =n-1 thôi (while k< n-1)


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

    hienha


    Chuyên viên
    Chuyên viên
    Tôi sửa lại bài viết cho giống cách viết của thầy:
    cách 1:
    proc KRUSKAL()

    1) Sắp xếp ds[1].t ≤ ds[2].t ≤ ....≤ ds[m].t;

    2) FOR x := 1 TO n DO sh[x] := 0;

    3) //cho cạnh đầu tiên vào T, gán chỉ số cây 2 đỉnh của cạnh là 1
    k := 1, s := 1 //k: số các cạnh có trong T, s: số hiệu cây
    sh[ds[1].d] := s; sh[ds[1].c] := s;
    E'[k] = ds[1]; ts = ds[1].t ;
    j := 2;

    4) WHILE k ≤ n -1 DO
    {
              WHILE (sh[ds[j].d] = sh[ds[j].c] & sh[ds[j].c] ≠ 0) j++;
    d := ds[i].d; c := ds[i].c;// cho viết đoạn sau nó gọn thôi, k có mục đích gì khác
    p := sh(d); q := sh(c);
              IF (p = q ) THEN
                        s := s + 1;
                        sh(d) := s; sh(c) := s;
              ELSE
                        a) t := p; IF q > 0 THEN t := q;
                        b) IF (p.q = 0)THEN
                                  sh(d) := t; sh(c) := t;
                        ELSE
                                  FOR x := 1 TO n DO
                                            IF(sh(x) = p || sh(x) = q) THEN sh(x) := t;
    //thêm cạnh vào T:
              k := k + 1;
              E’[k] := ds[j]; ts= ts + ds[j].t;
              j:= j + 1;
    }
    5) output E', ts

    cách 2: Ban đầu đánh số mỗi đỉnh là một cây

    proc KRUSKAL()

    1) Sắp xếp ds[1].t ≤ ds[2].t ≤....≤ ds[m].t;

    2) FOR x := 1 TO n DO sh[x] := x;

    3) k := 0; ts := 0; j := 1;

    4) WHILE k ≤ n - 1 DO
    {
              WHILE ( sh[ds[j].d] = sh[ds[j].c] ) DO j++;
    d := ds[i].d; c := ds[i].c;// cho viết đoạn sau nó gọn thôi, k có mục đích gì khác
    p := sh(d); q := sh(c);

    FOR x := 1 TO n DO
              IF(sh(x) = p) THEN sh(x) := q;

    //thêm cạnh vào T:
    k := k + 1;
    E’[k] := ds[j]; ts = ts + ds[j].t;
    j := j + 1;
    }

    5. output E', ts



    Được sửa bởi hienha ngày Sun Jun 19, 2011 4:09 pm; sửa lần 1.


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

    hienha


    Chuyên viên
    Chuyên viên
    mrP đã viết:- Đ/c Admin sửa sai cấu trúc của đ/c Son rồi.

    câu lệnh
    for i:= 1 to n do If VT(i) := tgd Then VT(i):=tgc; phải nằm trong dòng lệnh (b) nhé.

    - Trong trường hợp cạnh thưa, thì việc duyệt cạnh theo như đ/c Son For j=1 to m do .... là tương đối tốt(thủ tục Viết lại 2 - trang 116). Nếu sử dụng vòng while k < n-1(thủ tục Viết lại 1 - trang 116) thì mỗi một giá trị k, ta phải duyệt lại cạnh từ đầu.
    - Trong trường hợp nhiều cạnh như ví dụ đ/c Admin đưa ra thì sử dụng while k < n-1 sẽ tốt hơn. Nhưng nếu trọng số bằng nhau hết thì có khi cũng phải duyệt hết, chẳng bỏ được cạnh nào.

    đ/c Phương có chút nhầm lẫn nha, đối với thuật toán Kruskal, luôn duyệt các cạnh từ trên xuống theo danh sách đã sắp xếp, nên k có chuyện duyệt lại từ đầu (j=2 ở ngoài vòng while)


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

    mrP


    Thành viên cao cấp
    Thành viên cao cấp
    - Nhầm lẫn là do thứ 6 ở nhà ngủ. Bài viết đấy viết trước khi thầy làm mẫu thuật toán Kruskal, tớ trích dẫn thuật toán trên là trong sách của thầy (tớ đã ghi là Viết lại 1/ trang 116 rồi mừ )- thế mà còn chém mình. Còn cách mọi người làm bây giờ là có cải tiến chút ít nên không cần duyệt lại từ đầu. OK.

    - Nếu xem xét lại thuật toán mới của thầy thì đúng là tối ưu hơn cả. Vì trong cả hai cách nếu sh[ds[j].d] = sh[ds[j].c] thì chỉ thực hiện j++, còn nếu khác nhau thì gán vào E[k+1], tăng ts. Trong trường hợp xấu nhất, tức là cả hai đều xét hết các cạnh thì rõ ràng số bước thực hiện là như nhau. Còn bình thường nếu duyệt theo cạnh i:=1 to m thì khi k=n-1 rồi, nó vẫn bắt buộc thực hiện tiếp lệnh j++ cho đến khi duyệt hết cạnh.

    - Spam, câu view tí...
              (huytsao)

    - Nhân tiện nhờ em Hiền xem hộ bài này nhé : [You must be registered and logged in to see this link.]


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

    Admin


    Quản trị viên
    Quản trị viên
    Nếu đề ra như sau:
    Đồ thị G liên thông n đỉnh được đánh số từ 1 đến n nhưng được cho bởi ma trận trọng số A = (aij) viết thủ tục xây dựng cây khung bé nhất?
    Ta vẫn làm như vậy nha. Thử xem nào.
    Bước đầu tiên bao giờ cũng phải là mô tả cấu trúc cây khung. Bỏ bước này trừ một nửa số điểm.
    T : ARRAY (1.. n-1) of Cạnh
              Cạnh = record
              d, c: tên đỉnh;
              end;

    Bước thứ 2 viết một số thủ tục nho nhỏ nếu có để tiện sử dụng. Việc viết này giúp ta không phải viết đi viết lại một đoạn mã.
    Ví dụ
    Code:
    FUNC ChonDuoc (i, j: tên đỉnh): Boolean
    ChonDuoc = c(i) ≠ c(j)

    Bước 3. Chọn một thuật toán để viết.
    Viết bằng thuật toán Kruskal:
    1) FOR i = 1 TO n DO c(i) = i;
    2) k = 0;
    3) WHILE k < n -1 DO
              a) ts_min = + ∞;
                        FOR i = 1 TO n DO
                                  FOR j = 1 TO n DO
                                            IF ChonDuoc(i,j) & (A(i,j) < ts THEN
                                                      io = i,
                                                      jo = j;
                                                      ts_min = A(i, j)
              b)k ++; T(k).d = io; T(k).c = jo;
    4)OUTPUT(T(1..n-1)
    Viết bằng thuật toán Prim:
    FOR i = 1 TO n DO c(i) =Ø;
    2) k = 1; A( io jo) = min {A(i, j)}
    T(1).d = io; T(1).c = jo;
    c(io) = 1; c(jo) = 1;
    ts = A(io,(jo);
    3) WHILE k < n -1 DO
              a) ts_min = + ∞;
                        FOR i = 1 TO n DO
                                  FOR j = 1 TO n DO
                                            IF ChonDuoc(i,j) & (A(i,j) < ts THEN
                                                      io = i,
                                                      jo = j;
                                                      ts_min = A(i, j)
              b)k ++; T(k).d = io; T(k).c = jo;
              c(io) = 1; c(jo) = 1;
              ts = ts + A(io,(jo)
    4)OUTPUT(T(1..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

    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 | www.sosblogs.com