Google Mapsはどう道を探す？

Google Mapsはどう道を探す？

Google Mapsに目的地を入れると、一瞬でルートが出ます。

交差点と道を整理し、行き方の候補を1つずつ試しているのです。これを探索といいます。

地図アプリが目的地までのルートを探すとき、裏でしている基本の動きはどれでしょう。

問題：地図アプリがルートを探す基本の動きはどれでしょう。

1. 行き方の候補を順に試して比べる（正解）
2. 多くの人が通った道をそのまま選ぶ
3. 目的地への直線に近い道だけを選ぶ

解説：地図アプリは交差点から交差点へのルートを順に試し、最適な道を比較しています。人気や直線距離だけで選ぶと、行き止まりや遠回りを見落としてしまいます。

行き止まりまで突き進む探索

自動を押すと、1本の道を突き進む探索が始まります。調べた数と道の長さに注目してみてください。

一本道を奥まで突き進む

1本の道を行き止まりまで進み、ダメなら1つ手前に戻る方法を深さ優先探索といいます。

この迷路では42マス調べて、道は40歩。遠回りでも最初のルートで止まります。

波紋のように広げる探索

同じ迷路を近い順に調べます。道の長さを、深さ優先の40歩と比べてみてください。

スタートから順番に探す

1歩のマスを見てから2歩のマスへ。近くから広げる方法を幅優先探索といいます。

調べた数は59マスですが、道は16歩。近い順に探すので最初に着いた道が最短です。

最短ルートの保証

○か✕か：深さ優先探索を使えば、最初に見つけた道が必ず一番短いルートになる。

答え：✕。深さ優先探索は、突き進んだ1本がゴールに届いた時点で終わります。同じ迷路でも、幅優先の16歩に対して40歩の遠回りを選んでしまいました。

道を探す2つのやり方

• 探索とは、行き方の候補を順に試して比べること
• 深さ優先は1本を奥まで進み、遠回りでも最初の道で止まる
• 幅優先は近い順に広げるので、最初に着いた道が最短になる
• この探索を入口に、推理・確率・学習、そしてChatGPTの仕組みまで順に組み上げていく

どのマスも1歩で進める迷路で、ゴールまでの最短の道を必ず見つけたいとき、使うべきやり方はどれでしょう。

問題：どのマスも1歩で進める迷路で、ゴールまでの最短の道を必ず見つけたいとき、使うべきやり方はどれでしょう。

1. 近いマスから順に調べる幅優先探索（正解）
2. 1本を奥まで進む深さ優先探索
3. 調べるマスが少ないほうの探索

解説：幅優先探索は近いマスから順に試すため、最初に着いた道が必ず最短になります。調べた数は深さ優先の42マスより多い59マスでした。このコースを終えるころには、将棋AIが手を読む仕組みやChatGPTの文生成の仕組みを説明できるようになります。では、AIは次に調べる場所をどこに記憶しているのでしょうか。次のレッスンでは15パズルを使い、メモの扱いを1つ変えるだけで2つの探索が入れ替わる様子を見ていきます。