AHC020でシュタイナー木を作るような問題がでました。そこでプリム法ベースのシュタイナー木を作ることがあったのでその方法を説明します。
シュタイナー木とは
グラフとターミナルと呼ばれる頂点集合が与えられたとき、ターミナルを全てつなぐ木のことをシュタイナー木といいます。
ターミナルでない頂点はつないでもつながなくても構いません。
シュタイナー木のうちコストが最小のものを最小シュタイナー木といい、これを求めるアルゴリズムとしてDreyfus-Wagner法というものがあるらしいです。しかしこの方法はとても計算量が多いです。
今回紹介するプリム法ベースのシュタイナー木は、計算量は少なくて済みますがコストが最小になるとは限りません。ヒューリスティックコンテストにおける焼きなましの最中など、厳密さより速度が優先されるようなケースでの使用を想定しています。
プリム法ベースのシュタイナー木
手順
- ターミナル頂点の1つを選び、木に含めます。
- 木から最小コストでつなげられるターミナル頂点を選び、経路をつなぎます。経路上の頂点すべてを木に含みます。（コストと経路はダイクストラ法等で求めます）
- すべてのターミナル頂点が木に含まれるまで手順2を繰り返します。
例
まず、ターミナル頂点Aを木に含めます。
木から残りのターミナル頂点へのコストは
- 頂点B: 経路AFBでコスト10
- 頂点C: 経路AECでコスト12
最小コストでつなげる頂点Bとつなぎます。
木には頂点A,F,Bが含まれています。
木から残りのターミナル頂点へのコストは
- 頂点C: 経路FDCでコスト10
頂点Cとつなぎシュタイナー木の完成です。
総コストは20となりました。
これは最小コストではありません。以下の図のようにつなぐとコスト19の最小シュタイナー木が作れます。
この例では最初に木に含める頂点をCにすれば最小コストになりますが、与えられたグラフとターミナルによっては、どの頂点を最初に選んでも最小コストを達成できないケースもあります。
まだ木に含まれていない頂点のうち、最小コストでつなげられるものを木に含めていく、というところがプリム法と同じ考え方です。
以上。
