c - 2-Opt ローカル検索の実装

Question

巡回セールスマンの問題を解決するために、ローカル検索 (2-opt) を実装しようとしています。ただし、完全な回路 (ノードのツアー) を正しく再作成するのに問題があります。アルゴリズムに欠陥がある可能性があると思います。これは 2-opt の私の実装です:

a->b->...d->c->...a

に切り替えます

a->d->...b->c->...a

私の一般的なプロセスは標準的なスワップのように見えます: b を temp として保存 c を temp2 a->d b->c として保存

私のコードは次のようになります。

node* twoOpt(double** distance_matrix, node* tour, int NUM_CITIES)
{
int rand1, rand2;
int temp, temp2;

rand1 = rand() % NUM_CITIES; //a
rand2 = rand() % NUM_CITIES; //d

do
{
    //Ensure the two numbers are different
    while (rand1 == rand2 || tour[rand1].destination == rand2 || rand1 == tour[rand2].destination)
        rand2 = rand() % NUM_CITIES;

    //Make swap
    temp = tour[rand1].destination; //b
    temp2 = tour[rand2].destination; //c

    tour[rand1].destination = rand2;
    tour[rand1].distance = distance_matrix[rand1][rand2]; //a->d

    tour[temp].destination = temp2;
    tour[temp].distance = distance_matrix[temp][temp2]; //b->c

} while(!travelTour(tour, NUM_CITIES));

return tour;
}

これで、このコードが完璧ではないことがわかりました。たとえば、再シャッフルされた 2 つのノードが完全な回路を作成しない場合、コードは 2 番目のノードのみを変更してから再試行します。しかし、私が持っている質問は、そもそもなぜその完全なツアーを取得できないのかということです.

ご協力いただきありがとうございます！

Answer 1

私はついに問題を見つけました。私のソリューションの概念は不完全でした。a->d と b->c を指す必要があるだけでなく、新しいツアーの影響を受ける半分をすべて反転する必要もありました。つまり、古いパスを b から d に反転する必要があります。正しいコードは次のとおりです。

do
{
    //Ensure the two numbers are different
    while (rand1 == rand2 || tour[rand1].destination == rand2 || rand1 == tour[rand2].destination)
        rand2 = rand() % NUM_CITIES;

    //Make swap
    temp = tour[rand1].destination; //b
    temp2 = tour[rand2].destination; //c

    tour[rand1].destination = rand2;
    tour[rand1].distance = distance_matrix[rand1][rand2]; //a->d

    oldNode = temp;
    currNode = tour[oldNode].destination;

    tour[temp].destination = temp2;
    tour[temp].distance = distance_matrix[temp][temp2]; //b->c

    //Swap directions of graph for d->b
    while (currNode != temp2)
    {
        nextNode = tour[currNode].destination;
        tour[currNode].destination = oldNode;
        oldNode = currNode;
        currNode = nextNode;
    }
} while(!travelTour(tour, NUM_CITIES));

それはまだ完全にきれいではありません。プロジェクトを再起動する必要がある場合、データをノードとして保存しません。私はそれらをエッジの観点から保存し、各エッジはその 2 つのノードの知識を持っています。これにより、交換がはるかに簡単になります。それにもかかわらず、これがこの設計に対する私の解決策です。

Answer 2

チェーン修正が必要です：

DroolsPlannerのマニュアル から。