从完全图计算最短路径

Question

我有一个矩阵NxN，其中matrice[i][j]是无向图中顶点i和fj之间的边的代价。

我需要确定的是包含矩阵中所有顶点的最短路径。

因此，对于像这样的输入：

0 198 67 368
198 0 131 432
67 131 0 301
368 432 301 0

我需要尝试所有可能的路径，在这种情况下：

0-->1-->2-->3-->0

长度为998是正确的。

我如何实现这一点？

Answer 1

您所描述的是被广泛研究的Traveling Salesman Problem。

虽然有许多方法可以近似一个解决方案-确切的解决方案确实需要指数运行时间，而蛮力是解决它的一种选择(在O(n!)中)。

这个想法是生成所有可能的排列并评估每个排列-并找到最小的排列。

例如，This question讨论了如何生成所有排列。同样的想法也适用于你的问题。

有一些可能的优化是可以完成的，例如branch & bound技术-或者使用智能DP解决方案。