30/09/2018, 22:48
Thuật toán về đường đi Hamilton
Tim đường đi Hamilton ngắn nhất qua tất cả các đỉnh mỗi đỉnh 1 lần bằng thuật toán QHĐ độ phức tạp là 2^n*n^2 thì phải làm thế nào mọi người nhỉ?
Bài liên quan
gọi 1 trạng thái s là 010001, với bit 1 biểu diễn các thành phố đã thăm. Khi đó quy hoạch động dp[s][i] là đường đi ngắn nhất với trạng thái s, thành phố cuối cùng thăm là i, vậy dp[s][i] sẽ tính bằng các dp[s’][j] với s’ là trạng thái s với bỏ bit i đi (000001), j là 1 trong các bit bằng 1 của s’. Nếu bạn đã quen với qhđ trạng thái thì sẽ rất dễ hiểu, không thì mình cũng ko biết giải thích thế nào dễ hiểu hơn nữa