経路の特徴を反映した評価値の更新をともなう木探索

概要

論文の詳細を見る
根から葉節点に向かい,順次大きいコストを持つ辺で作られた木構造における探索手法を提案する.提案手法は,A*アルゴリズムをベースとして,直近に観測したコストの真値を利用し,所与のコストの推定値を更新しながら探索を進めるものである.コストの推定値は,その真値を超えないように更新されるため,対象とする問題空間において,提案手法は最適解を発見することが保証される.また,コストの推定値を更新することにより,その真値に近づけることができる.そのため,解を発見するまでに提案手法が展開する節点数は,同一の問題空間に適用したA*アルゴリズムによって展開される節点数以下であることが保証される.さらに,完全二分木を対象としたシミュレーションの結果からは,推定コストの初期値の精度にかかわらず,問題空間のいずれの深さにおいても,提案手法による有効分岐因子の値は,A*アルゴリズムより小さいことが示される.提案手法は,A*アルゴリズムの特性を継承しつつ,コストの分布に特徴がある問題空間において有効な手法であると考えられる.
2013-04-15