幅優先探索は、グラフやツリー構造のデータを探索する代表的なアルゴリズムです。出発地点に近い階層から順に全てのノードを水平に探索するため、最短経路の発見に優れています。古典的な人工知能での問題解決や経路計画、ネットワーク解析などで幅広く利用されており、漏れなく規則正しく状態空間を探索できる特徴を持ちます。
幅優先探索とは
幅優先探索を一言でいうと、スタート地点から近い順番に同じ深さの選択肢をすべて確認しながら進む探索アルゴリズムです。
詳しく解説
幅優先探索は、キュー構造と呼ばれるデータ管理方法を用いて探索を行います。スタートノードから隣接するすべてのノードをキューに追加し、同じ深さにある階層を1層ずつ順番にしらみつぶしにチェックします。各移動のコストが均一なグラフにおいて、必ず最短経路を発見できる点が大きな特徴です。人工知能における状態空間探索やロボティクスでの経路計画など、基礎的な意思決定プロセスで重要な役割を果たします。ただし、探索が深くなるにつれて記憶すべきノードの数が爆発的に増加するため、メモリー消費量が非常に大きくなる課題があります。
具体例・使われ方
カーナビや地図アプリにおける最短乗換ルートの計算、SNSでのユーザー同士の最短のつながりの特定、パズルや盤上ゲームにおいて最小手数でゴールに達する手順の探索などで活用されます。
似た用語との違い
混同されやすい深さ優先探索との違いは探索の進め方にあります。幅優先探索が同じ深さの選択肢を横方向に広げて探索するのに対し、深さ優先探索は1つの選択肢を最深部まで縦方向に辿ってから戻ります。幅優先探索は最短経路を保証できますが大量のメモリーが必要となり、深さ優先探索はメモリー使用量を抑えられますが最初に見つけた解が最短とは限らない特徴があります。
注意点
分岐数が多い広大な問題を扱う場合、探索の階層が深くなるとメモリーが不足して計算不能になる限界があります。そのため、より複雑なAIの探索問題では、単なる幅優先探索ではなく、ゴールまでの推定コストを利用するヒューリスティック評価を取り入れたA*アルゴリズムなどの高度な手法が用いられます。