前のページ 1/2 次のページ

迷路(めいろ)は、複雑に入り組んだ道を抜けて、目的地、ゴールまで辿り着くことを目指すゲーム、パズルのこと。「迷路」は英語で「maze(メイズ)」と言うので、迷図(めいず)という当て字をされることもある。

作為的に作られたものを指すことが多いが、山道や繁華街の路地などの実在する入り組んだ道を指して、比喩的に「迷路」と言うこともある。部屋や通路が入り組んだ建築物は、特に迷宮とも呼ばれる。

◆ 迷路の解法

◇ 右手法

右側の壁に手を付いて、ひたすら壁沿いに進むという方法である。(右側の壁の代わりに左側の壁に手をついても本質的には同じ。)

壁の切れ目は迷路の入口と出口にしかないので、右手法を使うと最終的には、入口に戻ってしまうか出口に到達するかのいずれかになる。

平面的な迷路であれば、右手法を使うと必ず出口にたどり着く。

しかし、迷路のスタートないしゴールが迷路の中にあったり、あるいは迷路が立体的だったりした場合は、右手法の結果スタート地点に戻ってしまう事もありうる。

またゴール以外にダミーの出口があると、そちらに行ってしまう事もある。ただしこの場合はダミーの出口を無視して右手法を続ければ良い。

なお右手法は最短経路でゴールにたどりつけるとは限らないが、最悪でも壁の長さ分だけ歩けば終了する。

◇ トレモー・アルゴリズム

あらゆる迷路を解くことが出来る解法として、「トレモー・アルゴリズム」が知られている。この解法は19世紀のフランスの数学者エドゥアール・リュカによって紹介された。

この方法は本質的には「全パターンの経路をしらみ潰し的に試す」というものであるが、チョークで地面に自分が通った跡を残す事で、効率的にしらみ潰しを行う事を可能にしたところに特徴がある。

この方法では、迷路上の各々の通路は最大2回しか通らない(試しに進んでみる場合と、諦めて戻る場合の2回)。

よってトレモー・アルゴリズムでは、最悪でも通路の長さの合計値の2倍歩けば、ゴールにたどり着く事になる。

アルゴリズムの詳細は以下の通り。なお、以下のアルゴリズムで、迷路を歩くときは常にチョークで地面に「→→→→」と描き続けるものとする。

まだチョーク跡のつけられていない通路を歩く事を「通路を進む」といい、すでにチョーク跡「→→→→」がつけられた通路を「←←←←」の方向へと進む事を「通路を戻る」と呼ぶ事にする。

簡単の為、スタート地点が迷路中の分岐点の一つにあると仮定して話を進める。

・ (0)任意に選んだ通路を進む。

・ (1)そのうち分岐点か行き止まりかゴールにたどり着く。

・ (2)通路を進んでいるときに、まだ通った事がない(=チョークの跡がない)分岐点にたどり着いた場合。

  ・ (2.1) 今通ってきた通路以外の任意の通路を選び、そこを進む。(1)へ

・ (3)通路を進んでいるときに、すでに通った事がある(=チョークの跡がある)分岐点にたどり着いた場合。

  ・ (3.1) 今進んできた通路を戻る。(1)へ。

・ (4)通路を戻っているときに分岐点にたどり着いた場合。(注:戻っているときなので、この分岐点は必ず過去に通ったことがある。)

  ・ (4.1)まだ通ったことがない(=チョークの跡がない)通路が残っていたら、その通路へと進む。(1)へ。

  ・ (4.2)全ての通路にチョークの跡があった場合、各通路を眺める。ほとんどの通路は、通路へと伸びてくチョーク跡「→→→→」と通路から引返して来るチョーク跡「←←←←」があるが、一つだけ「←←←←」の無い通路(=この分岐点に最初に来たときに通った通路)がある。その通路を引返す。(1)へ。

  ・ (4.3)ただし今いる分岐点がスタート地点だった場合は、全ての通路に「→→→→」と「←←←←」の両方が書いてある事もありうる。この場合ゴールに到達する方法が無いので諦めて終了。

・ (5)行き止まりに辿り着いた場合、今来た道を戻る。(1)へ。

・ (6)ゴールにたどり着いたら終了。

スタート地点が迷路中の分岐点の一つに無い場合も、スタート地点が分岐点だと無理矢理思い込む事で、上述のアルゴリズムが使える。

(スタート地点が通路の中央にある場合は、スタート地点は二方向に分岐する分岐点だと思う。スタート地点が迷路の行き止まりにあるときは、スタート地点は一方向にだけ分岐する分岐点だと思う。)

◇ オーア・アルゴリズム

「オーア・アルゴリズム」は、1959年にイェール大学のオイスティン・オーアによって紹介されたものである。スタートの近くにある分岐点から探索を始めて、徐々に探索範囲を広めていくというものである。このアルゴリズムは本質的に、最短経路問題におけるダイクストラのアルゴリズムと同一である。

このアルゴリズムの利点は、スタートからゴールまでに通る分岐点の数が最小の経路(ただしスタートからゴールまでの距離は必ずしも最短ではない)を発見出来ることと、

無限に広い(ゴールまでの距離は有限の)迷路でも有限の時間でゴールに辿り着くことが出来ることである。

一方欠点は同じ通路をかなり多くの回数いったりきたりしなければならない為、右手法やトレモー・アルゴリズムに比べると移動距離が長くなる事である。

(「右手法」や「トレモー・アルゴリズム」では、無限に広い迷路では無限の探索が必要となる可能性がある。

またこれらのアルゴリズムでは同じ通路は最大でも2回しか通らない。)

;オーア・アルゴリズムの概説

#スタートから最初の分岐点まで歩く。最初の分岐点から出ている全ての通路を辿り、分岐点、行き止まりに辿りついたら引き返す。

#もし、ある通路が行き止まりだったり、もう既に行ったことのある分岐点(もしくは同じ分岐点)に繋がっていたら、その通路を通らないように目印を付ける。

#その分岐点から出ている全ての通路を探索したら、一旦、スタートに戻り、スタートから行くことが出来る別の最初の分岐点にて、同様の探索を行う。

#スタートから最初の分岐点を全て探索したら、次にスタートから最初の分岐点を通過した、次の分岐点を全て探索する。

#このように、スタートから「n番目」の分岐点を「n=0,1,2,3,4,5...」というように、しらみ潰しに探索していく。

◇ その他の解法

紙の上で解く場合は、行き止まりを全て塗り潰せば、結果的に正解が浮かび上がる。

◆ 迷路園

庭園の生け垣や、農地のトウモロコシやコムギを利用して迷路が作られることもある。また、純粋に娯楽施設として板塀で囲った迷路園も数多く存在する。遊園地のミラーハウスもこのような迷路のひとつである。

◇ ヨーロッパの迷路園

ヨーロッパでは古くから修道院の庭などに迷路園が作られた。イングランド王ヘンリー2世は、愛人を迷路園の中の隠れ家に住まわせ、妻のアリエノールから匿ったとされる。しかし、アリエノールは紐を用いて迷路を解き、愛人を毒殺してしまったという。

前のページ 1/2 次のページ

・迷路 page1

・迷路 page2