翻訳と辞書
Words near each other
・ 坂齋小一郎
・ 坃
・ 坄
・ 坅
・ 坆
・ 均
・ 均し
・ 均しい
・ 均す
・ 均一
均一コスト探索
・ 均一係数
・ 均一化
・ 均一型ダム
・ 均一定期乗車券
・ 均一性
・ 均一性検定
・ 均一水性ガス反応
・ 均一系
・ 均一系水性ガス反応


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

均一コスト探索 : ミニ英和和英辞書
均一コスト探索[きんいつこすとたんさく]
=====================================
〔語彙分解〕的な部分一致の検索結果は以下の通りです。

均一 : [きんいつ]
  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)
ウィキペディアで「均一コスト探索」の詳細全文を読む




スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.