トレモー・アルゴリズム

ウィキペディア小見出し辞書

トレモー・アルゴリズム

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/08 01:16 UTC 版)

「迷路」の記事における「トレモー・アルゴリズム」の解説

あらゆる迷路を解くことが出来る解法として「トレモー・アルゴリズム」が知られている。この解法は19世紀のフランスの数学者エドゥアール・リュカによって紹介された。この方法は本質的には「全パターンの経路をしらみ潰し的に試す」というものであるが、チョークで地面に自分が通った跡を残す事で、しらみ潰しを効率的にできる点に特徴がある。 この方法では、迷路上の各々の通路は最大2回しか通らない（試しに進んでみる場合と、諦めて戻る場合の2回）。よって最悪でも通路の長さの合計値の2倍歩けば、ゴールにたどり着く。 アルゴリズムの詳細は以下の通り。以下のアルゴリズムで、迷路を歩くときは常にチョークで地面に「→→→→」と描き続ける。また、まだチョーク跡のつけられていない通路を歩くのを「通路を進む」と言い、すでにチョーク跡「→→→→」がつけられた通路を「←←←←」の方向へと進むのを「通路を戻る」と呼ぶ。 簡単のため、スタート地点が迷路中の分岐点の一つにあると仮定して話を進める。 任意に選んだ通路を進む。 そのうち分岐点か行き止まりかゴールにたどり着く。 まだ通っていない（＝チョークの跡がない）分岐点に辿り着いたら、通ってきた通路以外の任意の通路を選び、そこを進む。→2 すでに通った（＝チョークの跡がある）分岐点に辿り着いたら、進んできた通路を戻る。→2 通路を戻っているときに分岐点に辿り着いた場合（注：戻っているときなので、この分岐点は必ず過去に通っている）まだ通っていない（＝チョークの跡がない）通路が残っていたら、その通路へと進む。→1 全ての通路にチョークの跡があったら、各通路を眺める。ほとんどの通路は、通路へと伸びて行くチョーク跡「→→→→」および通路から引き返して来るチョーク跡「←←←←」があるが、一つだけ「←←←←」の無い通路（＝この分岐点に最初に来たときに通った通路）がある。その通路を引返す。→2 ただし今いる分岐点がスタート地点だった場合は、全ての通路に「→→→→」と「←←←←」の両方が書いてある事もありうる。この場合ゴールに到達する方法が無いので、諦めて終了。 行き止まりに辿り着いたら、来た道を戻る。→2 ゴールにたどり着いたら終了。 スタート地点が迷路中の分岐点の一つに無い場合も、スタート地点が分岐点だとみなして上述のアルゴリズムが使うことが出来る。つまり、スタート地点が通路の中央にある場合は、スタート地点は2方向に分岐する分岐点だとみなす。スタート地点が迷路の行き止まりにあるときは、スタート地点は一方向にだけ分岐する分岐点だと考える。