[Updated on Apr. 18] Integration of CiNii Articles into CiNii Research

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

Bibliographic Information

Other Title
  • A Tree Search Method with Improvement of Search Cost Estimation Based on Characteristics of Cost Allocation

Search this article

Abstract

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

This article proposes a search method applied to a tree structure that each link cost is larger than the cost of its precedent link along the path from root node to each leaf node. The proposed method searches the tree structure, updating the estimation of link cost based on the actual value of its precedent link cost. It is proved that the proposed method is able to find an optimal solution. And it is also proved that the number of expanded nodes by the proposed method in finding the solution is less than or equal to the number of expanded nodes by A* algorithm. Results of simulation using the proposed method on complete binary trees show that EBF (effective branching factor) by the proposed method is smaller than that by A* algorithm on each depth regardless of the accuracy of the initial value of estimated cost. The proposed method inherits some of known properties of A* algorithm and is effective to the tree structure which is assigned the characteristic cost.

Journal

Citations (0)*help

See more

References(0)*help

See more

Related Articles

See more

Related Data

See more

Related Books

See more

Related Dissertations

See more

Related Projects

See more

Related Products

See more

Details

Report a problem

Back to top