[發案] 最短漢米爾頓路徑(Hamilton path)演算法

[stool100 (思念是毒妳是解藥)]

        狀態: 已發包
        發案人: Kevin Lai
        聯絡方式1: MSN : [e-mail]
        聯絡方式2: 站內信聯繫
        有效時間: 徵到為止
        專案類型: 演算法
        專案說明:

請教是否有高人可以協助最佳路徑的演算法
條件是 平面上 N 個點
每一點都必須拜訪
不需考慮交叉線或是轉角
也不用回到原點
只需要最短路徑
希望是簡單快速的演算法
不需嚴謹到絕對最短路徑
虛擬碼含說明即可.
不需程式.

        技術需求: 演算法
        預算: 歡迎報價
        接案者要求: 北部
        附註:


        結案意見: (結案後自由填寫,可以詢問接案人願不願意暴光接案身份)
        接案人:
        說明: 目前進行中

--

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.116.6.19
※ 編輯: stool100        來自: 122.116.6.19         (02/14 10:06)
推 uqljnro:最小生成樹
推 yoco315:推最小生成樹
推 tkcn:我倒覺得直接用 BB 找到一定階段，效果可能會比較好
推 revivalworld:google Prim or Dijkstra
推 tkcn:不懂MST跟最短路徑有啥關係..找出來的path有一堆edge要走兩次
※ 編輯: stool100        來自: 122.116.6.19         (02/14 21:25)
推 cole945:推 tkcn  囧"  而且Hamilton path不是NPC嗎?
推 yoco315:MST 是 TSP 的一個近似解，演算法上課不是都會教？
→ yoco315:對了，請問 BB 是蝦米？
推 cole945:呃..好像沒學到過o_O 不過我的疑惑是,MST並不是path呀._.?
→ cole945:還有TSP是什麼的縮寫@o@?
→ cole945:知道TSP是什麼了..|||
推 asword:BB 是 branch and bound?
推 tkcn:是的.. BB 是 Branch & Bound
推 tkcn:我也沒學過MST找hamilton cycle @@   http://0rz.tw/503Ej
推 revivalworld:囧 是 hamilton   看錯了Orz
→ JosephChen:Traveling Salesman Problem
→ TonyQ:MST是全局的樹啊 但是只看樹跟子節點的話可以視為很多的path
推 ahand520:hamilton path是NPC喔，如果要heuristic我這邊倒是有