算法优化——多点之间的最短路线

Question

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

例如:我正在度假，我住在一个特定的城市。我正在进行一次单程旅行，去看看任何四个城市，我想旅行的距离尽可能短。我不能多次访问同一个城市。

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

搜索最短路径的更好方法是什么？

Answer 1

回答更新后的帖子，您检查每种可能性的解决方案是最佳的(至少，到目前为止还没有人发现更好的算法)。是的，那是一个旅行推销员，他的本质不是去每一个城市，而是去每一个城市一次。如果您不想搜索可能的最佳解决方案，您可能会发现使用工作速度更快但允许与理想解决方案存在有限差异的启发式方法很有用。

---

对于 future 的回答者:Floyd-Warshall algorithm并且所有类似弗洛伊德的变体在这里都不适用。