作者stool100 (思念是毒妳是解藥)
看板CodeJob
標題[發案] 最短漢米爾頓路徑(Hamilton path)演算法
時間Thu Feb 14 10:05:07 2008
狀態: 已發包
發案人: Kevin Lai
聯絡方式1: MSN :
[email protected]
聯絡方式2: 站內信聯繫
有效時間: 徵到為止
專案類型: 演算法
專案說明:
請教是否有高人可以協助最佳路徑的演算法
條件是 平面上 N 個點
每一點都必須拜訪
不需考慮交叉線或是轉角
也不用回到原點
只需要最短路徑
希望是簡單快速的演算法
不需嚴謹到絕對最短路徑
虛擬碼含說明即可.
不需程式.
技術需求: 演算法
預算: 歡迎報價
接案者要求: 北部
附註:
結案意見: (結案後自由填寫,可以詢問接案人願不願意暴光接案身份)
接案人:
說明: 目前進行中
--
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.116.6.19
※ 編輯: stool100 來自: 122.116.6.19 (02/14 10:06)
1F：推 uqljnro:最小生成樹 02/14 11:51
2F：推 yoco315:推最小生成樹 02/14 12:48
3F：推 tkcn:我倒覺得直接用 BB 找到一定階段，效果可能會比較好 02/14 15:32
4F：推 revivalworld:google Prim or Dijkstra 02/14 19:53
5F：推 tkcn:不懂MST跟最短路徑有啥關係..找出來的path有一堆edge要走兩次 02/14 21:19
※ 編輯: stool100 來自: 122.116.6.19 (02/14 21:25)
6F：推 cole945:推 tkcn 囧" 而且Hamilton path不是NPC嗎? 02/14 23:27
7F：推 yoco315:MST 是 TSP 的一個近似解，演算法上課不是都會教？ 02/15 10:13
8F：→ yoco315:對了，請問 BB 是蝦米？ 02/15 10:13
9F：推 cole945:呃..好像沒學到過o_O 不過我的疑惑是,MST並不是path呀._.? 02/15 11:18
10F：→ cole945:還有TSP是什麼的縮寫@o@? 02/15 11:20
11F：→ cole945:知道TSP是什麼了..||| 02/15 11:26
12F：推 asword:BB 是 branch and bound? 02/15 13:30
13F：推 tkcn:是的.. BB 是 Branch & Bound 02/15 13:40
15F：推 revivalworld:囧 是 hamilton 看錯了Orz 02/15 17:59
16F：→ JosephChen:Traveling Salesman Problem 02/15 22:30
17F：→ TonyQ:MST是全局的樹啊 但是只看樹跟子節點的話可以視為很多的path 02/16 00:45
18F：推 ahand520:hamilton path是NPC喔，如果要heuristic我這邊倒是有 02/16 15:29