algorithm - グラフ内のすべてのノードを調べる

Question

N 個のノード (1..N から番号付け) と、対 (A,B) で構成される M 個の双方向エッジを持つ接続グラフが与えられます。エッジは重み付けされていません。

ノード 1 から始まる K 人がいて、グラフのすべてのノードを調査したいと考えています。人が 1 つのノードからその隣のノードに移動するのに 1 単位の時間がかかります。

すべてのノードを探索するにはどのくらいの時間がかかりますか? 最小トラバーサル時間を計算するための効率的なアルゴリズムを探していますが、残念ながらそれは NP 完全問題です。(ただし、エッジの数と人数の制約は小さいです)。

Answer 1

K が 1 であると仮定します。この場合、最小化の問題は、すべてのノードに少なくとも 1 回接触する最小の長さのパスを見つけることになります。

同じノードを持ち、重みが元のグラフ内のノード間の最小距離である 2 つのノードごとにエッジを持つ、新しい重み付きグラフ G' を作成すると、G 内のすべてのノードを通る最小長パスは、最小長ハミルトニアンです。巡回セールスマン問題である G' を通る経路は、NP 完全であることがよく知られています。

したがって、K の少なくとも 1 つの値について、問題は NP 完全です。ただし、K の値が大きい場合 (たとえば、N 以上)、最小スパニング ツリーを構築して最も遠い要素の距離を見つけることができるため、はるかに短い時間で最小解を生成できます。K の値が小さい場合にそのような単純化された解があるかどうかは疑問ですが、合理的な解を見つけるためのヒューリスティックとして MST を使用することは間違いありません。