迷路で眺める探索アルゴリズム

CodeVS2.0(サイト:http://codevs.jp/ 予選の連鎖動画:http://www.nicovideo.jp/watch/sm19873888)の復習をかねてこんなFlashを作りました。



迷路で眺める探索アルゴリズム(Search algorithm visualize)

さまざまなアルゴリズムを使って、迷路探索を行います。
使ったのは基本的な探索アルゴリズム8種とオリジナルのアルゴリズム2種です。

まずは迷路の見方について。

  • 青色(): Sがスタート、Gがゴール
  • 白色(): 未探索のマス
  • 灰色(): 探索済みのマス
  • 赤色(): 探索により発見されて、リストに保持されているの分岐点
  • 橙色(): 枝刈りにより、リストから削除された分岐点
  • マスに書いてある数字は、リスト内のマスにゴールに近い順に順位を付けたものです
    (間違い制限探索のみ異なるので後で解説)

つぎに操作方法について。

  • 左上のコンボボックス[…|+]でから眺めるアルゴリズムを選ぶ
  • [new]で新しい迷路に更新
  • [new]の左隣のチェックボックスで、2種類の迷路(分岐が多いor少ない)を切り替える
  • [speed]のスライドバーで再生速度を選択

さらにFlash下部のデータの読み方です。

  • 探索回数は迷路内で移動した回数です(灰,赤,橙マスの合計数と同じ)。計算時間(CPU Time)に直結します
  • 分岐数は、現在の探索中リストに追加されているマス(赤)の数です。メモリの使用量に直結します

各アルゴリズムの解説

深さ優先探索(Depth-first search)

深さ優先探索 – Wikipedia

ひたすら一本の道を突き進み、行き止まりがあったら、1つ前の未探索の分岐点に戻って再びその道を突き進む探索法。

特徴

  • 知識なし(評価関数を使用しない)
  • 探索範囲が有限の場合は完全(解を必ず見つけられる)。
  • ただし、探索範囲が無限の場合は不完全。
  • 省メモリ

ただし無限に広いフィールドで探索を行うと、ゴールが近くにあっても見逃してしまいゴールを見つけられない場合があります。

幅優先探索(Breadth-first search)

幅優先探索 – Wikipedia

現在までに見つかってる分岐すべてを一回、一回伸ばしていく探索法。

特徴

  • 知識なし(評価関数を使用しない)
  • 完全(解を必ず見つけられる)
  • 探索範囲が無限でも完全
  • 並列化しやすい

一般的には深さ優先探索よりメモリを大量に使う探索ですが、今回ような迷路探索は分岐が少なく行き止まりが多いので深さ優先探索よりも省メモリな探索になってます。

反復深化深さ優先探索(Iterative deeping depth-first search)

反復深化深さ優先探索 – Wikipedia

深さ制限を設けて深さ優先探索を行い、ゴールが見つからなかった場合は深さ制限をゆるめて再度探索する探索法。

特徴

  • 知識なし
  • 完全
  • 探索範囲が無限でも完全
  • 省メモリ

深さ優先探索の省メモリ性をそのままに、無限に広いフィールドでも使えるようにした探索法です。
ただし省メモリな実装を行うと同じ探索を繰り返し行うことになるので、探索時間が長くなります。
また、省メモリでない実装を行うと、幅優先探索と同等のメモリ消費になります。

知識あり探索と知識なし探索

反復深化深さ優先探索は一般的には知識なし探索です。知識なし探索とは評価関数の使わない探索法のことで、この迷路探索の場合ゴールの位置も分からずに盲目的に探索するような手法です。ただし、今回のFlashでは知識あり探索として、反復深化深さ優先探索をおこないました。

ここから先、すべての探索法は知識あり探索ですが、これらすべてで評価関数に現在値とゴールのマンハッタン距離を利用しています。

 マンハッタン距離を使うとゴールまで到達するのに絶対に必要な深さというのがわかります。例えば、スタートからゴールまでの距離が15マスあった場合、最低15回は枝を伸ばさなければゴールに到達できません。これにより、絶対にゴールに到達できない深さ制限というのが分かります。さらにこれにいくらかのマージン(デフォルトでは4)を上乗せした値を深さ制限に使って探索を行うことで計算量を減らしています。

山登り法(Hill climbing)

山登り法 – Wikipedia

ゴールに近い方向へとひたすら進んでいき、行き止まりがあったらそこで断念する探索法。

特徴

  • 知識あり(評価関数を使う)
  • 不完全
  • 省メモリ

今回の迷路探索ではすぐに行き止まりに突っ込むので、あまり使えません。

最良優先探索(Best-first search)

最良優先探索 – Wikipedia

すべての枝を保持して、それらの分岐の中から一番ゴールに近いものを選んで伸ばしいく探索法。

特徴

  • 知識あり
  • 完全
  • 探索範囲が無限の場合の完全性は評価関数に依存

今回の迷路の条件と評価関数では、完全な探索方法としては最速になるはずです。

間違い制限探索(Limited discrepancy search)

始めに山登り法で探索を行い、解が見つからなかった場合は1回だけ最良では無い方向に行くことを許容して再び探索を行う。それでも見つからなければ、間違った方向へと進める回数(discrepancy)をさらに増やして探索を繰り返す手法。

注:この探索の赤マスに書かれた数字はそのルートの間違い数(discrepancy)です。

特徴

  • 知識あり
  • 完全
  • 探索範囲が無限の場合の完全性は評価関数に依存
  • 省メモリ

反復深化と同様、繰り返し同じ探索を行うことになるため探索に時間がかかります。
ただし、評価関数によっては、省メモリ性、完全性、速度を併せ持つ非常に強力な探索方法となります。

幅優先ビームサーチ(Breadth-first beam search)

幅優先と同じ手順で探索を行い、分岐のリストが事前に決めておいた数(ビーム幅)より長くなった場合に、評価値の悪い枝を枝刈りする。

特徴

  • 知識あり
  • 不完全
  • 並列化しやすい
  • ビーム幅が1の時、山登り法と同じ。
  • ビーム幅が∞(無限)の時、幅優先探索と同じ。

最良優先ビームサーチ(Best-first beam search)

Beam Search – Wikibooks

最良優先と同じ手順で探索を行い、分岐のリストが事前に決めておいた数(ビーム幅)より長くなった場合に、評価値の悪い枝を枝刈りする。

特徴

  • 知識あり
  • 不完全
  • ビーム幅が1の時、山登り法と同じ。
  • ビーム幅が∞(無限)の時、最良優先探索と同じ。

ここまでがある程度知名度のある基本的なアルゴリズムで、次からがオリジナルの探索アルゴリズムになります。

優良優先探索(good-first search)

最良優先探索をより一般化した探索。1度に伸ばす枝の数を、1つに限らず複数にまで拡張した。
例えば、1度に伸ばす枝の数(優先幅)を3に設定した場合、保持されてる枝のうち良い枝から順に3つを延長する操作を繰り返す。

特徴

  • 知識あり
  • 完全
  • 探索範囲が無限の場合の完全性は評価関数に依存
  • 優先幅が∞の時、幅優先探索と同じ
  • 優先幅が1の時、最良優先探索と同じ

二重制限探索(Double limit search, Good-first beam search)

優良優先探索にビームサーチを適用したもの。優先幅とビーム幅両方による制限を行う。

ただし、(優先幅)≦(ビーム幅)となる。

特徴

  • 知識あり
  • 不完全
  • 並列化しやすい
  • 優先幅、ビーム幅が共に∞の時、幅優先探索と同じ
  • 優先幅、ビーム幅が共に1の時、山登り法と同じ
  • 優先幅が1、ビーム幅が∞の時、最良優先探索と同じ
  • 優先幅とビーム幅が同じ時、幅優先探索ビームサーチと同じ
  • 優先幅が1の時、最良優先ビームサーチと同じ
  • ビーム幅が∞の時、優良優先探索と同じ

余談

 ここで紹介したアルゴリズムは各種アルゴリズムは迷路だけではなくて、15パズルや、codevsのような落ち物パズル、ソリティアのようなゲームの探索にも利用可能です。
 さらに、一工夫加えればチェスやオセロの様な対戦ゲームで利用することも出来ます。一見、ビームサーチは対戦ゲームでは使えないに見えますが、各手がどの程度良い手かではなく、各手がどの程度打たれやすいのか(この値は評価関数から算出できる)を考えてそれを基準に枝刈りを行えば、ビームサーチと同じような探索が可能です。

 ちなみにcodevsで使った探索法は幅優先ビームサーチでした。幅優先ビームサーチは実装も簡単で、評価関数を作る際にステップ数が異なる盤面の比較を気にする必要もありません。
 ただ一般的な場合でお勧めの探索法は二重制限探索です。実装の簡単さは幅優先ビームサーチとほぼ同じで、一度実装すればパラメータを変更するだけで、幅優先ビームサーチにしたり、最良優先ビームサーチにしたり、幅優先探索と最良優先探索の中間的な性質の探索にしたりできます。また、今回のような最良優先探索有利の課題に対してマルチコアで挑む場合、優先幅をコア数に合わせることで最良優先探索より高速な探索を行うことも可能になります。

あと、迷路生成アルゴリズムは古くて新しい自動迷路生成アルゴリズム – ガジェット通信を参考にクラスタリングアルゴリズムと穴掘り法を使用しました。

※追記:2017/05/27 wonderfl閉鎖によりリンク切れのため「How wonderfl!」へのリンクの差し替えをおこないました

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です