[問題] xy平面點最短距離問題

看板Python作者 (阿偉)時間4年前 (2020/03/03 00:27), 編輯推噓1(1推 0噓 13→)
留言14則, 4人參與, 4年前最新討論串1/1
版上各位好， 小弟想請教一個問題 如圖下圖所示，我有好幾個橘色點(分別有各自的xy座標) https://imgur.com/VJhyQeO
而我想做到指定起點後依照最短路徑點做連接 最終將其全部連接完畢 請問有什麼好的演算方法可以做到這件事嗎(時間複雜度盡量低) 網上搜尋有找到 廣度優先搜尋、深度優先搜尋、dijkstra等演算法似乎是在解決最短路徑問題 但小弟才疏學淺不曉得這幾種演算法是否有機會適用到我的問題上 希望版上大大幫解惑QQ 感激不盡! -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.169.144.155 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Python/M.1583166425.A.FC0.html
→
03/03 02:49, 4年前 , 1F
有，但你要會用呀。先決定問題再決定資料儲存方式，最後才
03/03 02:49, 1F
→
03/03 02:50, 4年前 , 2F
是演算法，至於挑選哪個？根據你的問題和資料特性都會不同
03/03 02:50, 2F
→
03/03 02:50, 4年前 , 3F
，就看你要不要花時間下去。
03/03 02:50, 3F
→
03/03 11:02, 4年前 , 4F
dijkstra 可以，只是你要先建立點與點之間的路徑，如
03/03 11:02, 4F
→
03/03 11:02, 4年前 , 5F
果不想實作，可以看看networkx
03/03 11:02, 5F
推
03/03 13:21, 4年前 , 6F
這是TSP吧 NP hard問題不要覺得有高效演算法
03/03 13:21, 6F
→
03/03 13:21, 4年前 , 7F
但是concorde可以參考一下
03/03 13:21, 7F
→
03/03 13:23, 4年前 , 8F
補充一下 你這問題不像TSP要回第一個點 但也可能我會
03/03 13:23, 8F
→
03/03 13:23, 4年前 , 9F
有poly time演算法
03/03 13:23, 9F
→
03/03 16:25, 4年前 , 10F
Hs大，摁摁了解了 感謝!
03/03 16:25, 10F
→
03/03 16:25, 4年前 , 11F
aas大，摁摁dijkstra感覺是可行的，只不過我考慮到時間
03/03 16:25, 11F
→
03/03 16:26, 4年前 , 12F
複雜度的問題，所以在想是否有更好的選擇方法
03/03 16:26, 12F
→
03/03 16:27, 4年前 , 13F
Ti大，其實我的需求應該是要讓他回第一點
03/03 16:27, 13F
→
03/03 16:27, 4年前 , 14F
我會再看看你說的TSP方法，感謝!
03/03 16:27, 14F
‣ 更多 oo855050 的文章
文章代碼(AID): #1UNJFP_0 (Python)