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

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

能不能不保存已经探索过的路径，不用每次都重新计算就可以使用？

为你的路径写一个比较函数。每次计算路径时，将其保存在 Hashmap 或随处可访问的类似文件中，并且每次计算路径时，确保它不在 Hashmap 中。

在探索完节点的所有连接后，将节点标记为已检查，这样您就不会浪费时间重新计算子路径。这可能需要您将 String path 替换为某种 List<Node> ，其中 Node 是您编写的 class 代表图形上的任何节点。

调查memoization

Whosebug on memoizing

另外，一定要看看现有的探路者，比如 A*，它在网上有大量的信息，你或许可以从中汲取灵感。

Answer 2

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

首先是一般提示，删除该字符串。字符串对于任何不是字符串的东西都很糟糕，而您正在使用它来存储整数数组。只需使用一个整数数组。同时停止数组中的 "removing" 项。只需稍微排列一下并记住你有多少 "removed" （因此数组中将有两个区域，一个用于逻辑上位于其中的项目，另一个用于逻辑上已被删除的项目）。

但更重要的是，您正在探索所有搜索 space，而且您通常不必这样做（除非遇到烦人的情况）。如果你计算到目前为止你在部分电路中创建了多少距离，你可以修剪只能导致 "worse than the best solution so far" 的整个子树。这可以通过从一个合理的上限开始来改进，例如使用贪婪的最近邻路径 and/or 本地搜索（2-OPT 是最简单的，也不错）。

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

这将倾向于创建每个包含 3 个城市的小型子地图，地图上到处都是一堆三角形。这是一个糟糕的估计，你可以通过禁止 subtrours 让它变得更好：进行 subtour，创建一个约束，即与该 subtour 相邻的道路总和至少为 2（不完全是，你被允许进入多次进出，但你必须每次至少进进出出一次，这样这些道路的总和至少为 2)。再次最小化，如果有更多子图，也将它们消除。您可能会得到一个包含道路 "partially used" 的解决方案（即分配的值既不是 0 也不是 1），因此这不会为您提供实际的游览，只是对距离的低估，考虑到目前所做的选择。

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

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

Travelling Salesman - How to find permutations that are not equivalent

java

algorithm

recursion

graph

permutation