假设我有10分 . 我知道每个点之间的距离 .
我需要找到通过所有点的最短路线 .
我已经尝试了几种算法（Dijkstra，Floyd Warshall，......），它们都给了我开始和结束之间的最短路径，但是它们没有制作一条包含所有点的路线 .
排列工作正常，但它们太耗资源 .
您可以建议我使用哪些算法来研究这个问题？或者是否有记录的方法使用上述算法执行此操作？
看看travelling salesman problem .
您可能想要查看一些heuristic solutions . 他们可能无法为您提供100％的确切结果，但通常他们可以在合理的时间内提出足够好的解决方案（距离最佳解决方案2％到3％） .
这显然是Travelling Salesman problem . 特别是对于 N=10 ，您可以尝试 O(N!) 天真算法，或使用Dynamic Programming，您可以通过交易空间将其减少到 O(n^2 2^n) .
N=10
O(N!)
O(n^2 2^n)
除此之外，由于这是一个NP难题，你只能希望得到一个近似或启发式，给出通常的警告 .
正如其他人所提到的，这是TSP的一个实例 . 我认为，乔治亚理工学院开发的Concord是目前最先进的解决方案 . 它可以在几秒钟内处理超过10,000点 . 它还有一个易于使用的API .
我认为这正是你正在寻找的，实际上：
Floyd Warshall
在计算机科学中，Floyd-Warshall算法（有时称为WFI算法[需要澄清]，Roy-Floyd算法或仅Floyd算法）是用于在加权图中找到最短路径的图分析算法（具有正边缘或负边缘）权重） . 算法的单次执行将找到所有顶点对之间的最短路径的长度（总和权重），尽管它不会返回路径本身的细节
在“路径重建”小节中，它解释了存储“路径”所需的数据结构（实际上，您只需存储下一个节点，然后根据需要轻松地重建所需的路径） .
4 回答
看看travelling salesman problem .
您可能想要查看一些heuristic solutions . 他们可能无法为您提供100％的确切结果，但通常他们可以在合理的时间内提出足够好的解决方案（距离最佳解决方案2％到3％） .
这显然是Travelling Salesman problem . 特别是对于
N=10，您可以尝试O(N!)天真算法，或使用Dynamic Programming，您可以通过交易空间将其减少到O(n^2 2^n).除此之外，由于这是一个NP难题，你只能希望得到一个近似或启发式，给出通常的警告 .
正如其他人所提到的，这是TSP的一个实例 . 我认为，乔治亚理工学院开发的Concord是目前最先进的解决方案 . 它可以在几秒钟内处理超过10,000点 . 它还有一个易于使用的API .
我认为这正是你正在寻找的，实际上：
Floyd Warshall
在“路径重建”小节中，它解释了存储“路径”所需的数据结构（实际上，您只需存储下一个节点，然后根据需要轻松地重建所需的路径） .