Re: [算表] excel最短路徑變數? (旅行商問題-TSP)

看板Office作者JieJuen (David)時間17年前 (2008/07/18 02:25)推噓0(0推 0噓 2→)

留言2則, 2人參與討論串1/1

第一個要說的就是：這是"旅行商問題" traveling salesman problem (tsp) 與最短路徑問題不同。先解答： http://i.am.ntu.googlepages.com/tsp.rar 您可以google找找有沒有規劃求解直接的作法，我沒找到。上面檔案中，有兩個作法第一是用循環參照，亂數配答案作法，(tsp_rand.xls) 數目一多可能就不是最佳解，但此法較容易做到。第二是用以下網站的增益集 http://www.me.utexas.edu/~jensen/ORMM/models/unit/combinatorics/tsp.html 在tsp.rar中， tsp_rand.xls 也回答了原文的問題：把變數放到儲存格中，下一步扣除前面用過的但是此法的規劃求解求不出來，說不定您可以試出來? tsp_shortpath.xls 為規劃求解失敗的一些方法網上有篇文章用類似最短路徑的方法解此問題， http://www.math.org.cn/forums/index.php?showtopic=15316 但似乎考慮欠周，會造成答案可能是兩個路徑如 1 2 一圈 3 4 5 一圈加起距離的確很少但那是兩條沒連在一起的路 Excelhome有一些討論，關於最短路徑 http://club.excelhome.net/dispbbs.asp?boardID=3&ID=330925 比旅行商問題容易許多 Excel規劃求解官方網站對於tsp的解法 http://www.solver.com/xlsplatform4.htm 用加強版規劃求解以得到"alldifferent" constraint 要錢吧. http://episte.math.ntu.edu.tw/articles/mm/mm_10_2_04/ "你的問題是「NP-hard」" "NP-hard 不但代表 hard（難），而且是 NP 的難！" ※ 引述《myson (就是要守著你)》之銘言： : 軟體:excel : 版本:2003 : 地點 1 2 3 4 5 : 1 0 10 15 20 40 : 2 10 0 12 16 24 : 3 15 12 0 10 20 : 4 20 16 10 0 16 : 5 40 24 20 16 0 : 規劃求解 : 地點1是起始點，到2,3,4,5各一次之後，再回到1 過程加總的值會是最少的 : 例如:一開始選擇到2,3,4,5其中之一，然後從2開始到3,4,5的距離去選 : 最後再加上回1的距離 : 問題是：怎麼設定讓一開始四個變數值放入某個限制式或儲存格{2,3,4,5} : 然後去加上第二次選擇的值，讓變數扣除第一次的選項剩下{3,4,5}or{2,4,5}進儲存格 : 或是能教學一下怎麼設定限制式@@? : 感謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.171.33.145

Re: [算表] excel最短路徑 變數? (旅行商問題-TSP)

Re: [算表] excel最短路徑變數? (旅行商問題-TSP)