definition of Wikipedia
Advertizing ▼
Graph and tree search algorithms 

Listings 
Related topics 
Iterative deepening depthfirst search (IDDFS) is a state space search strategy in which a depthlimited search is run repeatedly, increasing the depth limit with each iteration until it reaches , the depth of the shallowest goal state. IDDFS is equivalent to breadthfirst search, but uses much less memory; on each iteration, it visits the nodes in the search tree in the same order as depthfirst search, but the cumulative order in which nodes are first visited is effectively breadthfirst.
Contents 
IDDFS combines depthfirst search's spaceefficiency and breadthfirst search's completeness (when the branching factor is finite). It is optimal when the path cost is a nondecreasing function of the depth of the node.
The space complexity of IDDFS is , where is the branching factor and is the depth of shallowest goal. Since iterative deepening visits states multiple times, it may seem wasteful, but it turns out to be not so costly, since in a tree most of the nodes are in the bottom level, so it does not matter much if the upper levels are visited multiple times.^{[1]}
The main advantage of IDDFS in game tree searching is that the earlier searches tend to improve the commonly used heuristics, such as the killer heuristic and alphabeta pruning, so that a more accurate estimate of the score of various nodes at the final depth search can occur, and the search completes more quickly since it is done in a better order. For example, alphabeta pruning is most efficient if it searches the best moves first.^{[1]}
A second advantage is the responsiveness of the algorithm. Because early iterations use small values for , they execute extremely quickly. This allows the algorithm to supply early indications of the result almost immediately, followed by refinements as increases. When used in an interactive setting, such as in a chessplaying program, this facility allows the program to play at any time with the current best move found in the search it has completed so far. This is not possible with a traditional depthfirst search.
The time complexity of IDDFS in wellbalanced trees works out to be the same as Depthfirst search: .
In an iterative deepening search, the nodes on the bottom level are expanded once, those on the next to bottom level are expanded twice, and so on, up to the root of the search tree, which is expanded times.^{[1]} So the total number of expansions in an iterative deepening search is
For and the number is
All together, an iterative deepening search from depth 1 to depth expands only about 11% more nodes than a single breadthfirst or depthlimited search to depth , when . The higher the branching factor, the lower the overhead of repeatedly expanded states, but even when the branching factor is 2, iterative deepening search only takes about twice as long as a complete breadthfirst search. This means that the time complexity of iterative deepening is still , and the space complexity is . In general, iterative deepening is the preferred search method when there is a large search space and the depth of the solution is not known.^{[1]}
For the following graph:
a depthfirst search starting at A, assuming that the left edges in the shown graph are chosen before right edges, and assuming the search remembers previouslyvisited nodes and will not repeat them (since this is a small graph), will visit the nodes in the following order: A, B, D, F, E, C, G. The edges traversed in this search form a Trémaux tree, a structure with important applications in graph theory.
Performing the same search without remembering previously visited nodes results in visiting nodes in the order A, B, D, F, E, A, B, D, F, E, etc. forever, caught in the A, B, D, F, E cycle and never reaching C or G.
Iterative deepening prevents this loop and will reach the following nodes on the following depths, assuming it proceeds lefttoright as above:
(Note that iterative deepening has now seen C, when a conventional depthfirst search did not.)
(Note that it still sees C, but that it came later. Also note that it sees E via a different path, and loops back to F twice.)
For this graph, as more depth is added, the two cycles "ABFE" and "AEFB" will simply get longer before the algorithm gives up and tries another branch.

The following pseudocode shows IDDFS implemented in terms of a recursive depthlimited DFS (called DLS).
IDDFS(root, goal) { depth = 0 repeat { result = DLS(root, goal, depth) if (result is a solution) return result depth = depth + 1 } }
Depthlimited search can be implemented recursively as follows. Note that it need only check for goal nodes when depth == 0
, because when depth > 0
, DLS is expanding nodes that it has seen in a previous iteration of IDDFS.
DLS(node, goal, depth) { if (depth >= 0 and node == goal) return node else if (depth > 0) for each child in expand(node) DLS(child, goal, depth1) else return nosolution }
Similar to iterative deepening is a search strategy called iterative lengthening search that works with increasing pathcost limits instead of depthlimits. It expands nodes in the order of increasing path cost; therefore the first goal it encounters is the one with the cheapest path cost. But iterative lengthening incurs substantial overhead that make it less useful than iterative deepening.
sensagent's content
Dictionary and translator for handheld
New : sensagent is now available on your handheld
Advertising ▼
Webmaster Solution
Alexandria
A windows (popinto) of information (fullcontent of Sensagent) triggered by doubleclicking any word on your webpage. Give contextual explanation and translation from your sites !
SensagentBox
With a SensagentBox, visitors to your site can access reliable information on over 5 million pages provided by Sensagent.com. Choose the design that fits your site.
Business solution
Improve your site content
Add new content to your site from Sensagent by XML.
Crawl products or adds
Get XML access to reach the best products.
Index images and define metadata
Get XML access to fix the meaning of your metadata.
Please, email us to describe your idea.
Lettris
Lettris is a curious tetrisclone game where all the bricks have the same square shape but different content. Each square carries a letter. To make squares disappear and save space for other squares you have to assemble English words (left, right, up, down) from the falling squares.
boggle
Boggle gives you 3 minutes to find as many words (3 letters or more) as you can in a grid of 16 letters. You can also try the grid of 16 letters. Letters must be adjacent and longer words score better. See if you can get into the grid Hall of Fame !
English dictionary
Main references
Most English definitions are provided by WordNet .
English thesaurus is mainly derived from The Integral Dictionary (TID).
English Encyclopedia is licensed by Wikipedia (GNU).
Copyrights
The wordgames anagrams, crossword, Lettris and Boggle are provided by Memodata.
The web service Alexandria is granted from Memodata for the Ebay search.
The SensagentBox are offered by sensAgent.
Translation
Change the target language to find translations.
Tips: browse the semantic fields (see From ideas to words) in two languages to learn more.
last searches on the dictionary :
computed in 0.125s