Gourt Home::Gourt :: 迷路
迷路（めいろ）とは、複雑に入り組んだ道、またはそういった道を抜けて目的地まで辿り着くことをめざすゲーム、パズル。英語で迷路をmaze（メイズ）というので、迷図（めいず）と当て字されることもある。
作為的に作られたものを指すことが多いが、山道や繁華街の路地などを指して比喩的に迷路と呼ぶ場合もある。建築物の場合は迷宮とも呼ばれる。
迷路園
庭園の生け垣、あるいは広大なとうもろこしや小麦の農地を利用して迷路が造られる。また純粋に娯楽施設として板塀で囲った迷路園も多く存在する。遊園地のミラーハウスもこういった迷路の一種である。
ヨーロッパの迷路園
ヨーロッパでは古くから修道院の庭などに迷路園がつくられた。イングランド王ヘンリー2世 (イングランド王)（1133年 - 1189年）は愛人を迷路園のなかの隠れ家に住まわせ、妻エレアノールからかくまったとされる。しかしエレアノールはひもを用いて迷路を解き、愛人を毒殺してしまったという。ルネサンス以降は宮殿に付属して作られた。ルイ14世はヴェルサイユ宮殿の庭に迷路園を作った（1672年、この迷路園は1775年に解体された）。イギリスではテューダー朝やステュアート朝の時代に盛んに作られた。イギリスのハンプトン・コート･パレスの庭にあるものなど、現在も多くの迷路園が残っている。日本の迷路園
1876年(明治9年)、植木屋の川本友吉によって横浜市内に造られたものが日本最初の迷路園である。これをきっかけに、日本各地に迷路園が造られた。成島柳北の記述から、当時東京の向島では松を利用して、京都・大阪では竹林を利用して立体迷路を造り客を遊ばせていたことが知られている。1980年代ころには巨大迷路ブームが起こり、各地の娯楽施設に迷路が造られた。これらの多くは「ランズボロー迷路」と呼ばれるもので、可動式の板塀を利用しており、そのため定期的に設計を変えて違うパターンの迷路を提供することができた。立体交差やチェックポイント、緊急避難用のゲートなどを設け、幅広い年齢が楽しめる手軽な娯楽として成立した。興業者側の利点として設置・撤去費用の安さ、維持管理の容易さなどが挙げられる。
ペンシルパズルとしての迷路
紙上で解くペンシルパズルとしての迷路には多くのバリエーションがある。一見すると普通の絵画だが実は輪郭線にすき間があけられており迷路になっているものや、正解のルートを塗りつぶすことで絵が浮かび上がるものもある。前者は日本のパズル作家では吉岡博、後者は相羽高徳、湯沢一之らが雑誌などで数多く発表した。
迷路の解法
右手法
迷路の解法として、右側または左側の壁に手をついてひたすら壁沿いに進むという方法がある。紙上と立体とにかかわらず有効で、「右手の法則」または「左手の法則」と通称される。ただし必ずしも最短距離を進めるとは限らない。また、スタート地点で手をついた壁がゴール地点と連続していなかった場合は永久に辿り着けなくなる。他にも途中通過しなければならないチェックポイントがある場合などにこの法則は通用しない。
トレモー・アルゴリズム
あらゆる迷路を解くことが出来る解法として、トレモー・アルゴリズムが知られている。この解法は19世紀のフランスの数学者エドゥアール・リュカによって紹介された。この方法では、ヒモやパンくずなどで自分が通った跡を記録しておく必要がある。- 迷路を適当に歩く。行き止まりまたは、今まで通ったことのある分岐点にたどり着いたら、以下のような行動をとる。
- 行き止まりにたどり着いた場合、直前の分岐点まで戻る。
- 分岐点にたどりつくまでの通路が、初めて通っていたものであった場合、直前の分岐点まで戻る。
- 分岐点にたどりつくまで通っていた通路が、今回以前に一度通ったことのあるものであった場合（この解法では同じ通路を通るのは最大2回である）、その分岐点から一度も行ったことの無い通路があれば、そこに向かう。そのような通路が無い場合、1度だけ通ったことのある通路に向かう。
- 以上のルールを守ることにより、確実にゴールを見つけることが出来る。ゴールを見つけるまで、全ての通路を逆向きに2度づつ通ることになる。
オーアのアルゴリズム
オーアのアルゴリズムは1959年にイェール大学のオイスティン･オーアによって紹介されたものである。スタート近傍の分岐点から探索を始め、徐々に探索範囲を広めていくというものである。すなわち、- スタートから最初の分岐点まで歩く。この分岐点から出ている全ての通路を辿り、分岐点または行き止まりに辿りついたら引き返す。もし、ある通路が行き止まりだったり、今まで行ったことのある分岐点（もしくは同じ分岐点）につながっていたら。その通路を2度と通らないように目印をつける。
- その分岐点から始まる全ての通路を探索したら、一旦スタートに戻り、スタートからいける別の最初の分岐点にて同様の探索を行う。
- スタートから最初の分岐点を全て探索したら、次にスタートから1つ分岐点を通過した次の分岐点を全て探索する。
- このようにスタートからn番目の分岐点をn=0,1,2,3....としらみつぶしに探索していく。
- スタートから最短経路の経路（距離は必ずしも最短ではないが、通る分岐点の数が最小の経路）を発見することが出来る。
- 無限に広い（しかしゴールまでの距離は有限の）迷路でも、有限の時間でゴールに辿りつくことが出来る。右手法やトレモー・アルゴリズムでは、無限に広い迷路では無限の探索が必要となる。
その他の方法
紙の上で解く場合は、行き止まりを全て塗りつぶせば結果的に正解が浮かび上がる。NP完全問題
迷路の解法は、いづれも総当り的に通路を調べる必要がある。このため、迷路の規模が大きくなるにつれて急激に複雑になり、コンピュータですら解くのが困難になる。迷路の解法はNP完全問題であることが知られている。関連項目
"迷路"
