java - 使用循环排列来降低旅行商的复杂性

Question

我正在尝试一系列不同的算法来为 Traveling Salesman Problem 找到接近最优的解决方案，其中一种方法是蛮力法 - 检查 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) 如果我们意识到所有路径都可以反转而不影响它们的长度。

基本上，我正在寻找一种能够生成 circular permutations 的算法。来自一组不同的整数。如果算法将“镜像”排列视为等效(例如 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