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

書誌事項

タイトル別名
  • A Tree Search Method with Improvement of Search Cost Estimation Based on Characteristics of Cost Allocation

この論文をさがす

抄録

根から葉節点に向かい,順次大きいコストを持つ辺で作られた木構造における探索手法を提案する.提案手法は,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.

収録刊行物

詳細情報

  • CRID
    1050845762833313280
  • NII論文ID
    110009579577
  • NII書誌ID
    AN00116647
  • ISSN
    18827764
  • Web Site
    http://id.nii.ac.jp/1001/00091596/
  • 本文言語コード
    ja
  • 資料種別
    journal article
  • データソース種別
    • IRDB
    • CiNii Articles

問題の指摘

ページトップへ