研究成果 > アルゴリズムのデモ > 最小木問題
この問題は,いくつかの地点が与えられ,すべての地点がつながるように 2地点間に枝を張るとします.(すべ てがつながるとは,どの 2地点も選ばれた枝を経由して行き来できることです.)ただし,枝には長さがあり, 選んだ枝の長さの総和を小さくすることがこの問題の目的です.
選んだ枝の中の 3本が 3角形を作っていると,1本は余分に選んでいることが分かります.どの 1本を除いても, そのことでつながらなくなる 2地点はでてきませんから.ですので 3角形でなくても,ぐるりと輪になるような 枝の集まりが含まれていると余分に選んでいることが分かります.よって,輪の形状を含まないですべての地点 をつなぐように枝を選んでくる,つまり,樹状に選んでくればよいことになります.樹状に選ばれた枝の集まり を木(tree)と呼びます.
この問題(最小木問題)では,すべての地点をつなぐ木で使った枝の長さの和を最小にするものを見つけま す.[ここで面白い性質があります.例えば,与えられた地点が 48地点の場合には,すべての地点をつな ぐ木を選ぶと,ちょうど 47本の枝を使います(どのように選んでも).一般に,n地点をすべてつなぐように木 を選ぶなら n-1本の枝が使われます.]
最小木問題を解く二つのアルゴリズム,クラスカル法,プリム法をデモの説明とともに紹介します.
クラスカル法のデモの説明
デモ Kruskal1 を選択してクリックすると 48地点の問題例が 呼び出されます(Kruskal2, Kruskal3, Kruskal4 はそれぞれ地点数 が 105, 225, 532 の問題例です).呼び出された画面には各地点が緑の点で描かれています.この問題例では どの2地点間も枝を張ることが許されています.枝の長さはそれの結ぶ2地点間の距離としています.
Kruskal により提案されたこの方法は,大変シンプルで,以下のルール K に従って,枝を選ぶ(張る)ことを 繰り返すだけです.
ルール K: 「現在,張ることのできる枝のうち最も長さの短いものを選ぶ」張ることのできる枝としては,まだ取り上げていない枝で「すでに選ばれている枝の集まりに追加して輪を作ら ないもの」になります.言い換えると,すべての枝(実際にはその候補)をその長さの小さい順に取り上げ,輪 を作らない限り,木の一部として採用します.
遊び方
- 緑のボタン[play]をクリックすると: 計算開始(あるいは一時停止からの再開). 枝の選択過程が連続的に表示される([play]ボタンは [pause]ボタンへ変更される).
- 緑のボタン[step]をクリックすると: 計算を1ステップだけ進める(変化を少しずつ見たいとき).
- 緑のボタン[pause]をクリックすると: 計算を一時停止.
- 緑のボタン[init]をクリックすると: 初期状態(枝が一つも選ばれていない状態)に戻す.
プリム法のデモの説明
デモ Prim1 を選択してクリックすると 48地点の問題例が呼び出 されます(Prim2, Prim3, Prim4 はそれぞれ地点数が 105, 225, 532 の問題例です).呼び出された画面には各地点が緑の点で描かれ,2地点間を結ぶことができる枝は青 色で表示されています(青色の線分の引かれていない2地点間には枝を張ることが許されない設定です).枝の 長さはそれの結ぶ 2地点間の距離としています.[青い線分が生成される過程が終わるまで少しお待ちください]
Primにより提案されたこの方法の動きは,最短路問題を解くダイクストラ法によく似ています.まず,出発地点 をひとつ適当に定めます.そしてこの出発地点から樹状に枝が伸びていくように枝を選択していき,すべての地 点をつないだら終了します.新しい点が出発点から到達可能になるように枝を選んで継ぎ足すので輪の発生は自 然に防がれます.もちろん,どの枝を継ぎ足していくかが大切で次の選択のルールを使います.
ルール P: 「すでに選んだ枝により出発地点からたどれる地点と残りの地点とつなぐ枝候補の中から,最も長さの短いものを選ぶ」このルール P に従えば,最終的に得られる木が枝の長さの和が最小であるものであることが保障されています.
遊び方
オレンジ色の点が出発地点です.計算開始前にカーソル移動をさせると好きな緑の地点を出発地点(オレンジ色) に選ぶことができます.
- 緑のボタン[play]をクリックすると: 一時停止からの再開.
- 緑のボタン[pause]をクリックすると: 計算を一時停止.
- 緑のボタン[step]をクリックすると: 計算を1ステップだけ進める(変化を少しずつ見たいとき.出発地点を選ぶ前は利用できない).
- 緑のボタン[init]をクリックすると: 初期状態(出発地点のみを選んだ状態)に戻す.
アルゴリズムは与えられた出発地点から先に述べたルールPで出発地点からの伸びる木に新しい枝を付け足して いきます.付け足された枝はオレンジ色に着色されます.