Python中文
首页
教程
问答
标签
搜索
登录
注册
最短路线,起点和终点任意
回答此问题可获得
20
贡献值,回答如果被采纳可获得
50
分。
<p>我正在寻找一个算法,将连接大量的地理坐标(100-1000),创造他们之间的最短可能的路线,从任何地方开始,并完成任何其他地方。我在用Python。你知道吗</p> <p>我已经研究了可用的算法,我的问题类似于旅行推销员,但它需要我定义一个起点,并在结束时回到同一个点。<strong>我会把Uber带到任何起点和终点。我想要的是在尽可能少的步行时覆盖所有点。我不在乎它从哪里开始或结束。你知道吗</p> <p>Prim和Kruskal的算法似乎能找到好的起点和终点,但它们创建了一棵树,而不是像TSP那样优化的行走路线。你知道吗</p> <p>Prim算法:</p> <p><a href="https://i.stack.imgur.com/8qqvK.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/8qqvK.gif" alt="Prim's algorithm"/></a></p> <p>克鲁斯卡尔算法:</p> <p><a href="https://i.stack.imgur.com/jMNhc.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/jMNhc.gif" alt="enter image description here"/></a></p> <p>基于Prim/Kruskal,但使用TSP逻辑的期望结果(手工绘制的示例,未优化):</p> <p><a href="https://i.stack.imgur.com/NYXJX.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/NYXJX.png" alt="Desired outcome"/></a></p>
0 条评论
分类:
Python问答
请先
登录
后评论
默认排序
时间排序
1 个回答
匿名
1天前
擅长:python、mysql、java
<p>Prim和Kruskal是寻找生成树的算法。您正在尝试解决一个众所周知的TS(旅行推销员问题)变体,在这个变体中,您不会回到您的起点。你知道吗</p> <p>根据你的定义,你家的位置无关紧要。你定义的问题是用最少的旅行距离访问每一个地方,而不是回到你的起点。这在“文学”中有很好的论述。你知道吗</p> <p>“快速打击”解决方案是采取任何标准的TS解决方案,并删除最长的部分。这是一个很好的启发,虽然它不能保证最优的解决方案。你知道吗</p>
请先
登录
后评论
针对此问题:
更多的回答
关注
89
关注
收藏
1
收藏,
216
浏览
网友 提问于 2天前
相关Python问题
如果给定字符串与字典中的键值匹配,如何返回键
5 回答
如果给定字符串与字典中的键匹配,如何返回键的值
10 回答
如果给定字符串与某些格式不匹配,将引发哪个异常?
1 回答
如果给定存储库和修订号#/revision ID,我可以使用什么Bzr函数返回分支位置?
3 回答
如果给定开始和结束版本号,是否有bzrlib函数将返回所有虚线版本号?
1 回答
如果给定日期差(天)中不存在值,Python将删除ID行
6 回答
如果给定时间来源,如何将日期时间从十进制转换为“%y%m%d%H:%m:%S”?
7 回答
如果给定条件,如何计算欧氏距离?
8 回答
如果给定极限,如何在极限处停止循环。如何返回带有附加值的新列表?
2 回答
如果给定查询的lis没有找到记录,Django将返回none对象
10 回答
如果给定点和每个点之间的距离(测向纬度, 液化天然气)小于或等于0.1km
2 回答
如果给定的字符串与字典中的keys值匹配,如何返回字符串中的多个键
8 回答
如果给定的数字是列表中存在的两个不同数字的总和(仅在一次过程中),如何返回“True”?
3 回答
如果给定的数据在R或Python的范围(1到1)内,如何规范化格式(3、2、1、0、1、2、3)的数据?
3 回答
如果给定的日期是本月的最后一天,如何增加月数?
2 回答
如果给定的是像素值而不是坐标值,如何将灰度像素值更改为彩色值
5 回答
如果给定的条件为真,如何打开窗口?
9 回答
如果给定的键和值与字典列表中的匹配,则获取所有字典
2 回答
如果给定相同的名称,python类中的属性值会改变吗?
5 回答
如果给定空列表,则返回“0”
8 回答