Thuật Toán Hamilton

[Khoa_Thanh (Khoa Thành)]

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("\n-----Chu trinh Hamilton-----------\n");
            x[k] = v0;
            InKetQua(n + 1);
        }
        else
        {
            printf("\n-----Duong di Hamilton----------\n");
            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;
            }
}

[ltd (Lê Trần Đạt)]

Gửi cả code lên @Khoa_Thanh ơi, dùng markdown để post code nhé

Cách post Code dùng Markdown trong Category Programming

Làm sao để có thể hiển thị syntax highlighting bằng markdown? Các bạn phải đánh dấu ``` như ví dụ dưới đây Chú ý, dấu ``` được tạo ra bởi nút nằm bên trái số 1 trên bàn phím, nút này sẽ là ~ khi bấm giữ Shift Ví dụ cho C Nội dung: ``` void main() { } ``` Và đừng quên ``` ở cuối Kết quả void main() { } Ví dụ cho Pascal Nội dung: ``` Program HelloWorld; Begin WriteLn('Hello world!') {no ";" is required after the last statement of a block - adding one adds a "null stateme…

[Khoa_Thanh (Khoa Thà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

[ltd (Lê Trần Đạt)]

biến k thì 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 đương a[z][i]

• z là x[k-1]

Vậy x[k-1] trả về một số kiểu int và đó là vị trí nằm tỏng mảng a

Anh chỉ có thể giải thích đến thế, hi vọng giúp được em.

[Honey_moon (Thực tế khắc nghiệt)]

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!

[Gio (Gió)]

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(!)

[Khoa_Thanh (Khoa Thành)]

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

[Thuc_Nguyen_tan]

Đâ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/