使用循环排列来减少旅行商的复杂性

Question

我正在尝试一系列不同的算法来寻找旅行商问题的近似最优解,其中一种方法是蛮力方法 - 检查n个城市之间的每条可能路径,并简单地返回最佳路径.这是一个O(n!)算法,因此很自然地需要很长时间才能执行大量城市.

我想提高我的暴力实施的效率,我注意到的一件事是你不必检查城市的每一个排列.例如,如果您有城市1,2,3和4,则路径(1-2-3-4)与路径(2-3-4-1)的长度相同.路径(3-4-1-2)和(4-1-2-3)也是如此.通过利用这一事实,我们应该能够将蛮力算法的复杂性从O(n!)降低到O((n-1)!),甚至O((n-1)!/ 2)如果我们意识到所有路径都可以反转而不影响它们的长度.

基本上,我正在寻找一种能够从一组不同的整数生成循环排列的算法.如果算法将"镜像"排列视为等效(例如1-2-3和3-2-1是相同的,因此只需要其中一个),这也是很好的.有谁知道这样做的方法？Java实现会很精彩,但我会采取任何措施!

Answer 1

如果您始终从同一节点（例如“1”）开始，则永远不会遇到此问题。然后，您还可以轻松添加镜像检查，因为它只是从节点 0 运行到 N-1 N-2，直到再次为零。

例如，1,2,3,4 有以下排列：

1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431
3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321 

现在，如果我们强制 1 作为第一个节点，您最终将得到这些独特的解决方案：

1234 1243 1324 1342 1423 1432

接下来我们可以消除“镜像”解决方案：

normal => reverse => rotated by 1
1234 => 4321 => 1432
1243 => 3421 => 1342
1324 => 4231 => 1423

您只需要检查：

1234 1243 1324

更新：

生成此序列的最简单方法是枚举 1 ... N-1 的所有可能性，其中 1 在 2 之前（强制方向）并附加 N。

例如，对于 N=4，我们首先生成所有排列 1 ... N-1：

123 132 213 231 312 321 

现在我们过滤 1 在 2 之前的位置：

123 132 312

并附加 N (4)：

1234 1324 3124

这可能更容易、更有效地编程。这也证明了暴力破解TSP所需的上限是：(N - 1)！/ 2