迷路

迷路（めいろ）とは、複雑に入り組んだ道を抜けて、目的地、ゴールまで辿り着くことを目指すゲーム、パズルのこと。「迷路」は英語で「maze（メイズ）」と言うので、特に紙の上で解くパズルとしてのそれは迷図（めいず）という当て字をされることもある。
二次元的に紙などに描かれたり、ディスプレイに表示されたりした迷路のほか、生垣で複雑な順路を構成した庭園や、立体迷路など人間が辿れる大きさの迷路もある。後者については「[[#迷路園|迷路園]]」で詳述する。
人為的に作られたものを指すことが多いものの、山道や繁華街の路地のように迷いやすい道を指して、比喩的に「迷路（のような）」と言うこともある。部屋や通路が入り組んだ建築物は、特に[[迷宮]]とも呼ばれる。
迷路の解法.
右手法（左手法）.
右側の壁に手を付いて、ひたすら壁沿いに進むという方法である（右側の壁の代わりに左側の壁に手をついても本質的には同じ、この場合は左手法と言う）。壁の切れ目は迷路の入口と出口にしかないので、右手法を使うと最終的には、入口に戻ってしまうか出口に到達するかのいずれかになる。最短経路でゴールにたどりつけるとは限らないが、最悪でも壁の長さ分だけ歩けば終了する。
平面的な迷路であれば、右手法を使うと必ず出口にたどり着く。しかし、迷路のスタートないしゴールが迷路の中にあったり、あるいは迷路が立体的だったりした場合は、右手法の結果スタート地点に戻ってしまう事もありうる。
またゴール以外にダミーの出口があると、そちらに行ってしまう事もあるが、この場合はダミーの出口を無視して右手法を続ければ良い。
[[Windows]]の[[スクリーンセーバー]]の一つ「3D迷路」は、この方法で迷路を進んでいる。
トレモー・アルゴリズム.
あらゆる迷路を解くことが出来る解法として「トレモー・アルゴリズム」が知られている。この解法は[[19世紀]]の[[フランス]]の数学者[[エドゥアール・リュカ]]によって紹介された。この方法は本質的には「全パターンの経路をしらみ潰し的に試す」というものであるが、[[チョーク]]で地面に自分が通った跡を残す事で、しらみ潰しを効率的にできる点に特徴がある。この方法では、迷路上の各々の通路は最大2回しか通らない（試しに進んでみる場合と、諦めて戻る場合の2回）。よって最悪でも通路の長さの合計値の2倍歩けば、ゴールに辿り着く。
[[アルゴリズム]]の詳細は以下の通り。以下のアルゴリズムで、迷路を歩くときは常にチョークで地面に「→→→→」と描き続ける。また、まだチョーク跡のつけられていない通路を歩くのを「通路を進む」と言い、既にチョーク跡「→→→→」がつけられた通路を「←←←←」の方向へと進むのを「通路を戻る」と呼ぶ。
簡単のため、スタート地点が迷路中の分岐点の一つにあると仮定して話を進める。
スタート地点が迷路中の分岐点の一つに無い場合も、スタート地点が分岐点だとみなして上述のアルゴリズムが使うことが出来る。つまり、スタート地点が通路の中央にある場合は、スタート地点は2方向に分岐する分岐点だとみなす。スタート地点が迷路の行き止まりにあるときは、スタート地点は一方向にだけ分岐する分岐点だと考える。
オーア・アルゴリズム.
「オーア・アルゴリズム」は、[[1959年]]に[[イェール大学]]の[[オイスティン・オーア]]によって紹介されたものである。スタートの近くにある分岐点から探索を始めて、徐々に探索範囲を広めていくというものである。このアルゴリズムは本質的に、[[最短経路問題]]における[[ダイクストラ法|ダイクストラのアルゴリズム]]と同一である。
このアルゴリズムの利点は、スタートからゴールまでに通る分岐点の数が最小の経路(ただしスタートからゴールまでの距離は必ずしも最短ではない)を発見出来ることと、無限に広い（ゴールまでの距離は有限の）迷路でも有限の時間でゴールに辿り着くことが出来ることである。一方欠点は同じ通路をかなり多くの回数いったりきたりしなければならない為、右手法やトレモー・アルゴリズムに比べると移動距離が長くなる事である（「右手法」や「トレモー・アルゴリズム」では、無限に広い迷路では無限の探索が必要となる可能性がある。またこれらのアルゴリズムでは同じ通路は最大でも2回しか通らない）。
その他の解法.
紙の上で解く場合は、行き止まりを全て塗り潰せば、結果的に正解が浮かび上がる。
[[画像:Maze01-01 original.png|center|行き止まりを全て塗り潰し、ルートが浮かび上がった。]]
迷路園.
庭園の生垣を利用したや[[芝|芝生]]を刈り込んで作られる[[芝生迷路]]、[[農地]]の[[トウモロコシ]]や[[コムギ]]を利用した[[コーンメイズ]]と呼ばれる迷路などが作られることもある。また、純粋に娯楽施設として板塀で囲った迷路園も数多く存在する。[[遊園地]]のミラーハウスもこのような迷路の一つであるである。この他、近年では[[脱出ゲーム#現実における「脱出ゲーム」|リアル型脱出ゲーム]]として各種イベントなどでも開催されている。
[[画像:Schönbusch4.jpg|right|250px|thumb|迷路園の例]]
ヨーロッパの迷路園.
[[ヨーロッパ]]では古くから[[修道院]]の庭などに迷路園が作られた。[[ヘンリー2世 (イングランド王)]]は、愛人を迷路園の中の隠れ家に住まわせ、妻の[[アリエノール・ダキテーヌ|アリエノール]]から匿ったとされる。しかし、アリエノールは紐を用いて迷路を解き、愛人を毒殺してしまったという。
[[ルネサンス]]以降は、[[宮殿]]に付属して作られた。[[ルイ14世 (フランス王)]]は、[[1672年]]、[[ヴェルサイユ宮殿]]の庭に迷路園を作った。この迷路園は[[1775年]]に解体されている。イギリスでは[[テューダー朝]]や[[ステュアート朝]]の時代に盛んに作られた。イギリスの[[ハンプトン・コート宮殿]]の庭にあるものなど、現在も多くの迷路園が残っている。
日本の迷路園.
[[江戸時代]]に、[[八幡の藪知らず]]の森を真似て、囲いで覆った土地に迷宮式の藪を作り、入場料を取って中に入らせ、無事に出て来られた者に賞品を出すという興行場が現れ、明治10年頃にもこれが復活して、「八幡不知（やわたしらず）」「八陣」「かくれ杉」などの名前で大流行した。
[[1876年]]、植木屋の川本友吉によって[[神奈川県]][[横浜市]][[老松町 (横浜市)|老松町]]の花屋敷（遊園地）に作られたものが日本で最初の迷路園である。これをきっかけに、日本各地に迷路園が造られた。[[成島柳北]]の記述から、当時、[[東京]]の[[向島 (墨田区)|向島]]では[[マツ]]を利用して、[[京都]]や[[大阪]]では[[竹林]]を利用して立体迷路を作り、客を遊ばせていたことが知られている。
[[1980年代]]頃には巨大迷路ブームが起こり、各地の娯楽施設に迷路が作られた。これらの多くは[[スチュワート・ランズボロー]]が手がけたことから由来する「ランズボロー迷路」と呼ばれるもので、可動式の板塀を利用しており、そのため定期的に設計を変えて違うパターンの迷路を提供することが出来た。立体交差やチェックポイント、緊急避難用のゲートなどを設け、幅広い年齢が楽しめる手軽な娯楽として成立した。興業者側の利点として設置費用や撤去費用の安さ、維持管理の容易さなどが挙げられる。最盛期には、日本各地に100個以上の巨大迷路が存在したものの、結果として一過性のブームに終わり、現在では20箇所程度にまで激減した。しかしながらわずかに残っている施設は適宜改修やリニューアルが行われ根強い人気を誇っている。近年は迷路と[[アスレチック]]が組み合わされたアスレチック迷路や、複層型立体迷路と呼ばれる、複数階建ての建物の内部が迷路になっており、階を上がったり下りたりしながら攻略を目指す迷路施設などのアレンジ巨大迷路も作られている。
石兵八陣.
[[諸葛亮]]が考案したとされる、「[[石兵八陣]]」と呼ばれる石造建築群によって構成された、迷路状のものと考えられる架空の罠。
ゲームとしての迷路.
[[File:Labyrinth of Failure.jpg|thumb|盤面を傾けボールを誘導して穴に入れるゲーム。ゲームイベントから]]
ペンシルパズル.
紙の上で解く[[ペンシルパズル]]としての迷路には、多くのバリエーションがある。一見すると普通の絵画だが、実は輪郭線に隙間があって迷路になっているものや、正解のルートを塗り潰すことで絵が浮かび上がるものもある。日本のパズル作家では、前者は[[吉岡博]]、後者は[[相羽高徳]]、[[湯沢一之]]らが雑誌などで数多く発表している。海外では、ヴラディミイル・コズィアキン、グレッグ・ブライト、らがそれぞれを発表している。
動物学における迷路.
[[動物心理学]]や[[動物行動学]]では、[[記憶]]や[[学習行動]]などの研究において、動物に迷路を通らせる実験を行うことがある。このような実験を「[[迷路実験]]（迷路学習実験）」と呼ぶ。
外部リンク.
[[Category:迷路|*]]
[[Category:アトラクション]]
[[Category:パズル]]