この実験について
地図アプリ、ロボット、ビデオゲームの経路探索は、すべて同じ問題を解きます。開始地点からゴールまでの最も低コストな道を見つけることです。このグリッドでは、道路に進む1ステップのコストは1、ぬかるみに入るステップのコストは5で、壁は通り抜けられません。Sから広がる3つの古典的なアルゴリズムを見てみましょう。幅優先探索は歩数を数え、ぬかるみを考慮しません。ダイクストラ法は常に次に最もコストの低いセルを探索し、A*は残りの距離の推定値を加えることで、ゴールへまっすぐ進めるようにします。自分でマップを塗り、それぞれがどれだけの作業をするか比べてみましょう。
学習目標
- 地図を、隣接するセル同士がつながり、各ステップにコストが設定されたグラフとして表す
- 幅優先探索が、ステップ数の等しい同心円状にどのように探索するかを説明する
- ステップごとにコストが異なる場合、ダイクストラ法が最小コストの経路を見つけられる理由を説明しましょう
- A*のヒューリスティックが最適な経路を失わずに探索するセル数を減らす仕組みを説明しましょう
- 各アルゴリズムが見つける経路のコストと、処理にかかる量を比較しましょう
使い方
- 1BFSを選んで「検索」を押します。見つかった経路は泥の上を通りますか？表でコストを確認しましょう。
- 2ダイクストラ法を選んでもう一度検索します。BFSの経路とコストを比べましょう。
- 3A*を選びます。経路のコストはダイクストラ法と同じですか？探索したセルの数はどれだけ少なくなりましたか？
- 4検索中に青いフロンティアを観察しましょう。ダイクストラ法とA*では、その形はどのように異なりますか？
- 5泥の周りの道をふさぐように壁を塗ります。どのアルゴリズムが経路を変えますか？それはなぜですか？
- 6「マップをクリア」を押して、SとGを離して配置します。障害物がない場合、各アルゴリズムは何個のセルを探索しますか？
モデル
前提条件
- 移動できるのは上下左右のみです。マスに入るコストは道路では1、泥地では5で、壁には入れません。
- BFSは探索中、すべての移動のコストを1として扱うため、ステップ数が最も少ない経路を見つけます。表に示されるその経路のコストは、泥地も含めた実際のコストです。
- 2つのマスの優先度が同じ場合、先に追加されたマスが先に探索されます。そのため、同じマップなら毎回まったく同じ順序になります。
- ゴールがフロンティアから取り出された時点で探索は終了します。その時点で、ゴールまでの最小コストが確定するからです。
授業で試してみましょう
- Q1BFSは移動数が少ないのに、なぜダイクストラ法よりコストの高い経路を選ぶことがあるのでしょうか？
- Q2すべてのマスが道路だとしたら、BFSとダイクストラ法は同じコストの経路を見つけるでしょうか？それはなぜですか？
- Q3推定値hがマンハッタン距離の10倍だった場合、A*には何が起こるでしょうか？
- Q4ゴールが開けた場所にあるとA*が探索するマスの数が少なくなるのに、迷路ではダイクストラ法とほぼ同じ数になるのはなぜですか？
- Q5衛星ナビは、数百万もの道路の交差点がある国を横断する最速ルートを、1秒もかからずに見つけます。これを可能にしているのは、このラボで学んだどのような考え方でしょうか？
よくある質問
最も優れたアルゴリズムはどれですか？
問題によって異なります。すべての移動コストが同じなら、BFSはシンプルで正確です。移動コストが異なる場合はダイクストラ法を使います。ゴールまでの距離を適切に推定できれば、A*はダイクストラ法と同じ答えを、より少ないマスを探索するだけで求められます。
フロンティアとは何ですか？
フロンティアとは、到達済みでまだ探索されていないマスの集合です。各アルゴリズムは、一度に1つずつフロンティアからマスを取り出します。違いは、次にどのマスを取り出すかを決めるルールだけです。
これらのアルゴリズムは負のコストを扱えますか？
ダイクストラ法とA*は、どの移動コストも負ではないことを前提としています。負のコストがあると、すでに確定したマスへのより低コストのルートが後から見つかる可能性があるため、ベルマン・フォード法のような別のアルゴリズムが必要です。