翻訳と辞書
Words near each other
・ 双方向クイズ 天下統一
・ 双方向クイズ天下統一
・ 双方向テキスト
・ 双方向テレビ
・ 双方向テレビジョン
・ 双方向ライブ にっぽんのマジョリティー
・ 双方向ライブにっぽんのマジョリティー
・ 双方向リスト
・ 双方向・夜どおしナマ解説 どう読む激動の2008年
・ 双方向反射率分布関数
双方向探索
・ 双方向放送
・ 双方向散乱面反射率分布関数
・ 双方向番組
・ 双方向解説・そこが知りたい
・ 双日
・ 双日インフィニティ
・ 双日エネルギー
・ 双日ツーリスト
・ 双日プラネット


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

双方向探索 : ウィキペディア日本語版
双方向探索[そうほうこうたんさく]
双方向探索: bidirectional search)とは、グラフ探索アルゴリズムの一種で、同時に2つの方向から探索を行う。一方は初期状態から順方向に探索し、もう一方は最終状態から逆方向に探索して、その中間でぶつかった時点で終了する。それぞれの探索の計算量は O(b^)ランダウの記号)であり、両方を合わせても O(b^+b^) となり、一方向から全部の探索を行った場合の O(b^) よりも効率がよい。
しかし、よいことばかりではない。並列に2つの探索を行う複雑さは別として、探索木をどう拡張していくかを各ステップで決定する必要がある。また、最終状態から逆方向に探索できる状況は限られているし、事前に用意が必要になる場合もある。また、2つの探索木の交差を見つける効率的方法も必要になる。このような問題があるため、うまいヒューリスティックがあるならA
*
の方がよい選択となることが多い。
双方向探索でもヒューリスティックを使うことができる。A
*
について証明されているように、許容的ヒューリスティックによって最短解が得られる場合がある。
拡張されるノードは、オープンなノード数が最も少なく最も見込みがある最先端から選ばれる。そのようなノードがもう一方の最先端にもある時に、アルゴリズムは終了する。子ノードのf値の計算に当たっては、もう一方の最先端の全てのオープンなノードのg値を考慮しなければならない。そのため、ノードの拡張はA
*よりも計算量が多くなる。訪れるノードの数は上で概説したように少なくなることが期待できる。従って、個々の計算量が多くても調べるノード数が少なくなる。参考文献に示した1977年の文献では、A
*では解けなかった問題を双方向探索で解いた例が示されている。許容的でないヒューリスティックを使った場合でもより短い経路が見つかっている。これらの検証は Ira Pohl が15パズルで行った。
Ira Pohl は、世界で初めて双方向ヒューリスティック探索アルゴリズムを設計・実装した。最先端の子ノードは、もう一方の側のターゲットについてだけ評価していた。彼の報告によれば、2つの探索木は相手と交差したことを検出できなかったという。
== 参考文献 ==

*Dennis de Champeaux & Lenie Sint, An Improved Bi-directional Heuristic Search Algorithm, Journal ACM, vol 24, no 2, 1977 May, pp 177-191.
*Dennis de Champeaux, Bi-Directional Heuristic Search Again, Journal ACM, vol 30, no 1, 1983 January, pp 22-32.
*Ira Pohl, Bi-directional Search, in Machine Intelligence, vol. 6, eds. Meltzer and Michie, Edinburgh University Press, 1971, pp. 127-140.
*Stuart Russell and Peter Norvig. ''Artificial Intelligence: A Modern Approach'', 2nd ed., Prentice Hall, 2002 (§3.4).



抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「双方向探索」の詳細全文を読む



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

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