iterative deepening search

An uninformed searchstate space search, n.: Solving a problem by treating every situation it could be in as a point on a map, with each possible move as a road between points, and searching for a route from the start to a goal. strategy that performs a depth-first searchdepth-first search, n.: A way of exploring a maze or network by following one path as far as it goes, then backing up to the most recent fork and trying the next branch. capped at depth 0, then starts over with a cap of 1, then 2, and so on, raising the cap until some pass reaches a goal. It combines the linear memory use of depth-first search with the completeness and shortest-solution guarantee of breadth-first searchbreadth-first search, n.: A way of exploring a maze or network level by level — first every place one step away, then every place two steps away, and so on — so that the shortest route is found first. for unit-cost actions. Re-expanding shallow nodes costs surprisingly little, because in a tree with branching factor b most nodes lie at the deepest level: total work exceeds a single breadth-first pass by a factor of only about b/(b−1). Iterative deepening A* (IDA*) applies the idea to A* searchA* search, n.: A method for finding the shortest route on a map or network that weighs both how far you have already come and a smart guess of how far is left, so it tries the most promising paths first., using successive thresholds on f = g + h. Game programs deepen iteratively so that a best move found so far is always available when time runs out, and use earlier iterations to order moves for alpha–beta pruningalpha–beta pruning, n.: A shortcut for game programs: tracking the best result each side is already sure of, it ignores lines of play that could only do worse, and when promising moves come first it searches about twice as deep..