最良優先探索

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
探索 > 最良優先探索

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

探索ノードを効率的に選択するには優先度つきキュー: priority queue)を用いて実装するのが一般的である。キューに貯めずに最良のノードだけを扱うと山登り法になる。

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

擬似コード[編集]

最良優先探索(開始ノード, ノード展開関数, ノード評価関数, ノード探索終了判定関数)
    queue = ノード評価関数で自動的にソートするノードのキュー
    queue に開始ノードを追加
    visited = {開始ノード} // 訪問済みノードを管理する集合
    while (queue が空ではない)
        currentNode = queue の先頭から取り出す
        if (ノード探索終了判定関数(currentNode) == 探索終了)
            return currentNode
        foreach (node in ノード展開関数(currentNode))
            if (node が visited に含まれない)
                node を visited に追加
                node を queue に追加
    return 探索失敗

関連項目[編集]