脱出の日
「脱出の日」は1815年のこの日にエルバ島に流刑されていたナポレオンが島を脱出してパリに向かったことが由来です。
流刑とはいわゆる「島流し」のことで、遠方の島に取り残され、自分一人の力だけで生きていかなくてはらないという死刑と同じぐらいの厳罰であり、死刑への反発の声が大きいと予想された場合や、助命を嘆願された際に適用されていました。
流刑者の大半は流刑中の海上や流刑先でその人生を終える事となります。
迷路を脱出する方法
過去に様々な状況から脱出を試みたのはナポレオンだけではありません。
ありがちなのは牢屋や監獄などからの脱出、戦時中の収容所からの脱出などですが、当然脱出を防ぐための措置が取られており非常に困難です。
我々一般人が手軽に脱出の気分を味わいたいのであれば“迷路”などがあります。
二次元上の紙でやるものや、テーマパークには実際に歩いて脱出するものも目にしますよね。
この迷路においても、なんとか効率よく迷わずに脱出までこぎつけないか、様々な方法が考案されました。
よく聞くのが“右手法”というもので、右側の壁に手を付いてひたすら壁沿いに進むという方法です。(左側の壁に手をついても本質的には同じでありこの場合は左手法と呼びます)
壁の切れ目は迷路の入口と出口にしかないので、右手法を使うと最終的には入口に戻ってしまうか出口に到達するかのいずれかになるはずというもので、最短経路で脱出できるとは限らないものの最悪でも壁の長さ分だけ歩けば終了します。
平面的な迷路であればこの右手法を使うと必ず出口にたどり着くはずなのですが、迷路のスタートないしゴールが迷路の中にあったり、あるいは迷路が立体的だったりした場合は脱出できない可能性があるのです。
Windowsのスクリーンセーバーのひとつである“3D迷路”は、この方法で迷路を進んでいます。
“トレモー・アルゴリズム”というものも、あらゆる迷路を解くことが出来る解法として知られています。
この解法は19世紀のフランスの数学者エドゥアール・リュカによって紹介されたもので、この方法は本質的には“全パターンの経路をしらみ潰し的に試す”というものですが、チョークなどで地面に自分が通った跡を残す事でしらみ潰しを効率的にできる点がその特徴です。
この方法では迷路上の各々の通路は最大2回しか通らない(試しに進んでみる場合と、諦めて戻る場合の2回)ので、最悪でも通路の長さの合計値の2倍歩けばゴールにたどり着きます。
“オーア・アルゴリズム”という方法が1959年にイェール大学のオイスティン・オーアによって紹介されました。
スタートの近くにある分岐点から探索を始めて、徐々に探索範囲を広めていくというもので、その本質は最短経路問題におけるダイクストラのアルゴリズムと同一です。
このアルゴリズムの利点は、スタートからゴールまでに通る分岐点の数が最小の経路(ただしスタートからゴールまでの距離は必ずしも最短ではない)を発見出来ることと、無限に広い(ゴールまでの距離は有限の)迷路でも有限の時間でゴールに辿り着くことが出来ることにあります。
一方欠点は同じ通路をかなり多くの回数行き来しなければならない為、右手法やトレモー・アルゴリズムに比べると移動距離が長くなる事です。
右手法やトレモー・アルゴリズムでは同じ通路は最大でも2回しか通りませんが、無限に広い迷路では無限の探索が必要となる可能性があります。
それぞれの方法を調べて実際に迷路で試してみてはいかがでしょうか。
また、二次元の迷路を解く場合は行き止まりを全て塗り潰せば結果的に正解のルートが浮かび上がるので、こちらも試しみてください。
昨日は何の日？
2月25日
今日は何の日？
2月26日
・脱出の日
明日は何の日？
2月27日
