[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



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.


Citations (0)*help

See more


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


Report a problem

Back to top