ARC029「高橋君と国家」 - クラスカル法

シェアする

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

こんばんは。

きのうとおととい、2日連続でポッピンQの記事を書きましたが、今日は違います。

最近就職活動と大学の課題で忙しくてブログを書けていなかったので、半月ほど前に解いたクラスカル法を使う問題について書きます。

クラスカル法については大学の講義で習っていたので、バイトの休憩時間に30分ほどでコーディングできました。Union-Find木は過去の自分の提出コードから引っ張ってきました(そのときにメインノートPCではなくタブレットPCで解いたため)。

ちなみにポッピンQについては、本日アニメイトに行って、映画の半券を提示するともらえるポストカードを貰ってきました。

それと、梅田での応援上映2回目が決定し、本日24時から座席予約開始とのことなので、予約します。

最小全域木とは

各辺にコスト(重み)がついてあるグラフが与えられたとします(グラフは連結です)。

このとき、与えられたグラフの部分グラフで、全てのノードを含み、辺のループが存在しないものを「全域木」と呼びます。

与えられたグラフのノード数がNなら、全域木の辺の数はN-1本となります。

一般に1つのグラフの全域木は複数ありますが、その中で、全域木に含まれる辺のコストの合計が最も少なくなるような全域木のことを「最小全域木」と呼びます。

この最小全域木を求めるためのアルゴリズムの一つがクラスカル法です。

クラスカル法とは

最小全域木を求めるときに、貪欲法として以下の戦略が考えられます。

①まだ使っていない辺の中から最もコストが小さいものを選ぶ

②それを採用すると、それまでに採用した辺との関係でループができてしまう場合、選んだ辺を捨てる

③選んだ辺を採用してもループができない場合、それを採用する。

これをN-1回繰り返すと、コストが小さい全域木ができそうです。

つまり、毎回「選べる辺の中で一番良い辺を選ぶ」という操作を行うわけです。

実は、この単純なアルゴリズムで最小全域木が得られることが分かっています。

これをクラスカル法と呼びます。

最小全域木を求めるアルゴリズムには、クラスカル法の他にプリム法(ヤルニーク・プリム法)と呼ばれるものがあります。これも「一番良い辺を選ぶ」という貪欲法ですが、途中も木になるように更新していくもので、ダイクストラ法に似た実装になります。

ループができるかどうかは、Union-Find木を用いることで簡単に判定できます。

辺を採用するたびに、採用した辺の端点をUniteすることで全ノードの連結関係を記録しておけば、新たに採用しようとしている辺の端点がUnion-Find木において同じグループに属している場合は、ループができてしまいます。

Union-Find木において同じグループに属しているノードは、構成している途中の部分グラフにおいて連結である、すなわち互いに行き来するパスがあるということです。

その2点を接続する辺を追加すると、ループができてしまいますね。

ということで、ループ判定にはUnion-Find木の同属判定を用います。

また、「最もコストが小さい辺を選ぶ」は、優先度付きキューを使えます。

問題概要

問題文はこちらです。

処理が二つあると面倒なので、こういうときは「片方の処理をもう片方で言い換える」という発想が役に立つことがあります。

今回は、都市に交易所を建てる処理と、都市間を結ぶ道を舗装する処理がありますが、前者の処理を「その都市から"交易所"という都市に向かう道を舗装する」と言い換えることができます。

こうすると、「都市iと交易所を結ぶ道の舗装コストがc_i」と言えます。

また、「全ての都市から交易所がある都市へ行ける」は「全ての都市から"交易所"という都市へ行ける」と言い換えられます。

さらに、これは「全ての都市と交易所が連結になる」すなわち「交易所を含む全ての都市が連結である」というように言い換えられます。

こうなると、求めるものは「交易所を含む全ての都市が連結になるように、いくつかの道を舗装するときの、舗装コストの合計の最小値」になります。

まさしく最小全域木です。

N個の都市を都市[0]~都市[N-1]とし、交易所を都市[N]として、N+1個の都市をノードとする重み付きグラフを作り、クラスカル法を適用します。

これを実装したのが以下のコードです。

期末試験期間が終われば、競プロ関係の記事も積極的に書いていきたいと思います。では。

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

シェアする

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

フォローする