禁断探索法によるTSP (paizaランク S 相当)

巡回セールスマン問題とは、都市の集合と各都市間の距離が与えられ、全都市をちょうど1回ずつ訪れたのち出発した都市に戻ってくるような経路 (巡回路) のうち最も短いものを求める問題です。

ここでは、禁断探索法と呼ばれるアルゴリズムを学習しましょう。このアルゴリズムは発見的解法 (ヒューリスティクス) と呼ばれるもので、ある程度良い解が出力されることが期待されるものの、解の精度は全く保証されません。

一般的な禁断探索法の概要は、以下の通りです。

・ 解を適当に作り、暫定解 X とする。最良解 B を X で初期化する。禁断リストを空で初期化する。禁断リストのサイズの上限 TL を決める
・ 一定の回数、以下を繰り返す
    ・ (*) 暫定解 X を少しだけ変更したもの (X の近傍) であって、なおかつ禁断リストに含まれていない解のうち最も良い解 X' を求め、X を X' で更新する。X が B より真に良い場合は、B を X で更新する。解 X を禁断リストの先頭に加える。禁断リストのサイズが TL を超えた場合は禁断リストに含まれている最も古い解を削除する
・ 最良解 B を解として出力する

禁断リストを用いることによって、探索済みの解にすぐ戻ってしまう (= 探索がループしてしまう) ことが少なくなることが期待されます。このようにすることで、探索が局所解で停滞してしまうのを防いでいます。

この禁断探索法を用いて巡回セールスマン問題を解くことを考えます。まず、巡回路 X の近傍をどうするか、また禁断リストに何を入れるのか、を決める必要があります。ここでは、以下のようにします。

・ 巡回路 X に含まれる 2 本の辺を繋ぎ変えたものを X の近傍とする
・ 禁断リストには繋ぎ変えた辺の端点のうち巡回路 X の先頭に最も近い都市 t を入れる。つまり、t を端点として持つ辺を繋ぎ変えて解を更新した後しばらくは、t を端点として持つ辺は繋ぎ変えない

辺の繋ぎ変え方は 2-opt 法と同様です。例えば、辺 (a, d) と (b, c) を繋ぎ変えると 辺 (a, b) と (c, d) になります。



n 個の都市 (都市 0、都市 1、...、都市 n-1) のデータと、n 個の都市を巡る初期巡回路、整数 q、tl が与えられます。禁断探索法を実装し、巡回路を求めてください。(*) の処理は q 回繰り返してください。禁断リストのサイズは tl としてください。

ジャッジの都合上、以下の疑似コードに従って実装してください。SWAP(a, d, b, c)は巡回路 tour の辺 (a, d) と (b, c) を繋ぎ変えて辺 (a, b) と (c, d) にする処理を表します。

void tabu_search(){
    // 暫定解
    tour = (初期巡回路)
    // 最良解
    tour_best = tour
    // 禁断リスト    
    tabu_list = (空のキュー) 

    for(int i = 0; i < q; i++){
        a_best, b_best, diff = 99999999

        // 暫定解 tour の近傍を全探索する
        for(int a = 0; a < n; a++){
            if(tour[a] in tabu_list){
                // 都市 tour[a] を端点として持つ辺を繋ぎ変えてからあまり時間が経っていない場合は、tour[a] を端点として持つ辺は繋ぎ変えない
                continue;
            }
            for(int b = a+2; b < n; b++){
                if(a == 0 && b == n-1){
                    // 繋ぎ変える 2 辺の端点が重複してしまう場合を除外する
                    continue;
                }
                tmp_diff = (都市 tour[a] と tour[a+1] を結ぶ辺と、都市 tour[b] と tour[(b+1)%n] を結ぶ辺を結ぶ辺を繋ぎ変えた際の巡回路長の変化)
                if(diff > tmp_diff){
                    diff = tmp_diff;
                    a_best = a, b_best = b;
                }
            }
        }

        // タブーリストを更新する
        tabu_list.push(tour[a_best]);
        if(tabu_list.size > tl){
            tabu_list.pop()
        }

        // 暫定解 tour の近傍のうち最も良い解を新たな暫定解とする
        SWAP(tour[a_best], tour[a_best+1], tour[b_best], tour[(b_best + 1)%n]);

        if(tour の巡回路長が tour_best の巡回路長より短い){
            tour_best = tour;
        }
    }

    // tour を解として出力
}

なお、各都市は二次元平面上の点として与えられ、都市間の距離にはユークリッド距離を用いるものとします。

巡回路の始点は任意です。巡回路が正しければ正解と判定されます。