Depth-first iterative-deepening: An optimal admissible tree search
type: Item
instance of: scholarly article
title: Depth-first iterative-deepening: An optimal admissible tree search
zbMATH Open document ID: 0573.68030
DOI: 10.1016/0004-3702(85)90084-0
author: Richard E. Korf
published in: Artificial Intelligence
publication date: 1985-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68T99
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3915637
zbMATH Keywords: searching
zbMATH Keywords: depth-first iterative-deepening algorithm
zbMATH Keywords: exponential tree searches
Wikidata QID: Q56269613
MaRDI profile type: Publication
full work available at URL: 0004-3702(85)90084-0
OpenAlex ID: W2150470619
cites work: Q4747542
cites work: Q3862379
cites work: Q3807647
cites work: Q3856120
cites work: Q5679703
cites work: Q3732977
cites work: A heuristic search algorithm with modifiable estimate
DBLP publication ID: journals/ai/Korf85
Recommended article: Agent searching in a tree and the optimality of iterative deepening
Recommended article: A correction to: ``Agent searching in a tree and the optimality of iterative deepening''
Recommended article: Iterative-deepening search with on-line tree size prediction
Recommended article: Bounding the Depth of Search Trees
Recommended article: Anytime AND/OR depth-first search for combinatorial optimization
Recommended article: Q4356435
Recommended article: Q4230732
description: scientific article; zbMATH DE number 3915637