1

質問：巡回セールスマン問題で、すべての都市サブセット{1,2、...、n}の正しい反復順序をどのように処理しますか？

私のソリューションでは、サブセットはビットマスク（今のところ単に整数）で表されます。すべての結果は2次元配列Cに格納されます。ここで、1次元Sは都市サブセット（つまり、ビットマスク）に似ています。2番目の次元jは、 Sのすべての都市間を移動するコストを保持し、jは終了都市です。

すべてのサブセットには都市0（開始都市）が含まれ、アルゴリズムは最短ルートを設定することから始まります。

C[{0}][0] = 0;

ただし、このアルゴリズムが機能するには、すべてのサブセットをサブセットサイズの順に繰り返す必要があります。

これは単純なコードスニペットで、すべてのサブセットを増加する値で出力します。

#include <cstdio>

const int n = 5; // number of cities
const int s = 1 << n; // number of subsets

void printb(int x)
{
    for (int i = n-1; i >= 0; i--) {
        printf("%d", (x >> i) & 1);
    }
}

int main()
{
    for (int i = 0; i < s; i++) {
        printb(i); printf("\n");
    }

    return 0;
}

私の目標は、サブセットサイズ（ビット数）の順にサブセットを列挙することです。

私が使用しているアルゴリズムの説明：Algorithms、S。Dasgupta、CH Papadimitriou、およびUV Vazirani（p188）

4

1 に答える 1

2

TSPを正しく解くために、サイズ2のサブセットをトラバースする前に、実際にすべてのサイズ1のサブセットをトラバースする必要はありません。セットXをトラバースする前に、特定のセットXのすべてのサブセットをトラバースする必要があります。セットの標準エンコーディングを使用して番号順に反復を実行すると、このプロパティが満たされます。

于 2013-01-04T03:19:09.680 に答える