β Scribed by Richard E. Korf
No coin nor oath required. For personal study only.
The complexities of various search algorithms are considered in terms of time, space, and cost of solution path. It is known that breadth-first search requires too much space and depth-first search can use too much time and doesn't always find a cheapest path. A depth-first iterative-deepening algorithm is shown to be asymptotically optimal along all three dimensions for exponential tree searches. The algorithm has been used successfully in chess programs, has been effectively combined with bi-directional search, and has been applied to best-first heuristic search as well. This heuristic depth-first iterative-deepening algorithm is the only known algorithm that is capable of finding optimal solutions to randomly generated instances of the Fifteen Puzzle within practical resource limits. Depth-first iterative-deepening has no doubt been rediscovered many times
π SIMILAR VOLUMES
This paper will dzscuss two refinements to the depth-first tteratlve-deepemng search strategy The first refinement, the priority system, ts an attempt to simulate best-first search usmg depth-first tterattvedeepenmg search A new data structure, the priority hst, ts introduced mto depth-first tteratt
The agent searching framework models the effort of a search strategy in terms of the distance traversed by an agent while exploring the search space. The framework has been found to be useful in modeling search problems where the cost of backtracking and retracing search paths is important in determ
This paper contains a correction to one of the results presented in an earlier work [ 21 and establishes a new result in that direction. In the paper entitled "Agent searching in a tree and the optimality of iterative deepening" [2] we had presented three independent results, namely that there exist
Given a undirected graph G, the breadth-first search tree is constructed by a breadth-first search on G. In this paper, an optimal parallel algorithm is presented for constructing the breadth-first search tree for permutation graphs in O(log n) time by using O(n/Iog n) processors under the EREW PRAM