最良優先探索

最良優先探索（さいりょうゆうせんたんさく、best-first search）は、幅優先探索（breadth-first search）を何らかの規則（評価関数）に従って次に探索する最も望ましいノードを選択するように拡張した探索アルゴリズムである。探索ノードを効率的に選択するには優先度つきキュー（priority queue）を用いて実装するのが一般的である。キューに貯めずに最良のノードだけを扱うと山登り法になる。キューを評価関数でソートしないと幅優先探索になる。最良優先探索の例としてはダイクストラ法（Dijkstra's algorithm）やA*アルゴリズム（A* search algorithm）や均一コスト探索を挙げることができる。最良優先探索は経路探索においてしばしば使われるアルゴリズムである。コンピュータ将棋・コンピュータチェスなどでも最良優先探索を拡張した物が使われている。