算法：所有点之间的最短路径 [英] Algorithm: shortest path between all points

问题描述

假如我有10分。我知道每个点之间的距离。

Suppose I have 10 points. I know the distance between each point.

我需要找到最短的路线经过的所有问题。

I need to find the shortest possible route passing through all points.

我已经试过了几个算法（Dijkstra算法，弗洛伊德沃肖尔，...），他们都给予我的起点和终点之间的最短路径，但他们不与它的所有点的路由。

I have tried a couple of algorithms (Dijkstra, Floyd Warshall,...) and they all give me the shortest path between start and end, but they don't make a route with all points on it.

置换做工精细，但他们太资源昂贵。

Permutations work fine, but they are too resource-expensive.

你能劝什么算法，我寻找到这个问题？或者是有文件的方式与上述算法做到这一点？

What algorithms can you advise me to look into for this problem? Or is there a documented way to do this with the above-mentioned algorithms?

推荐答案

看一看旅行商问题。

您可能要考虑一些启发式的解决方案的。他们可能无法给你100％精确的结果，但他们往往能拿出足够好的解决方案（2〜3％，离最优解）在一个合理的时间。

You may want to look into some of the heuristic solutions. They may not be able to give you 100% exact results, but often they can come up with good enough solutions (2 to 3 % away from optimal solutions) in a reasonable amount of time.

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