|
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.
==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]].
| 