請問要如何使用動態規劃演算法來解推銷員旅行問題? |
|
缺席
|
|
kururu2006
一般會員   發表：9 回覆：2 積分：2 註冊：2006-12-04 發送簡訊給我 |
請問高手要如何用C++寫法，使用Dynamic Programming 來解推銷員旅行問題?
完成的部份 [code cpp] #include #include #include using namespace std; int main(void) { int in_data[20][20] = {0},i,j,x,y; srand(time(0)); //決定亂數種子 //產生矩陣 for(i=0;i<=19;i ) { for(j=0;j<=19;j ) { in_data[i][j] = rand() 1; //用亂數決定數值 cout << "in_data[" << i << "]" << "[" << j << "]=" << in_data[i][j] << endl; } } system("pause"); return 0; } [/code] 找到的範例演算法 [code cpp] int dd(int i, int j) { return 地點i到地點j的距離; } void TSP(int d, int now, int mask) { if (d == N) { if (dp[now][mask] dd(now, 0) < ans) ans = dp[now][mask] dd(now, 0); return; } for (int i=1, mm=1; i<=N; i, mm<<=1) if (!(mask & mm)) if (!dp[i][mask | mm] || dp[now][mask] dd(now, i) < dp[i][mask | mm]) { dp[i][mask | mm] = dp[now][mask] dd(now, i); TSP(d 1, i, mask | mm); } } [/code] 我已經寫出隨機亂數產生20個點之間距離的相鄰矩陣,要如何將找到的範例演算法轉變成可用於我已完成程式的部分,並用動態規劃找出最短路徑且記憶和列印路徑. 煩請各位高手解答,因為我已經在網路上找了很久並無發現夠完整的範例或解答,希望各位高手能解決我的疑惑,謝謝. P.S:我的編譯器版本是 Dev C Ver 4.9.8.0 編輯記錄
taishyang 重新編輯於 2007-12-14 19:05:39， 註解 將[求救]字樣拿掉‧
|
|
syntax
尊榮會員  發表：26 回覆：1139 積分：1258 註冊：2002-04-23 發送簡訊給我 |
接下來你要
1. 規劃一個 table 來記錄所有的可能性 2. 設計演算法來使用該 table，即是： 計算所以的可能性，並記錄一個 tag find the path with the table you just computed, and use the tag to detemine next node 至於如設計演算法，請參考書上範例，並試著去做 ===================引 用 kururu2006 文 章=================== 請問高手要如何用C 寫法，使用Dynamic Programming 來解推銷員旅行問題? 完成的部份 [code cpp] #include #include #include using namespace std; int main(void) { int in_data[20][20] = {0},i,j,x,y; srand(time(0)); //決定亂數種子 //產生矩陣 for(i=0;i<=19;i ) { for(j=0;j<=19;j ) { in_data[i][j] = rand() 1; //用亂數決定數值 cout << "in_data[" << i << "]" << "[" << j << "]=" << in_data[i][j] << endl; } } system("pause"); return 0; } [/code] 找到的範例演算法 [code cpp] int dd(int i, int j) { return 地點i到地點j的距離; } void TSP(int d, int now, int mask) { if (d == N) { if (dp[now][mask] dd(now, 0) < ans) ans = dp[now][mask] dd(now, 0); return; } for (int i=1, mm=1; i<=N; i, mm<<=1) if (!(mask & mm)) if (!dp[i][mask | mm] || dp[now][mask] dd(now, i) < dp[i][mask | mm]) { dp[i][mask | mm] = dp[now][mask] dd(now, i); TSP(d 1, i, mask | mm); } } [/code] 我已經寫出隨機亂數產生20個點之間距離的相鄰矩陣,要如何將找到的範例演算法轉變成可用於我已完成程式的部分,並用動態規劃找出最短路徑且記憶和列印路徑. 煩請各位高手解答,因為我已經在網路上找了很久並無發現夠完整的範例或解答,希望各位高手能解決我的疑惑,謝謝. P.S:我的編譯器版本是 Dev C Ver 4.9.8.0 |
|
kururu2006
一般會員 發表：9 回覆：2 積分：2 註冊：2006-12-04 發送簡訊給我 |
|
|
kururu2006
一般會員 發表：9 回覆：2 積分：2 註冊：2006-12-04 發送簡訊給我 |
===================引 用 syntax 文 章=================== 接下來你要 1. 規劃一個 table 來記錄所有的可能性 2. 設計演算法來使用該 table，即是： 計算所以的可能性，並記錄一個 tag find the path with the table you just computed, and use the tag to detemine next node 至於如設計演算法，請參考書上範例，並試著去做 ===================引 用 kururu2006 文 章=================== 請問高手要如何用C 寫法，使用Dynamic Programming 來解推銷員旅行問題? 完成的部份 [code cpp] #include #include #include using namespace std; int main(void) { int in_data[20][20] = {0},i,j,x,y; srand(time(0)); //決定亂數種子 //產生矩陣 for(i=0;i<=19;i ) { for(j=0;j<=19;j ) { in_data[i][j] = rand() 1; //用亂數決定數值 cout << "in_data[" << i << "]" << "[" << j << "]=" << in_data[i][j] << endl; } } system("pause"); return 0; } [/code] 找到的範例演算法 [code cpp] int dd(int i, int j) { return 地點i到地點j的距離; } void TSP(int d, int now, int mask) { if (d == N) { if (dp[now][mask] dd(now, 0) < ans) ans = dp[now][mask] dd(now, 0); return; } for (int i=1, mm=1; i<=N; i, mm<<=1) if (!(mask & mm)) if (!dp[i][mask | mm] || dp[now][mask] dd(now, i) < dp[i][mask | mm]) { dp[i][mask | mm] = dp[now][mask] dd(now, i); TSP(d 1, i, mask | mm); } } [/code] 我已經寫出隨機亂數產生20個點之間距離的相鄰矩陣,要如何將找到的範例演算法轉變成可用於我已完成程式的部分,並用動態規劃找出最短路徑且記憶和列印路徑. 煩請各位高手解答,因為我已經在網路上找了很久並無發現夠完整的範例或解答,希望各位高手能解決我的疑惑,謝謝. P.S:我的編譯器版本是 Dev C Ver 4.9.8.0 我的意思就是要將兩段程式碼結合且能正確執行才算是問題的正確解答. |
發表時間：2007-12-12 21:05:12
IP:218.175.xxx.xxx 訂閱
系統時間：2024-04-26 0:23:38
聯絡我們 | Delphi K.Top討論版
| 本站聲明 |
|
1. 本論壇為無營利行為之開放平台，所有文章都是由網友自行張貼，如牽涉到法律糾紛一切與本站無關。 2. 假如網友發表之內容涉及侵權，而損及您的利益，請立即通知版主刪除。 3. 請勿批評中華民國元首及政府或批評各政黨，是藍是綠本站無權干涉，但這裡不是政治性論壇！ |