巨大な迷路の入口に、2人の探検家が立っています。
2人の目的は同じです。
できるだけ早くゴールを見つけること。
1人目は、入口から近い場所を順番に丁寧に調べます。
右も左も確認しながら、少しずつ探索範囲を広げていきます。
もう1人は違います。
近い場所を調べながら、ときどきゴールの方向を見ます。
「ゴールはたぶん右上だ。だったら、こちらを優先して調べよう」
さて、どちらが先にゴールへたどり着きそうでしょうか？
前回紹介したダイクストラ法は、スタートからのコストを基準に近い場所から調べていく方法でした。
今回紹介するA*（Aスター）アルゴリズムでは、そこにもう一つの情報を加えます。
それが、
「ゴールまで、あとどれくらいありそうか？」
という予測です。
この小さな違いが、経路探索を大きく変えることがあります。
【画像① 挿入位置：ここ】
2人の探検家が同じ迷路に挑戦。
一人は近い場所から、もう一人はゴールの方向も考える。あなたならどちらを選びますか？
A*は「ゴールを意識する」
まず、とても簡単に考えましょう。
あなたが知らない町で駅を探しているとします。
駅が東にあることが分かっているのに、西へ向かう道を片っ端から調べるでしょうか？
普通は、
「駅は東だから、まず東へ向かう道を調べよう」
と考えるはずです。
A*も、これに少し似ています。
ただし、
ゴール方向に見える道だけを blindly 選ぶわけではありません。
今までにかかったコストと、ゴールまで残っていそうなコストの両方を考えます。
【画像② 挿入位置：ここ】
見た目ではゴールに近そうな道。
でも、本当にその道が一番速いのでしょうか？
A*で大切な3つの数字
ここだけ少し数学らしくなります。
A*では、ある地点について主に3つの値を考えます。
g(n)
スタートから現在地点までに実際にかかったコスト。
h(n)
現在地点からゴールまで、あとどれくらいかかりそうかという予測。
f(n)
その2つを合わせた評価。
式にすると、
f(n) = g(n) + h(n)
です。
でも式を暗記する必要はありません。
もっと簡単に言えば、
ここまで何分？ ＋ あと何分くらい？
です。
旅行中に、
「ここまで30分かかった。目的地まではあと10分くらいかな」
と考えるのと似ています。
カフェまで行くなら、どちらを選ぶ？
例えば、あなたが駅から人気のカフェへ歩いているとします。
道Aは、ここまで5分。
カフェまで残り10分くらいと予想されています。
すると、
5 + 10 = 15
です。
道Bは、ここまで8分かかりました。
しかしカフェまであと3分くらいです。
すると、
8 + 3 = 11
です。
現在までの時間だけ見ると道Aのほうが短い。
しかしゴールまで考えると道Bのほうが有望です。
A*はこのように、
「今まで」だけでなく「これから」も考える
のが特徴です.
【画像③ 挿入位置：ここ】
「ここまでは近い道」と「ゴールまで考えると近い道」。
2つは同じとは限りません。
ダイクストラ法と何が違う？
前回のダイクストラ法を思い出してください。
基本的には、
スタートから現在地点までのコスト
を使って探索を進めます。
そのため、ゴールとは違う方向にある地点でも、スタートから近ければ調べる候補になります。
A*では、
スタートからのコスト + ゴールまでの推定コスト
を使います。
そのため、良いヒューリスティックを使える場合には、ゴールに関係しそうな場所を優先的に探索しやすくなります。
イメージすると、
ダイクストラ法：周囲へ波紋のように広がる
A：ゴール方向へ探索が伸びていく*
という違いがあります。
【画像④ 挿入位置：ここ】
同じスタート、同じゴール。
ダイクストラ法とA*では「調べる場所」がどう変わるでしょうか？
「予測」が間違ったらどうなる？
ここで疑問が出てきます。
「ゴールまでの予測が間違っていたら？」
とても重要な質問です。
A*で使うゴールまでの予測を、
ヒューリスティック（heuristic）
と呼びます。
例えばマス目の地図なら、現在位置とゴールの直線距離などをヒューリスティックとして利用する場合があります。
予測が役に立てば、探索を効率よく進められます。
しかしヒューリスティックの設計が適切でなければ、探索効率が悪くなったり、条件によっては期待した最適性を保証できなくなったりします。
つまりA*では、
「未来を予測する」だけではなく、「どんな予測を使うか」
が非常に重要なのです。
【ちょっと意外】ゴールに近そうな道がハズレになる
あなたは山の中でホテルを目指しているとします。
地図を見ると、ホテルはすぐ向こう側。
直線距離なら500メートルしかありません。
「近い！」
と思って進むと……
巨大な川があります。
橋はありません。
結局、大きく遠回りして橋まで行かなければなりません。
一方、最初から少し遠く見える道を選んだ人は、橋を渡って早くホテルへ到着しました。
ここから分かるのは、
ゴールに近く見えることと、実際に早く着くことは同じではない
ということです。
A*でも、ヒューリスティックだけを見るのではなく、実際にここまでかかったコストも合わせて判断します。
【画像⑤ 挿入位置：ここ】
ホテルは目の前なのに、川を渡れない！
「ゴールに近い＝最短ルート」ではありません。
ゲームのキャラクターも道を探している
ゲームを想像するとA*はさらに分かりやすくなります。
キャラクターの前には、
壁
建物
川
敵
通れる道
などがあります。
キャラクターが宝箱まで移動するとき、単純に宝箱の方向へ一直線に進めるとは限りません。
障害物を避けながら、目的地までの経路を探す必要があります。
このような経路探索はゲームやロボットなどさまざまな分野で重要です。
A*は経路探索を学ぶときに登場する代表的なアルゴリズムの一つです。
ロボットならどうする？
倉庫を走るロボットを考えてみましょう。
ロボットは棚Aから商品を受け取り、棚Bへ向かいます。
しかし途中には、
商品棚
別のロボット
通れない場所
などがあります。
ロボットは目的地の方向だけを見るのではなく、実際に通れる経路を考えなければなりません。
こうした問題も、
現在までのコスト
と
目的地までの見込み
を考える経路探索として表現できます。
【画像⑥ 挿入位置：ここ】
ゲーム、ロボット、迷路、地図。
見た目は違っても「ゴールまでの良い道を探す」という問題は共通しています。
【1分チャレンジ】
あなたがA*になってみよう
では、最後はゲームです。
あなたは迷路の左下にいます。
ゴールは右上です。
道は何本もあります。
① ゴール方向へ進む短そうな道
② 少し遠回りに見える道
③ 最初は逆方向へ進む道
ただし①の先には壁があります。
さて、
あなたなら最初にどの道を調べますか？
重要なのは、
「ゴールに近いか？」
だけではありません。
「ここまでのコスト」と「ゴールまでの予測」を一緒に考えること。
これがA*の考え方です。
【画像⑦ 挿入位置：ここ】
あなた vs A*
先にゴールへの良いルートを見つけられるのはどちらでしょう？
A*は「未来が見えるダイクストラ法」？
初心者向けには、こんなイメージで覚えると分かりやすいでしょう。
ダイクストラ法は、
「ここまで何分かかった？」
を重視する。
A*は、
「ここまで何分？」＋「あと何分くらい？」
を考える。
ただし、これは理解するための簡略化です。
A*が最適な経路を保証する条件には、使用するヒューリスティックの性質などが関係します。
まずは、
A*にはゴールまでの推定値が加わる
と覚えておけば十分です。
30秒で復習
今日のポイントは5つです。
① A*は最短経路探索で使われる代表的なアルゴリズム。
② スタートから現在地までのコスト g(n) を考える。
③ ゴールまでの推定コスト h(n) も考える。
④ f(n) = g(n) + h(n) を使って探索する候補を評価する。
⑤ ヒューリスティックの選び方が重要。
一つだけ覚えるなら、
「ここまで」＋「これから」
です。
まとめ
A*アルゴリズムの面白さは、
まだ到着していないゴールについての予測を探索に利用すること
です。
ダイクストラ法ではスタートからのコストを中心に探索しました。
A*では、そこへゴールまでの推定値を加えます。
だから条件が合えば、ゴールと関係の薄い場所をたくさん調べる代わりに、有望な方向へ探索を集中させることができます。
しかし、ただゴール方向へ進めばよいわけではありません。
川や壁のような障害物もあります。
「今まで」と「これから」の両方を見る。
これがA*を理解する最初の一歩です。
次にゲームのキャラクターが障害物を避けながら自然に目的地へ向かっているのを見たら、
「このキャラクターは、どうやって道を選んでいるんだろう？」
と考えてみてください。
いつものゲーム画面が、小さな数学実験に見えてくるかもしれません。
次回予告
第17回｜迷路を解くコンピューターは右へ行く？左へ行く？BFSとDFSの違いをゲーム感覚で理解しよう
次回は、迷路の探索方法を使って**幅優先探索（BFS）と深さ優先探索（DFS）**の違いを比べます。
