|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 最 ： [さい] 1. (n,pref) the most 2. the extreme ・ 最良 ： [さいりょう] 1. (adj-na,n) the best 2. ideal ・ 良 ： [りょう] 【名詞】 1. good ・ 優 ： [ゆう] 1. (adj-na,n) actor 2. superiority 3. gentleness ・ 優先 ： [ゆうせん] 1. (n,vs) preference 2. priority ・ 先 ： [せん] 1. (n,adj-no) the future 2. priority 3. precedence 4. former 5. previous 6. old 7. late ・ 探索 ： [たんさく] 1. (n,vs) search 2. hunt 3. (item of) research 4. exploration 5. investigation ・ 索 ： [さく] 【名詞】 1. rope 2. cord
最良優先探索（さいりょうゆうせんたんさく、）は、幅優先探索（）を何らかの規則（評価関数）に従って次に探索する最も望ましいノードを選択するように拡張した探索アルゴリズムである。 探索ノードを効率的に選択するには優先度つきキュー（）を用いて実装するのが一般的である。キューに貯めずに最良のノードだけを扱うと山登り法になる。キューを評価関数でソートしないと幅優先探索になる。 最良優先探索の例としてはダイクストラ法（）やA *アルゴリズム（）や均一コスト探索を挙げることができる。最良優先探索は経路探索においてしばしば使われるアルゴリズムである。コンピュータ将棋・コンピュータチェスなどでも最良優先探索を拡張した物が使われている。 == 擬似コード == 大文字で書かれた関数は以下の通り。全て引数にノードをとる。 ;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 と呼ぶ。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「最良優先探索」の詳細全文を読む スポンサード リンク
|