最良優先探索

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

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

• ダイクストラ法
• A*
• 均一コスト探索

この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。

• 表示
• 編集