最小全域有向木 - Chu-Liu/Edmondsのアルゴリズム

シェアする

  • このエントリーをはてなブックマークに追加

こんにちは。

最近、競技プログラミングに関して、グラフアルゴリズムの知識を付けようと思い、AOJのLibrary of Graph Algorithmsを解いています。

そこで、最小全域有向木の問題を解いたので、解説を書いておきます。

問題はこちら→ Minimum-Cost Arborescence

最小全域有向木とは

コスト(重み)付きの有向グラフ(ネットワーク)と根ノード番号が与えられます。

指定された根ノードを根とする有向木(与えられたグラフの部分木)のうち、使用した辺の合計コストが最小になるものが、最小全域有向木です。

有向木では、全てのノードについて、根から有向道を通って辿り着ける必要があります。

今回の問題では、最小の合計コストを出力します(木の形は出力不要)。

無向グラフの場合は、最小全域木(Minimun Spanning Tree)となり、クラスカル法やプリム法(ヤルニーク・プリムのアルゴリズム)で、割とシンプルに(貪欲に)解けます。

しかし、最小全域有向木の場合は、なかなか単純にはいきません。

Chu-Liu/Edmondsのアルゴリズム

指定された根を持つ有向木なので、始点から広げていくプリム法で解けるんじゃないかと思いましたが、下図の入力に見事に撃墜されました。

プリム法だと、A,B,Cの順で選択してしまいます。

しかし、正解はA,C,Dです。

無向グラフならA,B,Dが正解になりますが、有向グラフなのでプリム法では失敗します。

そこで調べてみると"Chu-Liu/Edmondsのアルゴリズム"なるものが存在するようです。

次の2つのページを参考にしました。

https://gist.github.com/tjkendev/231897301fde67d4a81f51c3f0873936

1つめのはてなブログの記事で詳しく説明されていますので、その記事の補足と言う形で、図を使いながら解説を書きたいと思います。

有向木においては、根以外のすべてのノードの入り次数が1になります。つまり、根以外のすべてのノードについて、そこに入ってくる辺は1つです。

したがって、根以外のすべてのノードについて、「そこに入ってくる辺のうち、最もコストが低いもの」を選んだ結果、全域有向木となっていれば、それが解になります。

例えば下図。

赤と黒の矢印が与えられたグラフ、赤い矢印が選んだ辺(根以外の各ノードにおける、コスト最小の入辺)です。

この場合、赤いノードだけで有向木になっているので、これがそのまま解になります。(答えは1+2+6+7+5+4=25です)

ただし、いつも上手くいくわけではありません。

上図において、赤い辺の合計コストは28です。

上図では、赤い辺が全域有向木になっていません。閉路があるからです。

閉路に突入する辺を選ぶ必要があるので、この閉路の中のどれかの辺を諦めなければなりません。

例えば、コスト4の辺(0,2)を選ぶと、頂点2の入り次数の制約から、コスト3の辺(4,2)を諦めなければなりません。全体のコストは1増えます。

コスト5の辺(1,2)を選ぶと、コスト3の辺(4,2)を諦め、全体のコストが2増えます。

コスト3の辺(6,7)を選ぶと、コスト1の辺(5,7)を諦め、全体のコストが2増えます。

これらの中でどれが一番良いかを考えます。

ちなみに、複数の辺を諦めるのは損です。諦める辺は1つで十分だからです。2つ諦めて有向木を作る場合、そのどちらか一方を諦めるだけでも有向木ができます。

ここで大事なのは「どこから閉路に入るか」です。

さらに、閉路に入る辺それぞれに「その辺を選ぶと全体コストがどれだけ増えるか」という値があります。これは「(その辺のコスト)-(その辺の終点に入る、閉路内の辺のコスト)」で得られます。

また、閉路内にある、この時点で使用されていない辺は、必ず使いません。上図でいうとコスト7の辺(5,4)がこれに当たります。

つまり、閉路内の辺は全く考慮する必要が無いので、閉路を一つのものとして扱ってみます(これを閉路の縮約と呼びます)。

始点も終点も同じ閉路内にある辺は無視します(消します)。

閉路から出ていく辺はそのまま残します。

閉路に入る辺は、「その辺を選び、閉路内の辺を1つ諦めることで増えるコスト」でコストを書き換えて使用します。

すると、右下図のようになります(左下図は上図と同じものを再掲しています)。

 

閉路を頂点9として、グラフを書き換えています。

閉路内の辺(閉路の辺4本と未使用の辺1本)は無視します。

閉路に入る辺は、コストを書き換えています(右上図でx-x=xと書かれているもの)。

他の辺は、そのまま残してあります。

辺(9,8)など、同じ始点・終点を繋ぐ辺が複数あります(多重辺があります)が、そのままにしておいて問題ありません。

こうしてできた新たなグラフについて、もう一度最初の操作を行うと、下図になります。

これは全域有向木になっています。

この有向木の合計コストは14ですが、これは答えではありません。

閉路に使用した辺を無視しているからです。

元々の(有向木になっていない段階の)合計コストは28でした。

これは、閉路に無関係な辺のコスト13+閉路コスト15でした。

そのうち、前者の辺は縮約後にも全て残っています。

後者は縮約で全て消えました。

さらに、閉路を解消するために、辺(0,2)(縮約後の辺(0,9))を使用したので、総コストが1増えました。

したがって、最終的な合計コストは、

閉路に無関係なコスト13+閉路の15+閉路解消で増えた1=29

となるはずです。

実際、得られた有向木の、縮約後の閉路(頂点9)を元の閉路に戻すと、下図のようになります。

辺(0,2)を使用したので、辺(4,2)を諦めています。

これは全域有向木で、合計コストは29となります。

結局、合計コストは

縮約後のグラフにおける最小全域有向木のコスト14+縮約した閉路のコスト15

となっています。

つまり、最小全域有向木の合計コストは、以下の再帰アルゴリズムで得られます。

縮約した閉路の合計コストを足していく変数res=0を用意しておきます。

  1. 根以外の全頂点について、そこに入る最小コスト辺を選ぶ
  2. 閉路を探す
    1. 閉路があれば、縮約(グループ分け)
  3. 閉路が1つも見つからなければ、最小全域有向木が得られたので、合計コストを出力
  4. 見つかった閉路全ての合計コストをresに加算
  5. 閉路に入る辺のコストを計算し直す
  6. 作成されたグラフについて、このアルゴリズムを適用して最小全域有向木のコストを計算
  7. 得られたコストにresを加算したものを出力

実際の実装では、縮約したノードを9とすると不都合があるので、新たにノード番号を割り振ります。

上図のようになります。コードではgroup[]で新たな番号を管理しています。

上図のあと、グループ2の4つの頂点をまとめて頂点2としてグラフを再構成します。

実装

こちら↓をそのままC++に書き換えました。

https://gist.github.com/tjkendev/231897301fde67d4a81f51c3f0873936

実装において、まず必要なのが、閉路の検出です。

最初に、根以外の各頂点について「そこに入る最もコストの小さい辺」を選びます。

これをEdge型のmins[頂点番号]とします。

Edge型とは、pair<int, pair<int, int>>のことです。(コスト、(始点、終点))として扱います。こうすると、pairの性質から、コストで比較が可能になります。

この状態で、根以外の全ての頂点について入り次数が1なので、ある点からバックしていくと、必ず一本道になります(深さ優先等の探索が不要になります)。

したがって、適当な点からスタートして、バックしていき、訪れた点をvector<int> chainに追加しながらused[訪れた頂点番号]をtrueにしていきます。訪れた点がすでにusedなら終了。

終了時に訪れる予定だった点(curに入っている)がchainに含まれていれば、閉路になります。

詳しくは、

を参考にしてください。

実装したC++コードは以下になります。

スポンサーリンク
レクタングル(大)
レクタングル(大)

シェアする

  • このエントリーをはてなブックマークに追加

フォローする