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

• Item type: Journal(1)
• 公開日: 2013-04-15
• タイトル: 経路の特徴を反映した評価値の更新をともなう木探索
• タイトル / 言語: en
• タイトル: A Tree Search Method with Improvement of Search Cost Estimation Based on Characteristics of Cost Allocation
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [一般論文] 木探索，発見的探索，A*アルゴリズム，有効分岐因子，コストの偏り
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 和歌山大学経済学部
• 著者所属: 和歌山大学システム工学部
• 著者所属(英): en
• 著者所属(英): Faculty of Economics, Wakayama University
• 著者所属(英): en
• 著者所属(英): Faculty of Systems Engineering, Wakayama University
• 著者名: 芦田, 昌也; 瀧, 寛和
• 著者名(英): Masaya, Ashida; Hirokazu, Taki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 根から葉節点に向かい，順次大きいコストを持つ辺で作られた木構造における探索手法を提案する．提案手法は，A*アルゴリズムをベースとして，直近に観測したコストの真値を利用し，所与のコストの推定値を更新しながら探索を進めるものである．コストの推定値は，その真値を超えないように更新されるため，対象とする問題空間において，提案手法は最適解を発見することが保証される．また，コストの推定値を更新することにより，その真値に近づけることができる．そのため，解を発見するまでに提案手法が展開する節点数は，同一の問題空間に適用したA*アルゴリズムによって展開される節点数以下であることが保証される．さらに，完全二分木を対象としたシミュレーションの結果からは，推定コストの初期値の精度にかかわらず，問題空間のいずれの深さにおいても，提案手法による有効分岐因子の値は，A*アルゴリズムより小さいことが示される．提案手法は，A*アルゴリズムの特性を継承しつつ，コストの分布に特徴がある問題空間において有効な手法であると考えられる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 54, 号 4, p. 1632-1640, 発行日 2013-04-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764