java - 旅行推销员 - 如何找到不等价的排列

Question

我们正在尝试优化 TSP 的蛮力方法。它目前运行在 (n-1)!但我们可以通过忽略等效路径将其减少到 (n-1)!/2。

我们无法弄清楚的是，当我们的递归函数从头到尾开发路径时，如何停止向下将导致等效路径的分支。

例如设 A 为起始节点和结束节点，G 为具有 4 个节点 A、B、C、D 的图。中间路径B->C->D与C->D->B和D->B->C相同

我们目前的解决方案是:

private static int minPathFast(int[][] graph, String sequence, int[] nodesLeft, int start) {
    int min;
    if (nodesLeft.length == 0)
    {
        return 0;
    }
    if (nodesLeft.length == 1) {
        probes++;
        return calcDist(graph, sequence + " " + nodesLeft[0], start);
    } else {
        min = minPath(graph, sequence + " " + nodesLeft[0], remove(nodesLeft, nodesLeft[0]), start);
        for (int i = 1; i < nodesLeft.length; i++) {

            int[] newNodesLeft = remove(nodesLeft, nodesLeft[i]);

            int minPath = minPath(graph, sequence + " " + nodesLeft[i], newNodesLeft, start);
            if (minPath < min)
            {
                min = minPath;
            }

        }
    }
    return min;
}

Answer 1

当然，虽然这不是一个出色的算法。如果你不介意，我会介绍一个小的变化..

首先是一般性提示，去掉那个字符串。字符串对于任何不是字符串的东西都很糟糕，而您正在使用它来存储整数数组。只需使用一个整数数组。也停止从数组中“删除”项目。只需稍微排列一下并记住您“删除”了多少(因此数组中将有两个区域，一个用于逻辑上位于其中的项目，一个用于逻辑上已被删除的项目)。

但更重要的是，您正在探索所有的搜索空间，而且您通常不必这样做(除非遇到烦人的情况)。如果您计算到目前为止您在部分电路中创建了多少距离，您可以修剪整个子树，这些子树只会导致“比目前最好的解决方案更糟糕”。这可以通过从一个合理的上限开始来改善，例如使用贪婪的最近邻路径和/或本地搜索获得(2-OPT 是最简单的，也不错)。

无论如何，当您这样做时，您可以改进修剪。不完整的电路必须以某种方式完成，因此您可以低估完成它所需的距离。一个非常基本的方法是将部分电路以最短路径循环回到它的开头。但是你可以用线性规划做出更好的低估；为每条道路引入一个变量，限制在 0 .. 1 范围内。为每个城市添加一个约束，即与该城市相邻的道路对应的变量之和恰好为 2。限制您已经选择的道路(隐式通过创建部分排列)为 1. 将变量的权重设置为其相应道路的长度。尽量减少使用线性规划(获取库，很难对其进行编码)。这实际上低估了整个行程的距离，而不是“完成它的部分”，所以不要将它添加到到目前为止的距离，而是直接使用它。

这将倾向于创建每个包含 3 个城市的小型子路线， map 上到处都是一堆三角形。这是一个糟糕的估计，你可以通过禁止 subtrours 让它变得更好:进行 subtour，创建一个约束，即与该 subtour 相邻的道路总和至少为 2(不完全是，你被允许进入多次进出，但你必须每次至少进进出出一次，这样这些道路的总和至少为 2)。再次最小化，如果有更多子图，也将它们消除。你可能会得到一个道路“部分使用”的解决方案(即分配的值既不是 0 也不是 1)，所以这不会给你实际的旅行，只是低估了它的距离，给定到目前为止所做的选择。

这是低估了一半。足以用于小问题，你可以用这种方式处理 100 个城市(比你目前希望处理的要多得多)。这仅仅是个开始，您可以做很多事情来改进估算，关于它的整本书都有。