1

巡回セールスマン問題 (動的プログラミング) を C で実装したいと考えています。次の疑似コードがあります。

** Ignoring the base cases**
** C[i][j] is cost of the edge from i to j**
for m = 2,3,4..n:
    for each set S of size m which is subset of {1,2,3...n}:
        for each J in S, j ≠ 1:
            A[S][j] = min  of { A[S-{j}][k] + C[k][j] } for all k is in S and k ≠ j: 

 return min of { A[{1,2,3...n},j] + C[j][1] } for all j from 2 to n

A[S][j] は、S のすべての頂点を 1 回だけ訪れる、1 から j までの最短経路を格納します。(S には 1 と j が含まれます)。

時間計算量は O(n 2 2 n ) です。

私の問題は、この疑似コードではセットを配列インデックスとして使用しており、時間の複雑さは、要素 j ( S - {j}) のないセットのルックアップに一定の時間がかかることを示していることです。

私が考えたのは、m、i、および j でインデックス付けされた 3D 配列を使用することです。'i' は、m,i でインデックス付けされたセットの別の配列に格納されているセットを指します。

A[S-{j}[k]]しかし、問題は、一定の時間でルックアップを実行できないことです。

私の質問は、元のアルゴリズムの時間の複雑さを変更せずに、「セット」によってインデックス付けされた配列をどのように実装するかということです。

4

1 に答える 1

3

各パスをバイナリ文字列で表すとします。各ビットは、都市が訪問されたかどうかを表します。

そう

(123456)
 011001

都市 2、3、および 6 が訪問されることを意味します。

上記を配列インデックスとして使用します。

都市を含まないパスを検索する場合は、そのビットを 0 に設定し、出力をインデックスとして使用します。

最初の都市は常に訪問されるので、その都市にはビットは必要ありません。

于 2013-02-22T07:15:49.007 に答える