c++ - 巡回セールスマンのための再帰的動的計画法のアプローチ

Question

このページのコードがどのように機能するかを誰かが説明してくれることを期待していました: TSP-Recursive

疑似コードは解釈が難しく、動的プログラミングのアプローチにより、理解が特に困難になります。なぜビットシフトが必要なのですか？このアプローチはどのように一般化できますか (たとえば、場所の座標が与えられた場合、このアプローチを適用してその問題を解決できますか)?

Answer 1

変数graphは (数学的な意味での) マップです。2 つの都市 A と B が与えられた場合、A から Bgraph[A][B]までの距離は です。

変数dpは別のマップです。一連の都市 Sと都市 Aが与えられた場合、S内の各都市を訪れてA で終わるdp[S][A]最短の旅程は次のとおりです。

がgraph入力され、最終的な都市が選択されると、関数initは の距離の一部を入力しdpます。都市 A ごとに、A から始まり B だけを訪れる最短の旅程は、明らかにちょうどgraph[A][B]です。

この関数は、 S内のすべての都市を訪れ、X で終わるTSP( S, X )最短の旅程の長さを返します。その距離が に既にリストされている場合は、それを返します。それ以外の場合、 S内の各都市 A について、S内の他のすべての都市、次に A、次に Xを訪れる最短の旅の長さを計算します。それらの最短が答えであるため、関数はそれを に記録し、それを返します。dpdp

Answer 2

ビットシフトは、コードがセット、特に訪問した都市のセットを表すために int を使用しているためです。32 ビット整数の場合、int は最大 32 項目のセットを表すことができます。

基本操作は、

// add n to set
set |= 1 << n;

// remove n from set
set &= ~(1 << n);

// test set for n
if ((set&(1 << n)) != 0)
    ...