Chu trinh Haminton de quy

37 %
63 %
Information about Chu trinh Haminton de quy

Published on June 23, 2008

Author: hcdung18

Source: slideshare.net

Giáo viên hướng dẫn: TS. Hoàng Quang Nhóm 6: Nguyễn Mậu Quốc Hoàn Mai V ă n M ười Trần Thị Phương Chi Trương Thị Hương Huyền

NỘI DUNG TRÌNH BÀY Giới thiệu bài toán Định nghĩa Chu trình Hamilton Mô hình bài toán Các bước giải quyết bài toán Thủ tục mô tả thuật toán Thời gian thực hiện

Giới thiệu bài toán

Định nghĩa Chu trình Hamilton

Mô hình bài toán

Các bước giải quyết bài toán

Thủ tục mô tả thuật toán

Thời gian thực hiện

GIỚI THIỆU BÀI TOÁN Một người khách du lịch muốn đi thăm n thành phố được đánh số từ 1 đến n. Mạng lưới giao thông giữa n thành phố này là 2 chiều và được cho bởi ma trận A[i,j] trong đó A[i,j] = 1 nếu có đường đi giữa thành phố i và thành phố j, A[i,j] = 0 trong trường hợp ngược lại. Thiết lập đường đi cho người khách thông báo tồn tại đường đi hoặc không tồn tại đường đi.

Một người khách du lịch muốn đi thăm n thành phố được đánh số từ 1 đến n. Mạng lưới giao thông giữa n thành phố này là 2 chiều và được cho bởi ma trận A[i,j] trong đó A[i,j] = 1 nếu có đường đi giữa thành phố i và thành phố j, A[i,j] = 0 trong trường hợp ngược lại. Thiết lập đường đi cho người khách thông báo tồn tại đường đi hoặc không tồn tại đường đi.

ĐỊNH NGHĨA CHU TRÌNH HAMILTON Cho đồ thị G=(V, E) có n đỉnh Chu trình (x 1 , x 2 , …, x n , x 1 ) được gọi là Chu trình Hamilton nếu x i <>x j với 1<=i<j<=n Đường đi (x 1 , x 2 , …, x n ) được gọi là Đường đi Hamilton nếu x i <>x j với 1<=i<j<=n Chu trình Hamilton là chu trình xuất phát từ một đỉnh, đi thăm tất cả những đỉnh còn lại, mỗi đỉnh đúng một lần, cuối cùng quay lại đỉnh xuất phát. Đường đi Hamilton là đường đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần.

Cho đồ thị G=(V, E) có n đỉnh

Chu trình (x 1 , x 2 , …, x n , x 1 ) được gọi là Chu trình Hamilton nếu x i <>x j với 1<=i<j<=n

Đường đi (x 1 , x 2 , …, x n ) được gọi là Đường đi Hamilton nếu x i <>x j với 1<=i<j<=n

Chu trình Hamilton là chu trình xuất phát từ một đỉnh, đi thăm tất cả những đỉnh còn lại, mỗi đỉnh đúng một lần, cuối cùng quay lại đỉnh xuất phát.

Đường đi Hamilton là đường đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần.

VÍ DỤ VỀ CHU TRÌNH VÀ ĐƯỜNG ĐI HAMILTON Một đồ thị đầy đủ có nhiều hơn hai đỉnh là đồ thị Hamilton. Mọi đồ thị vòng là Hamilton. Đồ thị khối ba chiều là đồ thị Haminton.

MÔ HÌNH BÀI TOÁN (1) Ta có file: Input: Là file văn bản Input.pas Dòng 1 ghi số đỉnh n<=50 và số cạnh m của đồ thị cách nhau một dấu cách. m dòng tiếp theo, mỗi dòng có dạng 2 số nguyên dương u, v cách nhau một dấu cách, thể hiện u, v là 2 đỉnh kề nhau trong đồ thị. Output: là file văn bản Output.pas Liệt kê tất cả các chu trình Hamilton

Ta có file:

Input: Là file văn bản Input.pas

Dòng 1 ghi số đỉnh n<=50 và số cạnh m của đồ thị cách nhau một dấu cách.

m dòng tiếp theo, mỗi dòng có dạng 2 số nguyên dương u, v cách nhau một dấu cách, thể hiện u, v là 2 đỉnh kề nhau trong đồ thị.

Output: là file văn bản Output.pas

Liệt kê tất cả các chu trình Hamilton

MÔ HÌNH BÀI TOÁN (2) 1 5 4 2 3 Input.pas Output.pas 5 7 1 2 1 4 2 3 2 5 3 4 3 5 4 5 1 2 3 5 4 1 1 2 5 3 4 1 1 4 3 5 2 1 1 4 5 3 2 1

CÁC BƯỚC GIẢI QUYẾT BÀI TOÁN Gán đỉnh đầu tiên bằng 1 Thử các cách chọn đỉnh thứ i trong hành trình với i>=2 và i<=n. Chọn tất cả các đỉnh j để tìm đỉnh thứ i X[i] kề với X[i-1] và chưa bị đi qua Nếu tìm thấy đỉnh j thỏa mãn điều kiện trên thì gán X[i] = j . Nếu i < n thì Đánh dấu đỉnh j là đã đi qua để cho các bước tiếp theo không chọn j nữa. Sau đó chọn đỉnh thứ i+1 trong hành trình Thử phương án khác cho X[i] nên sẽ bỏ đánh dấu đỉnh vừa thử Ngược lại , nếu đã thử chọn đến X[n] thì kiểm tra nếu X[n] lại kề với X[1] thì ta có chu trình Hamilton.

Gán đỉnh đầu tiên bằng 1

Thử các cách chọn đỉnh thứ i trong hành trình với i>=2 và i<=n.

Chọn tất cả các đỉnh j để tìm đỉnh thứ i X[i] kề với X[i-1] và chưa bị đi qua

Nếu tìm thấy đỉnh j thỏa mãn điều kiện trên thì gán X[i] = j .

Nếu i < n thì

Đánh dấu đỉnh j là đã đi qua để cho các bước tiếp theo không chọn j nữa.

Sau đó chọn đỉnh thứ i+1 trong hành trình

Thử phương án khác cho X[i] nên sẽ bỏ đánh dấu đỉnh vừa thử

Ngược lại , nếu đã thử chọn đến X[n] thì kiểm tra nếu X[n] lại kề với X[1] thì ta có chu trình Hamilton.

THỦ TỤC MÔ TẢ THUẬT TOÁN procedure Try (i: Integer); var j: Integer; begin for j := 1 to n do if Mask[j] and A[X[i - 1], j] then begin X[i] := j; if i < n then begin Mask[j] := False; Try(i + 1); Mask[j] := True; end else if A[j, X[1]] then Print; end; end; Khai báo Const Max=50; Inputfilename=‘D:BPBININPUT.PAS’ Outputfilename=‘D:BPBINOUTPUT.PAS’ var ft: Text; A: array[1..max, 1..max] of Boolean; Mask: array[1..max] of Boolean; X: array[1..max] of Integer; n: Integer;

procedure Try (i: Integer);

var

j: Integer;

begin

for j := 1 to n do

if Mask[j] and A[X[i - 1], j] then

begin

X[i] := j;

if i < n then

begin

Mask[j] := False;

Try(i + 1);

Mask[j] := True;

end

else

if A[j, X[1]] then Print;

end;

end;

CÁC THỦ TỤC KHỞI TẠO (1) Nhập dữ liệu vào procedure Inputdata ; var i, u, v, m: Integer; fs: Text; begin Assign(fs, InputFilename); Reset(fs); FillChar(A, SizeOf(A), False); ReadLn(fs, n, m); for i := 1 to m do begin ReadLn(fs, u, v); a[u, v] := True; a[v, u] := True; end; Close(fs); end; In kết quả procedure Print; var i: Integer; begin for i := 1 to n do Write(ft, X[i], ' '); WriteLn(ft, X[1]); writeln; end;

Nhập dữ liệu vào

procedure Inputdata ;

var

i, u, v, m: Integer;

fs: Text;

begin

Assign(fs, InputFilename); Reset(fs);

FillChar(A, SizeOf(A), False);

ReadLn(fs, n, m);

for i := 1 to m do

begin

ReadLn(fs, u, v);

a[u, v] := True;

a[v, u] := True;

end;

Close(fs);

end;

CÁC THỦ TỤC KHỞI TẠO (2) Chương trình chính BEGIN Inputdata; FillChar(Mask, SizeOf(Mask), True); X[1] := 1; Mask[1] := False; Assign(ft, Outputfilename); Rewrite(ft); Try(2); Close(ft); readln; END.

Chương trình chính

BEGIN

Inputdata;

FillChar(Mask, SizeOf(Mask), True);

X[1] := 1; Mask[1] := False;

Assign(ft, Outputfilename); Rewrite(ft);

Try(2);

Close(ft);

readln;

END.

THỜI GIAN THỰC HIỆN T(n) = O(n*m) trong đó n là số đỉnh và m là số cạnh giữa các đỉnh 1 5 4 2 3 3 1 2 4 5 3 2 1 3 1 2 3 5 2 1 5 1 2 5 4 1 3 3 4 1 1 5 4 5 1 4 Đồ thị có 5 đỉnh và 7 cạnh Cây liệt kê chu trình Hamilton của đồ thị theo thuật toán quay lui

Add a comment

Related presentations

Related pages

Đường đi Hamilton – Wikipedia tiếng Việt

Chu trình x 0,x 1,...,x n,x 0 là chu trình Hamilton nếu x 0,x 1,...,x n,x 0 là đường đi Hamilton. ... Quy tắc để tìm chu trình Hamilton ...
Read more

[C++] Tìm 1 chu trình Hamilton | 朱漢輝 (Trần ...

Hãy tìm Một chu trình Hamilton Lý thuyết CHU TRÌNH ... Đoạn code dưới sử dụng thuật toán đệ qui quay lùi; Ý tượng tìm 1 chu ...
Read more

[C++] Tìm tất cả chu trình Hamilton | 朱漢輝 ...

Hãy tìm Tất cả chu trình Hamilton; Lý thuyết. CHU TRÌNH ... sử dụng thuật toán đệ qui quay lùi; Ý tượng tìm 1 chu trình ...
Read more

Tìm chu trình Euler và Hamilton (Ph n 2)

Tìm chu trình Euler và ... cout<<"Khong tim thay chu trinh Hamilton"; ... Hãy khử đệ quy cho đoạn chương trình trên bằng kỹ ...
Read more

Tìm chu trình Euler, chu trình Hamilton

cout<<"Chu trinh Euler nhu sau:"; for (int k=0; k<nCE; k++) ... Nội quy - Quy định. Liên lạc với chúng tôi; Lưu trữ; Lên trên; Múi ...
Read more

Đường đi Euler – Wikipedia tiếng Việt

... ("nKhong co chu trinh Eulern"); fclose(g); return; } printf("nDo thi co chu trinh Eulern"); int k,ok; // kiem tra va in ra man hinh ...
Read more

Quy trình viết chữ hoa Ă nét nghiêng - How to ...

Quy trình viết chữ hoa Ă nét nghiêng ... Tat ca cac chu cai Chu hoa kieu nghieng Luyen viet chu dep - Duration: 13:56.
Read more

Chương 7: Chu trình euler và chu trình hamilton ...

Chu trình Euler và chu trình Hamilton là hai loại chu trình rất nổi tiếng trong Lý thuyết ... Quy định bảo mật; Thỏa thuận sử ...
Read more

LTĐT: Tìm chu trình Euler, chu trình Hamilton - Quoc ...

Nghiên cứu thường được mô tả là một quy trình tìm hiểu tích cực, ... Cac chu trinh Hamiltom co: 1 2 3 5 4 1.
Read more