最良優先探索

最良優先探索（さいりょうゆうせんたんさく、）は、幅優先探索（）を何らかの規則（評価関数）に従って次に探索する最も望ましいノードを選択するように拡張した探索アルゴリズムである。
探索ノードを効率的に選択するには優先度付きキュー（）を用いて実装するのが一般的である。キューに貯めずに最良のノードだけを扱うと山登り法になる。キューを評価関数でソートしないと幅優先探索になる。
最良優先探索の例としてはダイクストラ法（）やA*アルゴリズム（）や均一コスト探索を挙げることができる。最良優先探索は経路探索においてしばしば使われるアルゴリズムである。コンピュータ将棋・コンピュータチェスなどでも最良優先探索を拡張した物が使われている。
擬似コード.
大文字で書かれた関数は以下の通り。全て引数にノードをとる。
 function 最良優先探索(startNode)
 visited = 訪問済みノードを管理する集合
 queue = ノード評価関数(EVAL)で自動的にソートするノードの優先度付きキュー
 startNode を visited と queue に追加
 while queue が空ではない do
 node = queue の先頭から取り出す
 if IS_GOAL(node) then
 return node
 for each child in EXPAND(node) do
 if child が visited に含まれない then
 child を visited と queue に追加
 return 探索失敗
A* の論文では、上記の visited を CLOSED、queue を OPEN と呼ぶ。