作者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/cn.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