2012-10-06 13:43:07Morris
旅行業務員問題 TSP － DP狀態壓縮做法
int g[20][20], dp[1<<20][20], t2[1<<20];
void tsp(int state, int last) {
if(dp[state][last] != oo) return;
int i, j, tmp;
dp[state][last]--; /*取代 used[state][last]*/
for(i = state; i; i -= j) {
j = i&(-i);
tsp(state-j, t2[j]);
tmp = dp[state-j][t2[j]]+g[t2[j]][last];
dp[state][last] = min(dp[state][last], tmp);
}
}
我們將要走過的 n 個節點轉換成 (11...111) 的狀態, 並且記錄最後停留的位置。
g[i][j] 裡面存放 i->j 的距離
t2[i] 裡面存放 i = 2^x 的 x
dp[state][last] 存放已經走過 state 的狀態, 最後停留的位置
for(i = 1<<n; i >= 0; i--)
for(j = 0; j < n; j++)
dp[i][j] = oo;
dp[0][0] = 0;
tsp((1<<nut)-1, 0);
接下來是初始化的部分, 如上述。記得要將點轉換成 0~ n-1 的編號
dp[(1<<nut)-1][0] // 答案
延伸作法 :
為何不用用 A* Algorithm ? 如果距離差別很大的話, 會加速很多, 不過相對的就不好寫。
H() 的估算, 這裡提供一個 H() = (其中尚未走過的點到0的最短距離)+尚未走過的點個數。
但是丟 heap 的時候, 由於無法判重可能會吃多餘的記憶體堆積在其中。
void tsp(int state, int last) {
if(dp[state][last] != oo) return;
int i, j, tmp;
dp[state][last]--; /*取代 used[state][last]*/
for(i = state; i; i -= j) {
j = i&(-i);
tsp(state-j, t2[j]);
tmp = dp[state-j][t2[j]]+g[t2[j]][last];
dp[state][last] = min(dp[state][last], tmp);
}
}
我們將要走過的 n 個節點轉換成 (11...111) 的狀態, 並且記錄最後停留的位置。
g[i][j] 裡面存放 i->j 的距離
t2[i] 裡面存放 i = 2^x 的 x
dp[state][last] 存放已經走過 state 的狀態, 最後停留的位置
for(i = 1<<n; i >= 0; i--)
for(j = 0; j < n; j++)
dp[i][j] = oo;
dp[0][0] = 0;
tsp((1<<nut)-1, 0);
接下來是初始化的部分, 如上述。記得要將點轉換成 0~ n-1 的編號
dp[(1<<nut)-1][0] // 答案
延伸作法 :
為何不用用 A* Algorithm ? 如果距離差別很大的話, 會加速很多, 不過相對的就不好寫。
H() 的估算, 這裡提供一個 H() = (其中尚未走過的點到0的最短距離)+尚未走過的點個數。
但是丟 heap 的時候, 由於無法判重可能會吃多餘的記憶體堆積在其中。