30/09/2018, 16:11
Thuật Toán Hamilton
Mình có đoạn code mình lấy trong sách nhưng mình không hiểu biến k ở đây là gì?
Thêm nữa, a[x[k-1]][i] có nghĩa là gì?
Đây là code
void hamilton(int k)
{
int y;
if (k==n)
{
if(a[x[k-1]][v0] >0)
{
printf("
-----Chu trinh Hamilton-----------
");
x[k] = v0;
InKetQua(n + 1);
}
else
{
printf("
-----Duong di Hamilton----------
");
InKetQua(n);
}
}
else if (k < n)
for (y=1; y <= n; y++)
if (a[x[k-1]][y]>0 && chuaxet[y]==0)
{
x[k] = y;
chuaxet[y] =-1;
hamilton(k+1);
chuaxet[y]=0;
}
}
Bài liên quan
Gửi cả code lên @Khoa_Thanh ơi, dùng markdown để post code nhé
Sách nó ghi như vậy thôi anh Đạt. Nên em củng không biết k là gì là số đỉnh hay value đang xét, chỉ mong có bạn nào từng biết hàm hamilton cho mình biết k mang ý gì và a[x[k-1]][i] là gì. Em xin hết
biến
kthì anh thua, vì cái này liên quan đến thuật toán.a[x[k-1]][i]ta có thể phân tích tương đươnga[z][i]zlàx[k-1]Vậy x[k-1] trả về một số kiểu
intvà đó là vị trí nằm tỏng mảngaAnh chỉ có thể giải thích đến thế, hi vọng giúp được em.
Nếu a Đạt giải thích chỗ đó thì coi như xong rồi! có mỗi chỗ đó khó hiểu còn lại thì đơn giản!
Hamiton là đường đi qua tất cả các đỉnh.
Như hàm trên bạn viết hàm hamilton(int k) sẽ nhận k từ 0-n theo kiểu quay lui.
k=0, nó sẽ nhận bất kì cạnh nào.
k=1, nó sẽ nhận x[k] thuộc chuaxet[…] tức là các đỉnh còn lại nếu có đường đi từ x[k=0]
lặp lại cho đến k=n.
theo mình thấy nếu đồ thị có tất cả các cạnh nối 2 điinh thì x[] sẽ nhận tất cả các hoán vị của n(!)
Vậy ý anh Đạt muốn nói là nếu em gọi hàng 1 chẳng hạn x[1]. Vậy nó sẽ trả ra là 5 và mình thế vào a[x[k-1]][i] = a[5][0]( với i=0 vòng for đầu tiên chẳng hạn)? có phải vậy không anh?
0 5 4
5 0 1
4 1 0
Đây là hàm trong bài tìm đường đi hamilton, với k là một đỉnh của đồ thị, x là matran kề.
Kết quả của hàm đệ qui này là sẽ trả về tất cả các đường đi Hamilton theo thuật toán vét cạn, quay lui.
thân.
http://vibigaba.esy.es/