1

Java で TSP 用の 2-opt ローカル検索ヒューリスティックを設計しようとしていますが、アルゴリズムに欠陥があるようです。入力のように最近傍回路が与えられると、どういうわけか回路が悪化します。最も近い隣人: http://goo.gl/uI5X6 ; 2-opt の 10 秒後: 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;
                }
            }
        }
    }
}
4

2 に答える 2

1

2-opt はエッジ AB と CD をエッジ AC と BD に置き換えます。つまり、開始する部分回路 0 AB xyz CD 1 がある場合、完了したら 0 AC zyx BD 1 が必要になります。
コードは 0 CB xyz AD 1 を生成します。

B と C を交換したいのですが、途中ですべてを逆にする必要もあります。

于 2013-07-26T14:52:24.827 に答える