木の頂点被覆問題は次のとおりです。
入力:非巡回単純無向グラフ G
出力:すべてのエッジ uv について、u ∈ W または v ∈ W となるような頂点 W の集合。W のサイズを最小化したい。
私の貪欲なアルゴリズムは、W = ∅ を初期化し、G が空でない間、次の手順を繰り返すことです。L を G の葉の頂点とする。N(L) を L のある頂点に隣接する頂点の集合とする。W = W ∪ N(L) を更新する。頂点 L ∪ N(L) とそれらの入射エッジを G から削除します。
このアルゴリズムは、これまでに試したすべてのケースで機能します。それが正しいことを証明するにはどうすればよいですか？これが私がこれまでに持っているものです。
最適解である別の集合 S があるとします。矛盾して、S がすべてのエッジをカバーしていないか、S が貪欲なアルゴリズムによって生成されたものと同じセットであることを立証したいと考えています。
これは妥当な出発点ですが、2 つの問題が見られます。まず、最適解は一意ではない可能性があります。a-b-c-d3 つの最適解がある 4 つの頂点パス を考えてみましょう{a,c}, {b,c}, {b,d}。2 番目に (おそらく既にこれを実行しているはずですが、そうは言っていません)、ツリーがルート化されていることを考慮する必要があります。a-bそれ以外の場合、たとえばグラフでは と がL = {a,b}ありN(L) = {b,a}、生成された頂点カバーは でありW = {b,a}、これは最適ではありません。ルートとして指定aすることにより、定義上、葉のセットから除外されます。
ループを含むプログラムの正しさを正式に証明するには、帰納法を使用してループ不変条件を確立することをお勧めします。2つ提案させてください。
すべての時間 t (ここで、時間 = ループの反復回数) について、時間 t における G の残りを G(t) とし、時間 t における W の値を W(t) とします。G(t) の頂点被覆 X ごとに、集合 W(t) ∪ X は G(0) の頂点被覆であり、0 は開始時刻です。
すべての時間 t に対して、サブセットとして W(t) を含む最適解が存在します。
T を終了時刻とします。G(T) は空のグラフであるため、X = ∅ は G(T) の有効な頂点カバーであるため、不変式 #1 は W(T) が G(0) の頂点カバーであることを確立します。不変式 #2 は、W(T) が何らかの最適解に含まれていることを確立します。W(T) 自体が頂点カバーであるため、W(T) 自体がその最適解に違いありません。
不変式 #2 を証明する帰納的ステップは、W(t-1) を含むが W(t) を含まない最適解が与えられた場合、それを W(t) を含む別の最適解に変換することです。これには、葉の隣人を葉の上に置くことが常に少なくとも同じくらい生産的であるという直感を形式化することが含まれます。