加重無向グラフの 2 つのノード間の固定長パスを見つける方法について、アルゴリズムまたはさらなる研究へのポインタが必要です。
1 に答える
0
特定のノードから特定の長さの特定のノードへの単純なパスを見つけることは NP 完全です。ハミルトニアン サイクル問題はこのクラスの問題であり、NP 完全です。
エッジが重み付けされている場合、サブセット和の問題はこの問題の特殊なケースであるため、まだ NP 完全です。
どちらの場合も、パスを列挙し、単純ではないパスやtheta(b^len)予想時間内に長すぎるパスを枝刈りすることができますb。
繰り返されるエッジ (ウォークと呼ばれることもあります) を許可するパスの検索は、[長さ] の行列乗算で実行でき、O(v^3 * len)時間の複雑さを合計するか、それよりも優れています。
Aグラフの隣接行列を表現しましょう。次にA^len、頂点の各ペア間の長さ len のパスの数を保持します。乗算中に使用できます1+1 = 1（ブール加算-高度な行列乗算アルゴリズムでどのように機能するかはわかりません）。その場合、そのようなパスの存在のみを取得しますが、同時に整数オーバーフローを回避します。
A^1..A^len( )を準備しO(n^3 len)ます。次に、 の距離ごとdに、 の子であり、ターゲット ( ) までの長さのパスを持つ1..len頂点を見つけます。v[d]v[d-1]len-dO(n len)
A..A^lenそのようなパスが存在するかどうかだけを知る必要がある場合は、必要ありませんA^len。二乗乗算アルゴリズムO(n^3 log(len))によって時間内に計算することも、 Coppersmith-Winograd 行列乗算アルゴリズムと組み合わせて計算することもできます。O(n^2.37 log(len))
[node x distance]または、状態空間を検索して で実行することもできますO(n*b*len)。
于 2012-11-18T15:17:53.783 に答える