為什麼這篇tsp解法鄉民發文收入到精華區：因為在tsp解法這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者JieJuen (David)看板Office標題Re: [算表] excel最短路徑 變數?...
tsp解法 在 ANDY DARK Instagram 的精選貼文
2021-09-15 21:21:30
【意式芝士焗燒賣 Easy Siu Mai Casserole】 前幾日分享咗一道「#冰花煎燒賣」俾大家，好多人都同我講覺得好簡單易做，的確係宵夜佐酒之選！ 而今天就再將我YouTube嘅《#店煮》系列中嘅另一道燒賣菜式 — 「#意式芝士焗燒賣」嘅食譜俾埋你哋～ 6號 (@maubolung)同...
第一個要說的就是：
這是"旅行商問題" 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
→ mddc62:印象中沒錯的話 工業工程類的專業軟體應該有解 07/18 07:30
→ JieJuen:^^ 增益集開發者對能免費讓excel可算此問題感到十分自豪 07/20 04:27