旅行商 (TSP) 获取实际路径

Question

我想知道是否有一种方法可以在我的解决方案中获取通过蛮力算法 (TSP) 选择的路径（不仅是距离），就像我只获取距离一样。

请注意，我从斯德哥尔摩市开始，在斯德哥尔摩结束。

最短路径是city1 --> City2 --> City3 ----> ......然后---> City1 ?

我主要的一部分class:

    public void step(boolean[] wentTo, int currentCity, float distance)
    {
        int wentToCount = 0;
        for (int i = 1; i <= cityCount; ++i)
        {
            if (wentTo[i - 1])
            {
                ++wentToCount;
                continue;
            }
            boolean[] copy = new boolean[cityCount];
            System.arraycopy(wentTo, 0, copy, 0, cityCount);
            copy[i - 1] = true;
            float dist = distance + distances[distanceIndex(currentCity, i)];
            step(copy, i, dist);
        }
        if (wentToCount == cityCount)
        {
            if (shortest > distance)
            {
                shortest = distance;
            }
        }
    }

Answer 1

简单的部分：只需在计算中注册变量即可。如果您的算法稍后决定使用另一条路线，则重置。对于不了解您的代码的局外人来说，困难的部分是尝试将其融入充其量难以理解的代码中。不过，这是一个尝试。为了记录路线，我使用了两个实例变量：

/** stack of numbers of towns on the route so far */ 
private Deque<Integer> route = new ArrayDeque<>();
/** shortest route found */
private List<Integer> solution;

要保持第一个更新，请在递归调用之前和之后执行此操作：

        route.push(i);
        step(copy, i, dist);
        // after having tried town i, remove it from route again before trying next town
        int j = route.pop();
        assert j == i : "Got wrong town off stack, " + j + " instead of " + i;

这将确保在您将所有城镇添加到路线后，它们也会以正确的顺序出现在 route 堆栈中。

要使 solution 保持最新，请在找到更短的路线时为其添加新值：

        if (shortest > distance)
        {
            shortest = distance;
            solution = new ArrayList<>(route);
        }

现在，当您打印出最短距离时，您的 solution 保留了访问过的城镇的顺序，因此您也可以打印它。

由于没有拿到你的完整代码，没机会测试，可能还需要打磨一下。

旅行商 (TSP) 获取实际路径

Travelling salesman (TSP) getting the actual path

java

algorithm

traveling-salesman

brute-force