Jan 8 2012, 03:39 PM Bởi: hanguyenphuongthu

BÀI TOÁN TÌM CÂY BAO TRÙM NHỎ NHẤT

Tìm cây bao trùm nhỏ nhất (tiếng Anh: minimum spanning tree) là bài toán tối ưu có nhiều ứng dụng trong thực tế. Nó có thể là bài toán tìm hệ thống liên thông với chi phí nhỏ nhất, hoặc ngược lại, vói lợi nhuân lớn nhất. Hai thuật toán tìm cây bao trùm nhỏ nhất và lớn nhất thường được nhắc đến là thuật toán Prim và thuật toán Krusskal.
Bài toán

Cho G=(X,E) là một đồ thị liên thông. Ngoài ra, một hàm trọng số W(e) nhận các giá trị thực, xác định trên tập các cạnh E của G. Cả hai thuật toán Prim và Kruskal đều dựa trên tư tưởng của các giải thuật tham lam: Ở mỗi bước của thuật toán ta chọn và bổ sung vào cây cạnh có trọng số nhỏ nhất có thể.
Giải thuật Prim

Giải thuật Prim dựa trên cấu trúc của giải thuật tìm cây bao trùm theo chiều rộng hoặc chiều sâu, chỉ thay đổi về tiêu chuẩn chọn đỉnh sẽ bổ sung vào cây ở từng bước.

Vài nét R. C. Prim
Robert Clay Prim (sinh 1921 tại Sweetwater, Texas) là một nhà toán học và khoa học máy tính Mỹ. Năm 1941 ông đã lấy bằng cử nhân ở khoa kỹ thuật điện đại học Princeton. Sau này năm 1949, ông nhận bằng Ph.D. về toán học cũng tại đây. Giải thuật mang tên Prim được tìm ra từ năm 1930 bởi nhà toán học Vojtěch Jarník và do Prim hoàn thiện vào năm 1957.
Mô tả

Gọi T là cây bao trùm sẽ xây dựng
1. Chọn một đỉnh s bất kỳ của G cho vào cây T. Khi đó T là một cây chỉ có một đỉnh và chưa có cạnh nào.
2. Nếu T đã gồm tất cả các đỉnh của G thì T là cây bao trùm cần tìm. Kết thúc.
3. Nếu G còn có các đỉnh không thuộc T, vì G liên thông nên có các cạnh nối một đỉnh trong T với một đỉnh ngoài T, chọn một cạnh có trọng số nhỏ nhất trong số đó cho vào T.
4. Quay lại 2.

Giả mã

Giải thuật trình bày Prim ở trên dễ dàng thực hiện khi ta quan sát một đồ thị được biểu diễn trên mặt phẳng với một số ít đỉnh. Tuy nhiên để cài đặt thành một chương trình chạy trên máy tính cũng cần phân tích thêm một số điểm.
Liệu có thể sử dụng một hàng đợi (queue) giống như trong giải thuật tìm cây bao trùm theo chiều sâu không? Có. Nhưng điều khác biệt là ta sẽ sử dụng một hàng đợi có ưu tiên, tiêu chuẩn ưu tiên ở đây là cạnh nối đỉnh sẽ được bổ sung vào T là nhỏ nhất. Một cấu trúc thuận lợi cho hàng đợi có ưu tiên là cấu trúc đống (heap) như đã sử dụng trong giải thuật sắp xếp vun đống hoặc giải thuật xây dựng mã Huffman. Giả sử G=(X,E) là đồ thị liên thông, Ajd(u), là danh sách đỉnh kề của đỉnh u. L(e) là hàm trọng số xác đinh với moi cạnh . Trong đoạn mã sau ta dùng hàm COLOR(u) để tô màu các đỉnh của G bằng các màu WHITE, GRAY, BLACK để chỉ các trạng thái chưa xét, đang xét và đã xét xong của mỗi đỉnh, hàm PARENTS(u) chỉ đỉnh cha của đỉnh u trong cây, hàm DISTAN(u,T) chỉ trọng số nhỏ nhất của các cạnh nối từ đỉnh u ngoài T đến các đỉnh trong T. Ta cũng sử dụng một cấu trúc HEAP làm hàng đợi ưu tiên chứa các đỉnh đang chờ xét.
Ở bước khởi tạo, một đỉnh r bất kỳ được đưa vao Heap. Số các phần tử của đống là n=1. Cho đến khi hàng đợi Heap còn khác rỗng ta thực hiện các bước sau: lấy đỉnh u nằm ở gốc Heap ra để đưa vào cây. Đối với đỉnh u mới được bổ sung vào cây ta duyệt qua tất cả các đỉnh v thuộc danh sách kề với nó. Nếu đỉnh v chưa thuôch T và không nằm trong đống ta chèn v vào đống, nếu đỉnh v đã nằm trong đống đợi ta tính lại khoảng cách từ v của nó với tập các đỉnh đã nằm trong T, và vun lại đống. Sau khi tất cả các đỉnh ) đã duyệt qua bằng cách ấy thì thì đỉnh u đã được duyệt xong và được đưa vào cây.

Procedure Prim (G, r, W(e)) {
Var list COLOR(u), PARENTS(u), DISTAN(u),Heap H

For each u of E {
COLOR(u)= WHITE
PARENTS(u)=Null
DISTAN(u)= M
}
H(1)=r
n=1
DISTAN®=0
While n> 0 do
u=H(1)
n=n-1
Color(u)=BLACK
For each v of Ajd(u) {
if (Color(v)=WHITE)
or ((Color(v)=GRAY) and (DISTAN(v) then
{
COLOR(v)=GRAY
PARENTS(v)=u
DISTAN(v)=W(u,v)
if Color(v)=WHITE then InsertHeap(H,v)
else UpHeap(H,HeapIndex(v))

}
}
}

Một chương trình đầy đủ bằng ngôn ngữ Pascal

program
Prim_Algorithm;
uses dos,crt;
const max=150;
type
filename=string[12];
var
TrongSo: array[1..max,1..max] of integer;
DinhKe: array[1..max] of integer;
CanhKe: array[1..max] of integer;{}
n, DodaiCayKhung: integer;
i,j: integer;
fname: filename;
ch: char;
h,m,s, hund:word;
procedure PrintMatrix;
Begin
(*In ma tran ra *)
Writeln('-------------------------------------------------------');
Writeln('Ma tran trong so, Khong co canh noi thi trong so = MaxInt');
for i:=1 to n do
Begin
For j:=1 to n do
if TrongSo[i,j]=Maxint then write(' 0',' ')
else write(TrongSo[i,j]:5,' ');
Writeln;
End;
Writeln('-------------------------------------------------------');
End;
procedure
ReadInputFile(fname: filename);
var
i,j: integer;
f: text;
begin
assign(f,fname);
reset(f);
readln(f,n);
for i:=1 to n do
begin
for j:=1 to n do
begin
read(f,TrongSo[i,j]);
if TrongSo[i,j]=0 then TrongSo[i,j]:=MaxInt;
end;
readln(f);
end;
close(f);
PrintMatrix;
end;
procedure Prim;
var
v,i,k: integer;
min: integer;
begin
for v:=2 to n do
begin
DinhKe[v]:=1;
CanhKe[v]:=TrongSo[1,v];
end;
for i:=2 to n do
begin
min:=MaxInt;
for k:=2 to n do
if (CanhKe[k]>=0) and (CanhKe[k] begin
min:=CanhKe[k]; (
v:=k;
end;
CanhKe[v]:=-1;
for k:=2 to n do
if (TrongSo[v,k]0) then
begin
CanhKe[k]:=TrongSo[v,k];
DinhKe[k]:=v;
end;
end;
end;
procedure
WriteOutputFile;
var
i: integer;
f: text;
begin
assign(f,'prim.out');
rewrite(f);
Writeln(f,'-------------------------------------------------------');
Writeln(f,'Ma tran trong so, Khong co canh noi thi trong so = MaxInt');
for i:=1 to n do
Begin
For j:=1 to n do
if TrongSo[i,j]=Maxint then write(f,' 0',' ')
else write(f,TrongSo[i,j]:5,' ');
Writeln(f,);
End;
Writeln(f,'-------------------------------------------------------');
DodaiCayKhung:=0;
writeln(f,'Cay khung nho nhat gom cac canh:');
for i:=2 to n do
begin
write(f,'(',i,',',DinhKe[i],') ');
DodaiCayKhung:=DodaiCayKhung+TrongSo[i,DinhKe[i]];
end;
writeln(f);
writeln(f,'Length: ',DodaiCayKhung);
close(f);
end;
begin
repeat
clrscr;
writeln('THUAT TOAN PRIM TIM CAY KHUNG NHO NHAT');
writeln(' DUNG MA TRAN KE');
writeln('---------------------------------------');
writeln(' Hay bam phim chuc nang:');
Writeln;
writeln(' K(eyboard). Chay chuong trinh - Du lieu nhap tu ban phim.');
Writeln;
writeln(' F(ile). Chay chuong trinh - Du lieu lay tu File.');
Writeln;
writeln(' R(andom). Chay chuong trinh - Du lieu Random.');
Writeln;
writeln(' Q(uit). Thoat khoi chuong trinh.');
Writeln;
ch:=ReadKey;
case UpCase(ch) of
'F':
begin
write(' Hay nhap ten tep du lieu:'); readln(fname);
ReadInputFile(fname);
gettime(h,m,s,hund);
Writeln('Bat dau chay: ',h,':',m,':',s,':',hund);
Prim;
gettime(h,m,s,hund);
Writeln('Ket thuc chay: ',h,':',m,':',s,':',hund);
WriteOutputFile;
write('Cac canh cua cay khung be nhat:');
for i:=2 to n do write('(',i,',',DinhKe[i],')');
writeln;
writeln('Gia cua cay khung : ',DodaiCayKhung);
writeln('***************************************') ;
writeln('Nhan phim Enter de tiep tuc.');
readln;
end;
'R':
begin
write('Hay nhap so dinh cua do thi:'); readln(n);
for i:=1 to n do TrongSo[i,i]:=0;
for i:=1 to n-1 do
For j:=i+1 to n do TrongSo[i,j]:=random(100);
for i:=2 to n do
For j:=1 to i-1 do TrongSo[i,j]:=TrongSo[j,i];
PrintMatrix;
for i:=1 to n do
for j:=1 to n do
if TrongSo[i,j]=0 then TrongSo[i,j]:=MaxInt;
gettime(h,m,s,hund);
Writeln('Bat dau chay: ',h,':',m,':',s,':',hund);
Prim;
gettime(h,m,s,hund);
Writeln('Ket thuc chay: ',h,':',m,':',s,':',hund);
write('Cac canh cua cay khung be nhat:');
for i:=2 to n do write('(',i,',',DinhKe[i],')');
WriteOutputFile;
Writeln;
writeln('Gia cua cay khung : ',DodaiCayKhung);
writeln;
writeln('***************************************') ;
writeln('Nhan phim Enter de tiep tuc.');
readln;
end;
'K':
begin
write('Hay nhap so dinh cua do thi:'); readln(n);
for i:=1 to n do TrongSo[i,i]:=0;
for i:=1 to n-1 do
For j:=i+1 to n do
Begin
Write('a[',i,j,']=');
readln(TrongSo[i,j]); (* Nua tren *)
End;
for i:=2 to n do
For j:=1 to i-1 do TrongSo[i,j]:=TrongSo[j,i];
PrintMatrix;
for i:=1 to n do
for j:=1 to n do
if TrongSo[i,j]=0 then TrongSo[i,j]:=MaxInt;
gettime(h,m,s,hund);
Writeln('Bat dau chay: ',h,':',m,':',s,':',hund);
Prim;
gettime(h,m,s,hund);
Writeln('Ket thuc chay: ',h,':',m,':',s,':',hund);
write('Cac canh cua cay khung be nhat:');
for i:=2 to n do write('(',i,',',DinhKe[i],')');
WriteOutputFile;
writeln;
writeln('Gia cua cay khung : ',DodaiCayKhung);
writeln('***************************************') ;
writeln('Nhan phim Enter de tiep tuc.');
readln;
end;
end;
until
UpCase(ch)='Q';
end.

Permalink | Bình luận: 0

Trả lời ở chế độ đầy đủ

« Các bài cũ hơn · hanguyenphuongthu's Blog · Các bài mới hơn »

Thông tin cá nhân

hanguyenphuongthu

Nghề nghiệp:	sinh viên IT
Sinh nhật: :	26 Tháng 11 - 1992
Yahoo:	ngoncolau_mt2001
Trạng thái:	(Vắng mặt)

Thêm vào nhóm bạn bè
Gửi tin nhắn

luôn may mắn, hạnh phúc và thành đạt

Bạn bè

vutranvhp	huynhdang.it
dulichch0l0n	muabanaothun
cowboyviet	Hoài Mộng
codosocial	idochoi
honhao	kientrucnoithatitalia01
Xem tất cả