Iterative deepening search, Computer Engineering

Iterative Deepening Search:

So, breadth first search is always guaranteed to find a solution (if one exists), actually it eats all the memory. For the depth first search, there is much less memory hungry, however not guaranteed to find a solution. Is there any other way to search the space which combines the good parts of both?? 

Well, yes, but it sounds impractical Iterative Deepening Search (IDS) is just about a series combination of depth first searches where the depth limit is mostly increased by one every time. That is, the IDS will do a depth first search like DFS to depth 1, followed by a DFS to depth 2, and so on, so there may be each time starting completely from scratch. That is the main advantage of being complete this, as it covers almost all depths of the search tree. And also, it only requires the same memory just like this as depth first search (of course). 

In fact, you will have noticed that its means that it completely re-searches and the entire space for searched in the previous iteration. But this kind of redundancy will definitely make the search strategy for moving too slow to contemplate using in practice. Truly, it isn't as bad idea as you might think for this. This is just because, in the depth first search, most of the effort is mostly spent expanding the last row of the tree, so just for the repetition over the top part of the tree is a minor factor. However, the effect of this kind of the repetition reduces as the branching rate increases. In a search with branching rate 10 and depth 5, can reach the number of states searched is 111,111 with a single depth first search. With an iterative deepening search we see that, this number goes up to 123,456. So, there may be only a repetition of around 11%.

Posted Date: 1/9/2013 7:21:21 AM | Location : United States







Related Discussions:- Iterative deepening search, Assignment Help, Ask Question on Iterative deepening search, Get Answer, Expert's Help, Iterative deepening search Discussions

Write discussion on Iterative deepening search
Your posts are moderated
Related Questions
Declarative programming languages: We notice that declarative programming languages can have some better compensation over procedural ones. Actually, it is often said that a J

ID3 algorithm: Further for the calculation for information gain is the most difficult part of this algorithm. Hence ID3 performs a search whereby the search states are decisio

Draw and elucidate the block diagram of programmable interrupt controller 8259. The 8259A adds 8 vectored priority encoded interrupts to microprocessor. It can be expanded to 6

In general, all public processes of a controller class are treated as action processes. If you require prevent this default behaviour, just decorate the public process with NonActi

Categorized Optimization transformations The structure of program and the way in that data is defined and used in this provide vital clues for optimization. Optimization t

Advantages & Disadvantages Enhanced security and convenience: private keys never require be transmitting or revealing to anyone.  They can givce a method for digital signatu

A Lambda expression is not anything but an Anonymous Function, can have expressions and statements. Lambda expressions can be used mostly to make delegates or expression tree types

Give difference between top down parsing and bottom up parsing. Top down parsing: Specified an input string, top down parsing tries to derive a string identical to this by s

Main Objectives: Uploading codes into the microcontrollers Interfacing between both microcontrollers via I 2 C Reading and writing into various ports on the MCU Int

What do you understand by stepwise refinement of the program? The method of "Stepwise refinement" means to take an object and move it from a general perspective to a exact leve