java - 2-opt 搜索实现有缺陷吗？

Question

我正在尝试为 Java 中的 TSP 设计一个 2-opt 本地搜索启发式算法，但我的算法似乎有缺陷。给定一个最近邻电路作为输入，它会以某种方式使电路变得更糟。最近的邻居:http://goo.gl/uI5X6 ; 2-opt 十秒后:http://goo.gl/5AGJ1 。我的代码如下。我的实现有什么问题吗？ Location[] location 只是“图”的节点列表，每个节点都有经纬度以及它与另一个节点之间的距离计算。

    public HamiltonianCircuit execute(Location[] locations) {
    long startTime = System.currentTimeMillis();
    while (true) {
        for (int i = 0; i < locations.length; i++) {
            for (int k = 0; k < locations.length; k++) {
                if (System.currentTimeMillis() - startTime >= 10000) {
                    return new HamiltonianCircuit(locations);
                }
                Location a = locations[i];
                Location b = locations[(i + 1) % locations.length];
                Location c = locations[k];
                Location d = locations[(k + 1) % locations.length];
                double distanceab = a.distanceBetween(b);
                double distancecd = c.distanceBetween(d);
                double distanceac = a.distanceBetween(c);
                double distancebd = b.distanceBetween(d);
                double change = (distanceab + distancecd) - 
                    (distanceac + distancebd);
                if (change > 0) {
                    locations[k] = a;
                    locations[i] = c;
                }
            }
        }
    }
}

Answer 1

2-opt 将边 AB 和 CD 替换为边 AC 和 BD，这意味着如果我们从部分电路 0 A B x y z C D 1 开始，完成后我们需要 0 A C z y x B D 1。< br/>您的代码将生成 0 C B x y z A D 1。

您想要交换 B 和 C，但还需要反转中间的所有内容。