最良優先探索

探索 > 最良優先探索

最良優先探索（さいりょうゆうせんたんさく、英: best-first search）は、幅優先探索（英: breadth-first search）を何らかの規則（評価関数）に従って次に探索する最も望ましいノードを選択するように拡張した探索アルゴリズムである。

探索ノードを効率的に選択するには優先度付きキュー（英: priority queue）を用いて実装するのが一般的である。キューに貯めずに最良のノードだけを扱うと山登り法になる。キューを評価関数でソートしないと幅優先探索になる。

最良優先探索の例としてはダイクストラ法（英: Dijkstra's algorithm）やA*アルゴリズム（英: A* search algorithm）や均一コスト探索を挙げることができる。最良優先探索は経路探索においてしばしば使われるアルゴリズムである。コンピュータ将棋・コンピュータチェスなどでも最良優先探索を拡張した物が使われている。

擬似コード

大文字で書かれた関数は以下の通り。全て引数にノードをとる。

EVAL(node): ノード評価関数：ヒューリスティクスとしてノードからゴールまでの近さの数値を返す関数。EVAL(node1, node2) という形で node1 と node2 のどちらがゴールに近いかを判定する関数でも良い。
EXPAND(node): ノード展開関数：探索候補の集合を返す。
IS_GOAL(node): ノード探索終了判定関数：ゴールに到達したかどうか。

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 と呼ぶ。

最良優先探索

擬似コード

関連項目