島嶼渡假↘下殺$4900起女大生禁不起誘惑!按了..正妹的東京自助旅行破戒!比丘吃葷 連3次...
2012-10-06 13:43:07 人氣(737) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

旅行業務員問題 TSP - DP狀態壓縮做法

0
收藏
0
推薦

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 的時候, 由於無法判重可能會吃多餘的記憶體堆積在其中。



TSPDP狀態壓縮
台長:Morris
人氣(737) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 各類演算法與示範題目 |
此分類下一篇:[資料結構][作業] Heap Sort
此分類上一篇:Segment Tree,二維線段樹版本,zkw式

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文