algorithm
旅行セールスマン

備考

ブルートフォースアルゴリズム

すべての頂点を通るパスは、何らかの方法で頂点を順序付けするのと同じです。したがって、すべての頂点を1回だけ正確に1回移動するための最小コストを計算するには、 N! 1からNまでの数の順列。

擬似コード

minimum = INF
for all permutations P

    current = 0                                

    for i from 0 to N-2
        current = current + cost[P[i]][P[i+1]]  <- Add the cost of going from 1 vertex to the next
    
    current = current + cost[P[N-1]][P[0]]      <- Add the cost of going from last vertex to the first

    if current < minimum                        <- Update minimum if necessary
        minimum = current
    
output minimum

時間の複雑さ

N!がありますN!各経路のコストはO(N)で計算されるので、このアルゴリズムはO(N * N!)時間で正確な答えを出力します。

動的プログラミングアルゴリズム

パスを（順番に）考慮すると、次のようになります。

(1,2,3,4,6,0,5,7)

とパス

(1,2,3,5,0,6,7,4) 

頂点1から頂点2 、頂点3までのコストは同じなので、なぜ再計算する必要がありますか？この結果は、後で使用するために保存することができます。

ましょうdp[bitmask][vertex] 、その対応するビット内のすべての頂点を通って移動するの最小コスト表すbitmaskに設定されている1で終了vertex 。例えば：

dp[12][2] 

   12   =   1 1 0 0
            ^ ^ 
vertices:   3 2 1 0

12は2進数で1100を表しているため、 dp[12][2]は頂点2で終了するパスを持つグラフの頂点2と3を通過することを表します。

したがって、次のアルゴリズム（C ++実装）を持つことができます。

int cost[N][N];                        //Adjust the value of N if needed
int memo[1 << N][N];                   //Set everything here to -1
int TSP(int bitmask, int pos){
    int cost = INF;
    if (bitmask == ((1 << N) - 1)){      //All vertices have been explored
        return cost[pos][0];             //Cost to go back
    }
    if (memo[bitmask][pos] != -1){       //If this has already been computed
        return memo[bitmask][pos];       //Just return the value, no need to recompute
    }
    for (int i = 0; i < N; ++i){         //For every vertex 
        if ((bitmask & (1 << i)) == 0){  //If the vertex has not been visited
            cost = min(cost,TSP(bitmask | (1 << i) , i) + cost[pos][i]);   //Visit the vertex
        } 
    }
    memo[bitmask][pos] = cost;           //Save the result
    return cost;
}
//Call TSP(1,0)

この行はちょっと混乱するかもしれませんので、ゆっくりと進みましょう：

cost = min(cost,TSP(bitmask | (1 << i) , i) + cost[pos][i]);

ここで、 bitmask | (1 << i)は、bitmaskのi番目のbitmaskを1に設定します。これは、i番目の頂点が訪問されたことを表します。コンマの後のiは、新しい「最後の」頂点を表す関数呼び出しの新しいposを表します。 cost[pos][i]は、頂点posから頂点iに移動するコストを加算することです。

したがって、この行は、まだ訪問されていない他のすべての頂点に移動する可能な最小値にcostの値を更新することです。

時間の複雑さ

関数は、 TSP(bitmask,pos)有する2^Nの値bitmaskとNの値pos 。各関数は実行にO(N)時間かかる（ forループ）。したがって、この実装では、正確な答えを出力するためにO(N^2 * 2^N)時間がかかります。