| 探索 | ノード | 結果 |
|---|---|---|
| 素のバックトラック | – | – |
| ワーンズドルフ順 | – | – |
| 行き止まりと連結性の検査 | – | – |
| 三つとも | – | – |
ハミルトン路エクスプローラー
1857 年、ウィリアム・ローワン・ハミルトンはひとつのパズルを考え出しました。正十二面体の辺をたどり、20 個の角をちょうど一度ずつ通って、出発した場所で終えるというものです。こうした経路は今ではハミルトン閉路と呼ばれます。確かめるのは簡単ですが、見つけるのはたいてい難しい問題です。ハミルトンの正十二面体や、チェス盤や、自分で描いたグラフの上で実際になぞってみるか、バックトラック探索が閉路を追う様子を眺め、入り込む行き止まりの数を数え、いくつかの簡単な検査で探索がどれだけ縮むかを確かめてください。 グラフと目標を選びます。出発点に戻る閉路か、一本の路かです。なぞる:頂点をクリックして始め、あとは隣の頂点を一つずつクリックします。破線の輪が次に行ける先を示します。最後の頂点をクリックするか「戻る」「元に戻す」で一歩戻り、「ヒント」は今からでも完成できる次の一手を教えます。探索:「実行」か「ステップ」でバックトラック探索が動きます。行き詰まるまで頂点を足し、行き詰まったら戻ります。赤い破線は戻った場所を示し、棒グラフは路の長さごとのノード数を数えます。始める前に頂点をクリックすると、どこから始めるかを選べます。チェックボックスで枝刈りを切り替え、「比較」は同じ探索を枝刈りあり・なしで走らせ、「すべて数える」は小さなグラフの閉路や路をすべて数えます。編集:クリックで頂点を追加、二つの頂点をクリックすると結んだり切り離したりでき、ドラッグで動かせます。「削除」は選んだ頂点を取り除きます。
使い方
- グラフを選びます。たとえばハミルトンの正十二面体、ピーターセングラフ、ナイト巡回など。あるいは「編集」で自分のグラフを描き、目標として閉路か路かを選びます。
- 「なぞる」では頂点をクリックして始め、隣の頂点を一つずつクリックします。「戻る」と「元に戻す」は一歩戻り、「ヒント」は今からでも完成できる次の一手を示します。
- 「探索」では「実行」か「ステップ」を押してバックトラックが経路を探す様子を眺め、枝刈りを切り替え、「比較」を押して各方式が必要とするノード数を見比べてください。
ハミルトンとオイラー
オイラー路はすべての辺を一度ずつ使い、ハミルトン路はすべての頂点を一度ずつ通ります。似て聞こえますが、振る舞いはまるで違います。連結グラフにオイラー路があるかどうかは、オイラーが 1736 年に示したとおり、奇数次数の頂点を数えれば決まります。0 個か 2 個のときにあります。ハミルトン路にはそうした規則が知られていません。グラフにハミルトン閉路があるかを決めるのは NP 完全で、リチャード・カープの 1972 年の 21 問の一つです。ですから速い方法が見つかれば、他の何千もの難問も速く解けることになります。あるのは、一部のグラフについて決着をつける条件です。1952 年のディラックの定理は、すべての頂点の次数が n/2 以上ならハミルトン閉路があると保証し、1960 年のオーレの定理は、隣接しない二頂点の次数の和が常に n 以上なら、と述べます。次数 1 の頂点、切断点、大きさの異なる二つの色のクラスは、いずれも閉路を否定します。
探索のしくみ
バックトラックは頂点を一つずつ足して路を作り、行き詰まると最後の一歩を取り消して次の隣接点を試します。ハミルトン閉路があれば必ず見つけますが、部分的な路の数は指数的に増えることがあります。ハミルトン閉路を持たない 5 × 5 の格子では、素のバックトラックは確信するまでに 153,745 ノードを調べます。二つの検査が見込みのない路を早く打ち切ります。空き隣接点が二つに満たない未訪問の頂点は、もう閉路に収まりません。また未訪問の頂点がばらばらの部分に分かれたら、一本の路ではそれらを覆えません。両方を使うと、同じ証明が 1,761 ノードで済みます。1823 年のワーンズドルフの規則は次の手が最も少ない隣接点から試し、8 × 8 のナイト巡回を角から 64 手で、行き止まり一つなしに見つけます。
よくある質問
ハミルトン路とハミルトン閉路の違いは何ですか。
ハミルトン路はグラフのすべての頂点をちょうど一度ずつ通ります。ハミルトン閉路は同じことをしたうえで、もう一本の辺を通って出発点に戻ります。ですからどの頂点からでも始められます。ハミルトン閉路を持つグラフにはハミルトン路もあります(閉路の辺を一本外せばよい)が、逆は成り立ちません。ピーターセングラフにはハミルトン路があり、ハミルトン閉路はありません。
正十二面体にハミルトン閉路はありますか。
あります。出発点と向きを問わず各閉路を一度と数えて 30 本です。ハミルトンは 1857 年にこれをイコシアンゲームにしました。平らに広げた正十二面体の 20 個の角に子音字を記した盤です。権利はロンドンの玩具商 John Jaques and Son に 25 ポンドで売られました。アプリの「すべて数える」は、この 30 本をおよそ 1,400 ノードで見つけます。
5 × 5 の格子にハミルトン閉路がないのはなぜですか。
25 個の点をチェス盤のように塗り分けてみてください。13 個が一方の色、12 個がもう一方になり、一歩進むごとに色が変わります。閉路は一周を通じて色が交互になるので、両方の色が同数必要ですが、13 と 12 ではそうなりません。同じ議論は点の数が奇数のどの格子にも、5 × 5 や 7 × 7 の盤上のナイトにも(ナイトは常にマスの色を変えます)、二つのクラスが 6 頂点と 5 頂点のハーシェルグラフにも当てはまります。ハミルトン路なら可能です。多いほうの色で始まり終わります。
ワーンズドルフの規則はどうやってナイト巡回を見つけるのですか。
H・C・フォン・ワーンズドルフは 1823 年に、次の手が最も少なくなるマスへ常にナイトを動かすことを提案しました。縁や角に近い、切り離されやすいマスが、ナイトがまだ入れるうちに早く訪れられます。この規則は経験則であって保証ではなく、同点のときは何らかの方法で決める必要がありますが、8 × 8 の盤ではたいてい戻らずに巡回を完成させます。このアプリのようにバックトラックと組み合わせると、5 × 5 以上の開いた巡回と、6 × 6 と 8 × 8 の盤の閉じた巡回を見つけます。
完全グラフにはハミルトン閉路がいくつありますか。
n ≥ 3 のとき (n − 1)!/2 本です。出発点の頂点を固定すると、残りの n − 1 個は任意の順に並べられ、各閉路は向きごとに二度数えられます。K₆ は 5!/2 = 60 本、K₁₀ は 181,440 本です。これが巡回セールスマンの選ぶべき周回路であり、だからこそ全部試すことがあっという間に不可能になるのです。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ