Gia sư Cần Thơ, Dạy Kèm Cần Thơ

VỮNG TIN - TIẾP BƯỚC - THÀNH CÔNG


Bài 4. Tìm cây phủ tối tiểu bằng nguyên lý tham lam

Share
avatar
admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 37
Đến từ : Cần Thơ

Bài 4. Tìm cây phủ tối tiểu bằng nguyên lý tham lam

Bài gửi  admin on Sun Dec 19, 2010 4:26 pm

TÌM CÂY PHỦ TỐI TIỂU CỦA ĐỒ THỊ VÔ HƯỚNG G


BÀI TOÁN
Tìm cây phủ tối tiểu của đồ thị vô hướng G.
THUẬT TOÁN PRIM

CODE MẪU
Code:
(*BAI TOAN : LAP DIEN THOAI
    THUAT TOAN : PRIM - NGUYEN LY THAM LAM*)
(*Ma tran doi xung cap n duoc phat sinh ngau nhien trong doan [a, b]*)
MaTranDoiXung[n_, a_, b_] := Module[{L, i, j},
         L = Table[0, {i, n}, {j, n}];
         For[i = 2, i ≤ n, i++,
           For[j = 1, j < i, j++,
                  L[[i, j]] = L[[j, i]] = Random[Integer, {a, b}];
               ];
           ];
         Return[L];
      ];
(*Thuat toan Prim tim cay phu toi tieu*)
ThuatToanPrim[A_, n_] := Module[{m, M, L, W, i, j, Dem, u, v, min, w},
         (*Lay 1 dinh ngau nhien m lam dinh bat dau*)
         m = Random[Integer, {1, n}];
         (*M : luu tap dinh duoc lay*)
         M = {m};
         (*L : luu canh duoc di qua*)
         L = {};
         (*w : tong trong so nho nhat*)
         w = 0;
         Dem = 1;
         While[Dem < n,
              min = ∞;
              For[i = 1, i ≤ Dem, i++,
                   For[j = 1, j ≤ n, j++,
                        If[Intersection[M, {j}] == {} && A[[M[[i]], j]] > 0 && min > A[[M[[i]], j]],
                             u = M[[i]];
                             v = j;
                             min = A[[u, v]];
                          ];
                     ];
                ];
              w += A[[u, v]];
              M = Append[M, v];
              L = Append[L, {u, v}];
              Dem++;
           ];
         Return[{L, w}];
];

Clear[n, a, A, b, L];
n = Input["Nhap so dinh cua do thi G "];
a = Input["Nhap a = "];
b = Input["Nhap b = "];
A = MaTranDoiXung[n, a, b];
Print["------- Thuat toan Prime --------"];
Print["So dinh n = ", n];
Print["Ma tran doi xung duoc tao ngau nhieu trong khoang [", a, ",", b, "]"];
Print[MatrixForm[A]];
L = ThuatToanPrim[A, n];
Print["Trong so nho nhat w = ", L[[2]]];
Print["Canh duoc chon:", L[[1]]];

    Hôm nay: Tue Dec 11, 2018 9:15 pm