算法: 10个城市之间的最短出行路线
算法: 10个城市之间的最短出行路线
提问于 2020-03-27 02:31:54
我有一个包含80个城市的图表。我需要找到一条经过10个城市的尽可能短的路线。
我必须从一个已经定义为起始城市的城市开始，用户将从城市列表中输入10个城市名称。我必须旅行这10个城市，然后我必须回到我开始的城市。我只有相邻城市之间道路距离的所有信息，除了这些，我没有任何信息。
我知道Dijkstra等人找到了两个城市之间的最短路径，一些启发式算法需要更多的数据。
我可以使用Dijkstra寻找起始城市和其他10个城市之间的最短路径，然后找到其中的最小生成树并遍历它吗？有没有什么启发式算法可以用来处理这些数据？
回答 1
Stack Overflow用户
发布于 2020-03-27 05:13:08
给出你的10个城市，找出每对城市之间的最短路径。这只是对Dijkstra算法的45次调用。这为您提供了一个包含10个顶点的完整图。
现在你有一个旅行推销员的问题，但是10个城市并不是那么多，而且你得到了开始城市，所以只有9！(362880)个可能性。我会简单地尝试所有的排列，并找到最小的一个。
您可以做一些更聪明的事情，但是这个简单的暴力解决方案将是快速且易于编码的。
编辑:也许你有一个起始城市和10个其他城市。不过，10！(3728800)仍然足够小，足以使搜索每个排列的速度足够快
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/60873945
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号