保留とKarpアルゴリズムを使用したトラベリングセールスマン

Question

私は旅行セールスマンの問題に対するDPソリューションを十分に認識しています。 TSPのHeld and Karpアルゴリズムとも呼ばれます。

私はビットマスクでそれを実装した、そしてそれはこのようなものです：

int TSP(int pos, int bitmask) { 
    if (bitmask == (1<<(K+1))-1) 
     return dist[pos][0];    // Completing the round trip 

    if (memo[pos][bitmask] != -1) 
     return memo[pos][bitmask]; 

    int answer = INF; 
    for (int i = 0; i <= K; i++) { 
     if (i != pos && (bitmask & (1 << i)) == 0) 
      answer = Math.min(answer, dist[pos][i] + TSP(i, bitmask | (1 << i))); 
    } 

    return memo[pos][bitmask] = answer;  // Storing the best dist for the set of traveled cities and untraveled ones. 

}

このアルゴリズムは、非常に高速です。 15都市の計算は比較的速いです。しかし、私はそれがさらに約20の都市に適応するように改善されることに気づいた。 distの行列が対称である場合

1）、おそらく我々は繰り返し計算を防ぐために、この性質を利用することができます。 （例えばA-> B-> C-> D-> == A-> D-> C-> B-> A）

2）上部及び整理する下界の両方の使用。上記のアルゴリズムは、非常に短時間で最初の可能な最適解を得ることができ、それを使用できるかもしれません。

私は上記の2つの原則に基づいたアルゴリズムを改善しようとしています。しかし、私はより良いアルゴリズムを得ることはできません。

私は不可能な何かを向上させることで、無益な試みを行っていますか？どう思いますか？

Answer 1

私はあなたが正しいと思います。あなたの方法では、都市の最大数は20,21または22ですが、25にすることはできません。これは、アルゴリズムのステータスの数がn *（2^n）であるためです.n = 20の場合、約10^7、n = 25の場合、それは約10^9です。これは非常に大きな数です。最新のコンピュータでは、1秒以内に約10^7の計算を処理できます。しかし、10^9の計算には約100秒かかります。

だから私は、などの模擬アニーリングアルゴリズム、遺伝的アルゴリズム、同様に、より多くの都市を処理したい場合は、いくつかの近似アルゴリズムが有用かもしれないと思うそれとも複数のマシンを使用して、問題を縮小することができます。