算法优化-多点之间的最短路径 [英] Algorithm Optimization - Shortest Route Between Multiple Points

问题描述

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

Problem: I have a large collection of points. Each of these points has a list with references to other points with the distance between them already calculated and stored. I need to determine the shortest route that begins from an origin and passes through a specific number of points to any destination.

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

Ex: I'm on vacation and I'm staying in a specific city. I'm making a ONE WAY trip to see ANY four cities and I want to travel the least distance possible. I cannot visit the same city more than once.

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

Current solution: Right now I'm just iterating through every possibility manually and storing the shortest path. This works but feels inefficient. Also, this problem will eventually be expanded to include searching from multiple origin points to multiple destination points, so I think that might explode the search space.

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

What is the better way to search for the shortest route?

推荐答案

对更新后的帖子的回答是，检查各种可能性的解决方案是最佳的(至少到目前为止，还没有人发现更好的算法).是的，那是一位旅行推销员，他的本质不是触摸每个城市，而是一次.如果您不想寻找最佳的解决方案，则可能会发现使用工作速度更快的启发式方法很有用，但与理想解决方案之间的差异却有限.

Answering to the updated post, your solution of checking every possibility is optimal (at least, noone has discovered better algorithms so far). Yes, that's a travelling salesman, whose essense is not touching every city, but touching every city once. If you don't want to search for best solution possible, you may find it useful to use heuristics that work faster, but allow for limited discrepancy from ideal solution.

对于将来的答复者: Floyd-Warshall算法和所有Floyd-类似的变体在这里不适用.

For future answerers: Floyd-Warshall algorithm and all Floyd-like variations are inapplicable here.

这篇关于算法优化-多点之间的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！