推 FRAXIS: 這問題跟 TSP 應該是等價的吧 所以 greedy 應該不 work.. 07/25 22:37
我認為是不等價的，
TSP 中 af 距離為 sqrt(2)
而在此題中 af = ab + bf = 2
觀念若有錯請多包涵
※ 編輯: noodleT (39.12.195.169), 07/25/2016 22:55:35
推 FRAXIS: TSP 中的 edge weight 是輸入的一部分 07/25 23:03
→ FRAXIS: 你想的 TSP 是 edge weight 被設定為 Euclidean distance 07/25 23:03
→ FRAXIS: 所以只是 TSP 的特例而已.. 07/25 23:03
推 FRAXIS: 不過這題的圖是定死的 而且是 grid 的 subgraph 07/25 23:05
→ FRAXIS: 所以應該有比較快的方法作吧 07/25 23:06
推 DJWS: 運氣好 07/26 06:52
推 FRAXIS: 我查了一下 TSP 在 grid graph 中還是 NPC 的 07/26 11:49
→ FRAXIS: HAMILTON PATHS IN GRID GRAPHS 論文 title 07/26 11:49
→ FRAXIS: 不過如果 grid graph 上面沒有洞的話是多項式可解的 07/26 11:50
→ noodleT: 在這張圖上有什麼例子是貪婪解不出來的？ 07/26 12:15
→ noodleT: 看很久沒看出來 07/26 12:16
推 yvb: 從 n 出發, 須拜訪 a, b, f, j, p. 07/26 14:07
→ noodleT: 謝謝樓上，我再想想其他解法 07/26 19:57
→ FRAXIS: 應該就 backtracking 吧 07/26 21:38
目前利用一張表來儲存子問題(應該是屬於動態規劃解)，但效果不彰。
從 a 出發把所有點走一遍需要跑 30 秒左右(答案 15?)
unsigned SortestVisitWithBacktracking
(char begin,const std::vector<char> &visit)const
{
//map<pair<起點,拜訪點向量>,最小路徑>
static std::map<std::pair<char,std::vector<char> >,unsigned> table;
//...
}
在思考是不是需要改成
unsigned SortestVisitWithBacktracking
(char begin,const std::vector<char> &visit,unsigned 剩餘步數限制)const
利用貪婪求一開始的剩餘步數限制，
然後每次遞迴都更新(縮小)剩餘步數限制
※ 編輯: noodleT (110.28.205.127), 07/28/2016 00:00:13
推 FRAXIS: 應該是要的吧 不然你的方法就等同產生所有排列了.. 07/28 09:16
推 DJWS: TSP可以用動態規劃解 時間從O(n!)變O(2^n * n) 快了很多 07/28 22:00
→ DJWS: O(2^n * n^2) 07/28 22:04
→ noodleT: 加入限制條件後就快多了 08/01 16:38
推 FRAXIS: 你還可以嘗試 A star 08/01 21:01
→ noodleT: 好的 08/01 21:17
→ noodleT: a start 似乎沒有保證最佳解 08/06 21:48
推 FRAXIS: A* 如果你 heuristic 設計的對是保證會有最佳解的.. 08/06 22:02
推 DJWS: 這題的heuristic要怎麼設計？我是第一次聽說這種題目可以A* 08/10 07:06
推 FRAXIS: 要設計不難啊 有沒有用又是另外一回事.. 08/10 08:02
→ FRAXIS: MST 的 cost 應該可以當 heuristic 吧 08/10 08:03
推 DJWS: 是可以，不過總共得算多少次MST呢? 08/10 21:43