问题:我有很多要点。这些点中的每个点都有一个列表,其中引用了其他点,并且它们之间的距离已经计算和存储。我需要确定从起点开始并经过特定数量的点到任何目的地的最短路线。

例如:我正在休假,我待在一个特定的城市。我正在单程旅行以查看任何四个城市,我希望旅行的距离尽可能短。我不能多次访问同一个城市。

当前解决方案:现在,我只是手动遍历所有可能性并存储最短路径。这行得通,但感觉效率低下。另外,这个问题最终将扩展为包括从多个起点到多个目的地的搜索,因此我认为这可能会扩展搜索空间。

搜索最短路线的更好方法是什么?

最佳答案

回答最新的帖子,您检查所有可能性的解决方案是最佳的(至少到目前为止,没有人发现更好的算法)。是的,那是一位旅行推销员,其本质不是触摸每个城市,而是触摸每个城市一次。如果您不希望寻找最佳解决方案,则可能会发现使用工作速度更快的启发式方法很有用,但可以与理想解决方案保持有限的差异。

对于将来的答复者:Floyd-Warshall algorithm和所有类似Floyd的变体在此处均不适用。

关于算法优化-多点之间的最短路径,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/1511585/

10-10 00:01