Wikipedia

Khác biệt giữa bản sửa đổi của “Đường đi Hamilton”

Duyệt lịch sử tương tác
← Thay đổi trướcThay đổi sau →
Nội dung được xóa Nội dung được thêm vào
Trực quanMã wiki
Không có tóm lược sửa đổi
n Đã hủy sửa đổi của Tranphuongduy (Thảo luận) quay về phiên bản của TuanUt
Dòng 1:
{{wikify}}
{{cần biên tập|trình bày quá màu mè}}
'''Đường đi Hamilton''' có nguồn gốc từ bài toán: "Xuất phát từ một đỉnh của [[khối thập nhị diện đều]] hãy đi dọc theo các cạnh của khối đó sao cho đi qua tất cả các đỉnh khác, mỗi đỉnh đúng một lần sau đó quay về đỉnh xuất phát." là gọi theo tên của [[William Rowan Hamilton]] phát biểu vào năm 1859.
 
[[Tập tin:Dodecahedron.gif|lớn|khung|300px|giữanhỏ|Khối thập nhị diện đều]]
'''[[Tập tin:220px-Hamiltonian path.png |nhỏ|Đường đi Hamilton (Đáp án bài toán Hamilton ở trên)''']]
[[Tập tin:220px-Hamiltonian path.png |lớn|khung|300px|giữa|Đường đi Hamilton]]
==Định nghĩa==
Cho đồ thị G = (V,E), có n đỉnh
Hàng 57 ⟶ 58:
 
*Giả sử '''G=(X,E)''' là [[đồ thị vô hướng]] gồm n đỉnh với tập đỉnh '''X={x<sub>1</sub>,x<sub>2</sub>,...,x<sub>n</sub>}''', nếu G là đồ thị Hamilton thì sẽ có chu trình Hamilton có dạng: '''x<sub>1</sub>--x<sub>i1</sub>--x<sub>i2</sub>--x<sub>i3</sub>... x<sub>i n-1</sub>--x<sub>1</sub>''',với '''{i<sub>1</sub>,i<sub>2</sub>,...,i<sub>n-1</sub>}''' là một hoán vị của tập hợp '''{2,3,...,n}'''
==> Từ đó, ta có một thuật toán hiển nhiên là: Đặt '''Z={x<sub>i1</sub>, x<sub>i2</sub>, x<sub>i3</sub>,…}''' là dãy đỉnh tương ứng
trong hoán vị của tập '''{2,3,…n}'''ta kiểm tra xem Z có tạo nên chu trình hay không, tức là phải kiểm tra '''(n-1)!''' tập (Z) khác nhau.
 
==> Đây là một [[thuật toán vét cạn]], có độ phức tạp không khả thi khi n chỉ từ 20,30 đỉnh trở lên.
 
*Cho đến nay, việc nghiên cứu tìm ra thuật toán hiệu quả, xác định xem một đồ thị Hamilton hay không vẫn đang là một thách thức lớn đối với các nhà toán học và tin học.
Hàng 67 ⟶ 68:
 
*Những thuật toán loại này khá nhanh và thông thường dừng với hai trường hợp sau:
1. Nếu khẳng định đồ thị đang xét là đồ thị Hamilton là đó là một khẳng định chính xác và có thể kiểm chứng dễ dàng.
2. Nếu khẳng định định không phải là đồ thị Hamilton: có thể bị sai lầm với một xác xuất nào đó(thật ra trường hợp này chính là "Không biết đồ thị đã cho có phải là đồ thị Hamilton không").
 
==Qui tắc để tìm chu trình Hamilton==
Hàng 86 ⟶ 87:
 
Quy tắc 3 được minh họa trong hình,khi thực hiện qui tắc này thì bậc của một số đỉnh bị giảm xuống : nhờ vậy chúng ta có thể tận dụng trở lại qui tắc 1 và qui tắc 4.
== Áp dụng 4 quy tắc tìm đường đi Hamilton ==
'''Bài toán: Tìm chu trình Hamilton trong đồ thị sau:'''
[[Tập tin:VdBaiToan1.png|lớn|400x|giữa|Đồ thị]]
'''BÀI GIẢI:'''
Tại đỉnh 1, chỉ có thể 2 trong 5 cạnh kề với đỉnh 1, do tính chất đối xứng của đồ thị ta chỉ cần xét hai trường hợp:
-Lấy 1---2 và 1---6
-Lấy 1---2 và 1---4
Nếu 1 trong 2 trường hợp mà tìm được chu trình Hamilton thì dừng và không cần xét trường hợp còn lại, nếu cả 2 trường hợp đều không tìm được chu trình Hamilton thì kết luận đồ thị không phải là đồ thị Hamilton.</br>
* '''Bây giờ giả sử lấy 1---2 và 1---6:'''
-Theo quy tắc 3, có thể xóa cạnh 1---3, 1---4 và 1---5
[[Tập tin:VdBaiToan2.png|lớn|400x|giữa|Hình 1]]
-Các đỉnh 3, 4, 5 trở thành bậc 2: ta lấy them được 6 cạnh kề với chúng.
[[Tập tin:VdBaiToan3.png|lớn|400x|giữa|Hình 2]]
-Theo quy tắc 3, có thể xóa cạnh: 10---9, 10---11
[[Tập tin:VdBaiToan4.png|lớn|400x|giữa|Hình 3]]
-Lấy 7---8 sẽ tạo chu trình(chỉ có 5 cạnh): ta xóa cạnh này theo quy tắc 2.
[[Tập tin:VdBaiToan5.png|lớn|400x|giữa|Hình 4]]
- Nếu lấy cả 7---11 và 8---9 thì tạo chu trình chư đủ cạnh, theo quy tắc 2 thì chỉ lấy 1 trong 2 cạnh này, do tính
đối xứng ta lấy 8---9 và bỏ 7---11
[[Tập tin:VdBaiToan6.png|lớn|400x|giữa|Hình 5]]
-Theo quy tắc 3: bỏ 8---6, 9---2
[[Tập tin:VdBaiToan7.png|lớn|400x|giữa|Hình 6]]
-Bắt buộc phải lấy 2---7 và 6---11: đã tìm được chu trình Hamilton.
[[Tập tin:VdBaiToan8.png|lớn|400x|giữa|Hình 7]]
</br>
'''==> Kết luận: đồ thị đang xét là đồ thị Hamilton.'''
 
==Cài đặt chương trình tìm đường đi Hamilton==
Bài toán: Cho một đồ thị n đỉnh hãy tìm chu trình Hamilton từ 1 đỉnh sao cho tổng trọng số đi từ đỉnh đó là nhỏ nhất (3=<n<=10)
//Khai báo
#define MAX 100
struct GRAPH // ma trận kề
{
int n;
int L[MAX][MAX];
};
int flag_trongso=0;// cờ giữ trọng số đang giữ nhỏ nhất
int flag_duongdi[MAX];// lưu giữ đường đi hiện tại với trọng số nhỏ nhất
int danhdau[MAX];// mảng lưu các đỉnh đã được đánh dấu
int duongdi[MAX];// lưu đường đi đang xét
 
 
//Hàm đọc ma trận từ file input.txt
void DocMaTranKe(GRAPH &g)
{
int i;
int j;
FILE* f;
f = fopen("input.txt","rt");
if(f == NULL)
{
printf("\nKhong mo duoc file");
return;
}
fscanf(f,"%d",&g.n);
for(i = 0; i < g.n; i++)
{
for(j = 0; j < g.n; j++)
{
fscanf(f,"%d",&g.L[i][j]);
flag_trongso+=g.L[i][j];//Gán cho trọng số 1 con số ảo lớn
}
}
fclose(f);
}
 
 
 
//Hàm Hamilton sử dụng phuơng pháp quay lui để tính tất cả các đường xuất phát từ 1 đỉnh
void Hamilton(int lan,int x,GRAPH g,int dinhbatdau)
{
if(lan>g.n && g.L[x][dinhbatdau])
{
printf(".");
int ts = TinhTrongSo(g);
if(ts<flag_trongso)
{
flag_trongso=ts;
LuuDuongDiNganNhatNow(g);
}
return;
}
for(int i=1;i<=g.n;i++)
{
if(g.L[x-1][i-1]!=0 && XetDanhDau(i,g)==1)
{
duongdi[lan]=i;
danhdau[lan]=i;
Hamilton(lan+1,i,g,dinhbatdau);
BoDanhDau(i,g);
}
}
}
 
 
 
//Hàm main
void main()
{
GRAPH g;
DocMaTranKe(g);
Init(g);
int x;
do
{
printf("Nhap dinh bat dau: ");
scanf("%d",&x);
} while (x>g.n);
danhdau[1]=x; duongdi[1]=x;
Hamilton(2,x,g,x);
printf("\nDuong di ngan nhat tu dinh %d la: \n",x);
ShowPath(g);
printf("Voi trong so nho nhat la: %d",flag_trongso);
getch();
}
 
 
//Các hàm nhỏ liên quan
void Init(GRAPH g)
{
for(int i=0;i<=g.n;i++)
danhdau[i]=-1;
}
int TinhTrongSo(GRAPH g)
{
int tong=0;
int i=1;
while(i<g.n)
{
int i1 = duongdi[i];
int i2 = duongdi[i+1];
tong+=g.L[i1-1][i2-1];
i++;
}
int dinhbatdau = duongdi[1];
int dinhketthuc = duongdi[g.n];
tong+=g.L[dinhketthuc-1][dinhbatdau-1];
return tong;
}
int XetDanhDau(int dinhxet,GRAPH g)
{
for(int i=1;i<=g.n;i++)
{
if(danhdau[i]==dinhxet)
return 0;
}
return 1;
}
void BoDanhDau(int dinhxet,GRAPH g)
{
for(int i=0;i<=g.n;i++)
if(danhdau[i]==dinhxet)
danhdau[i]=-1;
}
void ShowPath(GRAPH g)
{
for(int i=1;i<=g.n;i++)
printf("-%d-",flag_duongdi[i]);
printf("\n");
}
 
'''Cho một file "input.txt"''' có nội dung như sau:
9
978 1281 1129 1288 534 1002 1086 516 1077
1281 834 1111 761 821 1490 799 1296 1320
1129 1111 1998 1152 621 1543 1475 1139 597
1288 761 1152 312 1081 1374 398 885 1247
534 821 621 1081 768 925 676 989 1335
1002 1490 1543 1374 925 1168 419 1544 1847
1086 799 1475 398 676 419 322 211 953
516 1296 1139 885 989 1544 211 136 644
1077 1320 597 1247 1335 1847 953 644 210
 
'''Kết quả đường đi có trọng số nhỏ nhất xuất phát từ đỉnh 1 có chu trình Hamilton là: '''
1 -> 6 -> 4 -> 2 -> 5 -> 3 -> 9 -> 8
Với trọng tổng trọng số là: 5779
==Ứng dụng==
Bài toán mã đi tuần là một dạng của bài toán tổng quát hơn là bài toán tìm [[đường đi Hamilton]] trong [[l‎ý thuyết đồ thị]], là một bài toán [[NP-đầy đủ]]. Bài toán tìm hành trình đóng của quân mã là một bài toán cụ thể của bài toán tìm [[chu trình Hamiltonian]].
Lấy từ “https://vi.wikipedia.org/wiki/Đường_đi_Hamilton”