均一コスト探索とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > 均一コスト探索の意味・解説 

均一コスト探索

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

探索 > 最良優先探索 > 均一コスト探索

均一コスト探索(きんいつこすとたんさく、: uniform-cost search)は、重み付きの木や木構造グラフを辿ったり探索するための探索アルゴリズムである。最良優先探索において、評価関数を根ノードから探索ノードまでのコストの総和とした物。直観的には、探索は根ノードで始まり根ノードからの合計コストが最小になるようにノードを訪れ、ゴールに到達するまで続く。均一探索は探索方法としては幅優先探索に似ている。

普通、探索アルゴリズムには隣接する未訪のノードを優先度付きキューに追加する操作が含まれる。キューにはそれぞれのノードが根ノードからの合計コスト順に格納されていて、最小コストのパスを持つノードが最も高い優先度を持っている。キューの先頭にあるノードから直接つながった次のノードをたどり、根ノードからのコストを計算してキューに追加する。

均一コスト探索は一般のグラフ探索を行うダイクストラ法の特殊なケースである。ダイクストラ法A*アルゴリズムの特殊なケースでヒューリスティクスを定数関数にした場合と同じである。幅優先探索は均一コスト探索の特殊なケースであり、辺のコストが全て同じ場合と同じである。

辺のコストが非負値の場合、最小の評価値の物が必ず見つかる。

擬似コード

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

COST(node1, node2)
辺のコスト関数:node1 から node2 への辺の重み。
EXPAND(node)
ノード展開関数:探索候補の集合を返す。
IS_GOAL(node)
ノード探索終了判定関数:ゴールに到達したかどうか。
function 均一コスト探索(startNode)
    visited = 訪問済みノードを管理する集合
    queue = ノード評価値で自動的にソートするノードの優先度付きキュー
    
    startNode の評価値 = 0
    startNode を visited と queue に追加
    while (queue が空ではない)
        node = queue の先頭から取り出す
        if (IS_GOAL(node)) then
            return node
        for each (child in EXPAND(node))
            evalValue = node の評価値 + COST(node, child)
            if (child が visited に含まれない) then
                child の評価値 = evalValue
                child を queue に追加
            else if (evalValue < child の評価値) then
                child の評価値 = evalValue
                child を queue から削除して追加し直す
    return 探索失敗



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

辞書ショートカット

すべての辞書の索引

「均一コスト探索」の関連用語

均一コスト探索のお隣キーワード
検索ランキング

   

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



均一コスト探索のページの著作権
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