迷路
テンプレート:Otheruseslist テンプレート:出典の明記
迷路（めいろ）は、複雑に入り組んだ道を抜けて、目的地、ゴールまで辿り着くことを目指すゲーム、パズルのこと。「迷路」は英語で「maze（メイズ）」と言うので、特に紙の上で解くパズルとしてのそれは迷図（めいず）という当て字をされることもある。
作為的に作られたものを指すことが多いが、山道や繁華街の路地などの実在する入り組んだ道を指して、比喩的に「迷路」と言うこともある。部屋や通路が入り組んだ建築物は、特に迷宮とも呼ばれる。
目次
迷路の解法
右手法（左手法）
右側の壁に手を付いて、ひたすら壁沿いに進むという方法である（右側の壁の代わりに左側の壁に手をついても本質的には同じ、この場合は左手法という）。
壁の切れ目は迷路の入口と出口にしかないので、右手法を使うと最終的には、入口に戻ってしまうか出口に到達するかのいずれかになる。
最短経路でゴールにたどりつけるとは限らないが、最悪でも壁の長さ分だけ歩けば終了する。
平面的な迷路であれば、右手法を使うと必ず出口にたどり着く。 しかし、迷路のスタートないしゴールが迷路の中にあったり、あるいは迷路が立体的だったりした場合は、右手法の結果スタート地点に戻ってしまう事もありうる。
またゴール以外にダミーの出口があると、そちらに行ってしまう事もあるが、この場合はダミーの出口を無視して右手法を続ければ良い。
Windowsのスクリーンセーバーのひとつ、「3D迷路」は、この方法で迷路を進んでいる。
トレモー・アルゴリズム
あらゆる迷路を解くことが出来る解法として「トレモー・アルゴリズム」が知られている。この解法は19世紀のフランスの数学者エドゥアール・リュカによって紹介された。この方法は本質的には「全パターンの経路をしらみ潰し的に試す」というものであるが、チョークで地面に自分が通った跡を残す事で、しらみ潰しを効率的にできる点に特徴がある。
この方法では、迷路上の各々の通路は最大2回しか通らない（試しに進んでみる場合と、諦めて戻る場合の2回）。よって最悪でも通路の長さの合計値の2倍歩けば、ゴールにたどり着く。
アルゴリズムの詳細は以下の通り。以下のアルゴリズムで、迷路を歩くときは常にチョークで地面に「→→→→」と描き続ける。また、まだチョーク跡のつけられていない通路を歩くのを「通路を進む」と言い、すでにチョーク跡「→→→→」がつけられた通路を「←←←←」の方向へと進むのを「通路を戻る」と呼ぶ。
簡単のため、スタート地点が迷路中の分岐点の一つにあると仮定して話を進める。
- 任意に選んだ通路を進む。
- そのうち分岐点か行き止まりかゴールにたどり着く。
- まだ通っていない（＝チョークの跡がない）分岐点に辿り着いたら、通ってきた通路以外の任意の通路を選び、そこを進む。→2
- すでに通った（＝チョークの跡がある）分岐点に辿り着いたら、進んできた通路を戻る。→2
- 通路を戻っているときに分岐点に辿り着いた場合（注：戻っているときなので、この分岐点は必ず過去に通っている）
- まだ通っていない（＝チョークの跡がない）通路が残っていたら、その通路へと進む。→1
- 全ての通路にチョークの跡があったら、各通路を眺める。ほとんどの通路は、通路へと伸びて行くチョーク跡「→→→→」および通路から引き返して来るチョーク跡「←←←←」があるが、一つだけ「←←←←」の無い通路（＝この分岐点に最初に来たときに通った通路）がある。その通路を引返す。→2
- ただし今いる分岐点がスタート地点だった場合は、全ての通路に「→→→→」と「←←←←」の両方が書いてある事もありうる。この場合ゴールに到達する方法が無いので、諦めて終了。
- 行き止まりに辿り着いたら、来た道を戻る。→2
- ゴールにたどり着いたら終了。
スタート地点が迷路中の分岐点の一つに無い場合も、スタート地点が分岐点だとみなして上述のアルゴリズムが使うことが出来る。つまり、スタート地点が通路の中央にある場合は、スタート地点は2方向に分岐する分岐点だとみなす。スタート地点が迷路の行き止まりにあるときは、スタート地点は一方向にだけ分岐する分岐点だと考える。
オーア・アルゴリズム
「オーア・アルゴリズム」は、1959年にイェール大学のオイスティン・オーアによって紹介されたものである。スタートの近くにある分岐点から探索を始めて、徐々に探索範囲を広めていくというものである。このアルゴリズムは本質的に、最短経路問題におけるダイクストラのアルゴリズムと同一である。
このアルゴリズムの利点は、スタートからゴールまでに通る分岐点の数が最小の経路(ただしスタートからゴールまでの距離は必ずしも最短ではない)を発見出来ることと、 無限に広い（ゴールまでの距離は有限の）迷路でも有限の時間でゴールに辿り着くことが出来ることである。 一方欠点は同じ通路をかなり多くの回数いったりきたりしなければならない為、右手法やトレモー・アルゴリズムに比べると移動距離が長くなる事である。
（「右手法」や「トレモー・アルゴリズム」では、無限に広い迷路では無限の探索が必要となる可能性がある。 またこれらのアルゴリズムでは同じ通路は最大でも2回しか通らない。）
- オーア・アルゴリズムの概説
- スタートから最初の分岐点まで歩く。最初の分岐点から出ている全ての通路を辿り、分岐点、行き止まりに辿りついたら引き返す。
- もし、ある通路が行き止まりだったり、もう既に行ったことのある分岐点（もしくは同じ分岐点）に繋がっていたら、その通路を通らないように目印を付ける。
- その分岐点から出ている全ての通路を探索したら、一旦、スタートに戻り、スタートから行くことが出来る別の最初の分岐点にて、同様の探索を行う。
- スタートから最初の分岐点を全て探索したら、次にスタートから最初の分岐点を通過した、次の分岐点を全て探索する。
- このように、スタートから「n番目」の分岐点を「n=0,1,2,3,4,5...」というように、しらみ潰しに探索していく。
その他の解法
紙の上で解く場合は、行き止まりを全て塗り潰せば、結果的に正解が浮かび上がる。
迷路園
庭園の生け垣や、農地のトウモロコシやコムギを利用して迷路が作られることもある。また、純粋に娯楽施設として板塀で囲った迷路園も数多く存在する。遊園地のミラーハウスもこのような迷路のひとつである。リアル型脱出ゲームとして各種イベントなどでも開催されている。
ヨーロッパの迷路園
ヨーロッパでは古くから修道院の庭などに迷路園が作られた。イングランド王ヘンリー2世は、愛人を迷路園の中の隠れ家に住まわせ、妻のアリエノールから匿ったとされる。しかし、アリエノールは紐を用いて迷路を解き、愛人を毒殺してしまったという。
ルネサンス以降は、宮殿に付属して作られた。フランス王ルイ14世は、1672年、ヴェルサイユ宮殿の庭に迷路園を作った。この迷路園は1775年に解体されている。イギリスではテューダー朝やステュアート朝の時代に盛んに作られた。イギリスのハンプトン・コート宮殿の庭にあるものなど、現在も多くの迷路園が残っている。
日本の迷路園
1876年、植木屋の川本友吉によって神奈川県横浜市老松町の花屋敷（遊園地）に作られたものが日本で最初の迷路園である[1]。これをきっかけに、日本各地に迷路園が造られた。成島柳北の記述から、当時、東京の向島ではマツを利用して、京都や大阪では竹林を利用して立体迷路を作り、客を遊ばせていたことが知られている。
1980年代ころには巨大迷路ブームが起こり、各地の娯楽施設に迷路が作られた。これらの多くはスチュワート・ランズボローが手がけたことから由来する「ランズボロー迷路」と呼ばれるもので、可動式の板塀を利用しており、そのため定期的に設計を変えて違うパターンの迷路を提供することが出来た。立体交差やチェックポイント、緊急避難用のゲートなどを設け、幅広い年齢が楽しめる手軽な娯楽として成立した。興業者側の利点として設置費用や撤去費用の安さ、維持管理の容易さなどが挙げられる。最盛期には、日本各地に100個以上の巨大迷路があったが、結果として一過性のブームに終わり、現在では二十箇所程度にまで激減した。しかしながらわずかに残っている施設は適宜改修やリニューアルが行われ根強い人気を誇っている。近年は迷路とアスレチックが組み合わされたアスレチック迷路や、複層型立体迷路と呼ばれる、複数階建ての建物の内部が迷路になっており、階を上がったり下りたりしながら攻略を目指す迷路施設などのアレンジ巨大迷路も作られている。
- 現在も営業している巨大迷路
- 仙台ハイランド（宮城県仙台市） 遊園内施設
- 日光江戸村忍者からくり格言迷路（栃木県日光市） 遊園内施設
- 巨大迷路パラディアム（栃木県日光市） 有料 迷路面積3500m2
- 渋川スカイランドパーク（群馬県渋川市） 遊園内施設
- わらび平森林公園キャンプ場（群馬県高崎市） 有料 春-秋季限定
- 国営ひたち海浜公園（茨城県ひたちなか市） 遊園内施設 迷路面積1230m2
- みずほの村市場ひまわり迷路（茨城県つくば市） 有料 夏季限定
- 清水公園アクアベンチャー（千葉県野田市） 有料
- ロマンの森共和国（千葉県君津市） 遊園内施設
- さがみ湖リゾート プレジャーフォレスト（神奈川県相模原市） 遊園内施設、多数面
- こだまの森（長野県木曽郡木祖村） 有料
- ぐりんぱ（静岡県裾野市） 遊園内施設
- 日本サイクルスポーツセンター（静岡県伊豆市） 遊園内施設
- 白浜エネルギーランド（和歌山県西牟婁郡白浜町） 遊園内施設、2面
- 東条湖おもちゃ王国（兵庫県加東市） 遊園内施設
- 匹見町の巨大迷路MAZE（島根県益田市） 有料 迷路面積7000m2
- 心の駅 陽だまりの丘 ドラゴンメイズ(島根県雲南市) 有料 迷路面積2000m2
- 香川県立飯山高等学校ひまわり迷路（香川県丸亀市） 無料 夏季限定
- 海の中道海浜公園（福岡県福岡市） 遊園内施設 迷路面積240m2
ペンシルパズルとしての迷路
紙の上で解くペンシルパズルとしての迷路には、多くのバリエーションがある。一見すると普通の絵画だが、実は輪郭線に隙間があって迷路になっているものや、正解のルートを塗り潰すことで絵が浮かび上がるものもある。日本のパズル作家では、前者は吉岡博、後者は相羽高徳、湯沢一之らが雑誌などで数多く発表している。
動物学における迷路
動物心理学や動物行動学では、記憶や学習行動などの研究において、動物に迷路を通らせる実験を行うことがある。このような実験を「迷路実験（迷路学習実験）」と呼ぶ。
脚注
関連項目
外部リンク
- テンプレート:脳科学辞典 動物行動実験に使われる迷路に関する解説。
