オーア・アルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/08 01:16 UTC 版)
「オーア・アルゴリズム」は、1959年にイェール大学のオイスティン・オーアによって紹介されたものである。スタートの近くにある分岐点から探索を始めて、徐々に探索範囲を広めていくというものである。このアルゴリズムは本質的に、最短経路問題におけるダイクストラのアルゴリズムと同一である。 このアルゴリズムの利点は、スタートからゴールまでに通る分岐点の数が最小の経路(ただしスタートからゴールまでの距離は必ずしも最短ではない)を発見出来ることと、無限に広い（ゴールまでの距離は有限の）迷路でも有限の時間でゴールに辿り着くことが出来ることである。一方欠点は同じ通路をかなり多くの回数いったりきたりしなければならない為、右手法やトレモー・アルゴリズムに比べると移動距離が長くなる事である（「右手法」や「トレモー・アルゴリズム」では、無限に広い迷路では無限の探索が必要となる可能性がある。またこれらのアルゴリズムでは同じ通路は最大でも2回しか通らない）。 オーア・アルゴリズムの概説 スタートから最初の分岐点まで歩く。最初の分岐点から出ている全ての通路を辿り、分岐点、行き止まりに辿りついたら引き返す。 もし、ある通路が行き止まりだったり、もう既に行ったことのある分岐点（もしくは同じ分岐点）に繋がっていたら、その通路を通らないように目印を付ける。 その分岐点から出ている全ての通路を探索したら、一旦、スタートに戻り、スタートから行くことが出来る別の最初の分岐点にて、同様の探索を行う。 スタートから最初の分岐点を全て探索したら、次にスタートから最初の分岐点を通過した、次の分岐点を全て探索する。 このように、スタートから「n番目」の分岐点を「n=0,1,2,3,4,5...」というように、しらみ潰しに探索していく。
※この「オーア・アルゴリズム」の解説は、「迷路」の解説の一部です。
「オーア・アルゴリズム」を含む「迷路」の記事については、「迷路」の概要を参照ください。
- オーア・アルゴリズムのページへのリンク
