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