|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 均一 ： [きんいつ] 1. (adj-na,n) uniformity 2. equality ・ 一 ： [いち] 1. (num) one ・ 探索 ： [たんさく] 1. (n,vs) search 2. hunt 3. (item of) research 4. exploration 5. investigation ・ 索 ： [さく] 【名詞】 1. rope 2. cord
均一コスト探索（きんいつこすとたんさく、）は、重みつきの木や木構造やグラフを辿ったり探索するための探索アルゴリズムである。最良優先探索において、評価関数を根ノードから探索ノードまでのコストの総和とした物。直観的には、探索は根ノードで始まり根ノードからの合計コストが最小になるようにノードを訪れ、ゴールに到達するまで続く。均一探索は探索方法としては幅優先探索に似ている。 普通、探索アルゴリズムには隣接する未訪のノードを優先度つきキューに追加する操作が含まれる。キューにはそれぞれのノードが根ノードからの合計コスト順に格納されていて、最小コストのパスを持つノードが最も高い優先度を持っている。キューの先頭にあるノードから直接つながった次のノードをたどり、根ノードからのコストを計算してキューに追加する。 均一コスト探索は一般のグラフ探索を行うダイクストラ法の特殊なケースである。ダイクストラ法は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 探索失敗 de:Breitensuche#Optimalität 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「均一コスト探索」の詳細全文を読む スポンサード リンク
|