解剖学用語については「内耳」を、その他の用法については「迷路 (曖昧さ回避)」をご覧ください。
.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%;font-size:90%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}html.client-js body.skin-minerva .mw-parser-output .mbox-text-span{margin-left:23px!important}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。(このテンプレートの使い方)
出典検索?: "迷路"
迷路(めいろ)とは、複雑に入り組んだ道を抜けて、目的地、ゴールまで辿り着くことを目指すゲーム、パズルのこと。「迷路」は英語で「maze(メイズ)」と言うので、特に紙の上で解くパズルとしてのそれは迷図(めいず)という当て字をされることもある。
二次元的に紙などに描かれたり、ディスプレイに表示されたりした迷路のほか、生垣で複雑な順路を構成した庭園[1]や、立体迷路[2]など人間が辿れる大きさの迷路もある。後者については「迷路園」で詳述する。
人為的に作られたものを指すことが多いものの、山道や繁華街の路地のように迷いやすい道を指して、比喩的に「迷路(のような)」と言うこともある。部屋や通路が入り組んだ建築物は、特に迷宮とも呼ばれる。 右側の壁に手を付いて、ひたすら壁沿いに進むという方法である(右側の壁の代わりに左側の壁に手をついても本質的には同じ、この場合は左手法と言う)。壁の切れ目は迷路の入口と出口にしかないので、右手法を使うと最終的には、入口に戻ってしまうか出口に到達するかのいずれかになる。最短経路でゴールにたどりつけるとは限らないが、最悪でも壁の長さ分だけ歩けば終了する。 平面的な迷路であれば、右手法を使うと必ず出口にたどり着く。しかし、迷路のスタートないしゴールが迷路の中にあったり、あるいは迷路が立体的だったりした場合は、右手法の結果スタート地点に戻ってしまう事もありうる。 またゴール以外にダミーの出口があると、そちらに行ってしまう事もあるが、この場合はダミーの出口を無視して右手法を続ければ良い。 Windowsのスクリーンセーバーの一つ「3D迷路」は、この方法で迷路を進んでいる。スタートから左側の壁(線)に沿って進む。最短距離ではないものの、ゴールには辿り着いている。スタートから左側の壁(線)に沿って進んだが、壁(線)が連続しておらず、もとの場所に戻って来てしまった。 あらゆる迷路を解くことが出来る解法として「トレモー・アルゴリズム」が知られている。この解法は19世紀のフランスの数学者エドゥアール・リュカによって紹介された。この方法は本質的には「全パターンの経路をしらみ潰し的に試す」というものであるが、チョークで地面に自分が通った跡を残す事で、しらみ潰しを効率的にできる点に特徴がある。この方法では、迷路上の各々の通路は最大2回しか通らない(試しに進んでみる場合と、諦めて戻る場合の2回)。よって最悪でも通路の長さの合計値の2倍歩けば、ゴールに辿り着く。 アルゴリズムの詳細は以下の通り。以下のアルゴリズムで、迷路を歩くときは常にチョークで地面に「→→→→」と描き続ける。また、まだチョーク跡のつけられていない通路を歩くのを「通路を進む」と言い、既にチョーク跡「→→→→」がつけられた通路を「←←←←」の方向へと進むのを「通路を戻る」と呼ぶ。 簡単のため、スタート地点が迷路中の分岐点の一つにあると仮定して話を進める。 スタート地点が迷路中の分岐点の一つに無い場合も、スタート地点が分岐点だとみなして上述のアルゴリズムが使うことが出来る。つまり、スタート地点が通路の中央にある場合は、スタート地点は2方向に分岐する分岐点だとみなす。スタート地点が迷路の行き止まりにあるときは、スタート地点は一方向にだけ分岐する分岐点だと考える。 このアルゴリズムの利点は、スタートからゴールまでに通る分岐点の数が最小の経路(ただしスタートからゴールまでの距離は必ずしも最短ではない)を発見出来ることと、無限に広い(ゴールまでの距離は有限の)迷路でも有限の時間でゴールに辿り着くことが出来ることである。一方欠点は同じ通路をかなり多くの回数いったりきたりしなければならない為、右手法やトレモー・アルゴリズムに比べると移動距離が長くなる事である(「右手法」や「トレモー・アルゴリズム」では、無限に広い迷路では無限の探索が必要となる可能性がある。またこれらのアルゴリズムでは同じ通路は最大でも2回しか通らない)。 紙の上で解く場合は、行き止まりを全て塗り潰せば、結果的に正解が浮かび上がる。行き止まりを全て塗り潰し、ルートが浮かび上がった。 庭園の生垣を利用した生垣迷路 ヨーロッパでは古くから修道院の庭などに迷路園が作られた。ヘンリー2世 (イングランド王)は、愛人を迷路園の中の隠れ家に住まわせ、妻のアリエノールから匿ったとされる。しかし、アリエノールは紐を用いて迷路を解き、愛人を毒殺してしまったという。 ルネサンス以降は、宮殿に付属して作られた。ルイ14世 (フランス王)は、1672年、ヴェルサイユ宮殿の庭に迷路園を作った。この迷路園は1775年に解体されている。イギリスではテューダー朝やステュアート朝の時代に盛んに作られた。イギリスのハンプトン・コート宮殿の庭にあるものなど、現在も多くの迷路園が残っている。
迷路の解法
右手法(左手法)
トレモー・アルゴリズム
任意に選んだ通路を進む。
そのうち分岐点か行き止まりかゴールにたどり着く。
まだ通っていない(=チョークの跡がない)分岐点に辿り着いたら、通ってきた通路以外の任意の通路を選び、そこを進む。→2
すでに通った(=チョークの跡がある)分岐点に辿り着いたら、進んできた通路を戻る。→2
通路を戻っているときに分岐点に辿り着いた場合(注:戻っているときなので、この分岐点は必ず過去に通っている)
まだ通っていない(=チョークの跡がない)通路が残っていたら、その通路へと進む。→1
全ての通路にチョークの跡があったら、各通路を眺める。ほとんどの通路は、通路へと伸びて行くチョーク跡「→→→→」および通路から引き返して来るチョーク跡「←←←←」があるが、一つだけ「←←←←」の無い通路(=この分岐点に最初に来たときに通った通路)がある。その通路を引返す。→2
ただし今いる分岐点がスタート地点だった場合は、全ての通路に「→→→→」と「←←←←」の両方が書いてある事もありうる。この場合ゴールに到達する方法が無いので、諦めて終了。
行き止まりに辿り着いたら、来た道を戻る。→2
ゴールにたどり着いたら終了。
オーア・アルゴリズム(英語版
オーア・アルゴリズムの概説
スタートから最初の分岐点まで歩く。最初の分岐点から出ている全ての通路を辿り、分岐点、行き止まりに辿りついたら引き返す。
もし、ある通路が行き止まりだったり、もう既に行ったことのある分岐点(もしくは同じ分岐点)に繋がっていたりしたら、その通路を通らないように目印を付ける。
その分岐点から出ている全ての通路を探索したら、一旦、スタートに戻り、スタートから行くことが出来る別の最初の分岐点にて、同様の探索を行う。
スタートから最初の分岐点を全て探索したら、次にスタートから最初の分岐点を通過した、次の分岐点を全て探索する。
このように、スタートから「n番目」の分岐点を「n=0,1,2,3,4,5...」というように、しらみ潰しに探索していく。
その他の解法
迷路園
ヨーロッパの迷路園