best-first searchとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > best-first searchの意味・解説 

最良優先探索

(best-first search から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2017/09/03 13:47 UTC 版)

探索 > 最良優先探索

最良優先探索(さいりょうゆうせんたんさく、: 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 と呼ぶ。

関連項目




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「best-first search」の関連用語

best-first searchのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



best-first searchのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの最良優先探索 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS