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
What are the different between hypertext hypermedia? Hypertext is fundamentally the same like regular text; this can be stored, read or searched and edited along with a signifi

What are the roll and page areas? Roll and page areas are SAP R/3 buffers used to kept user contexts (process requests).  The SAP dispatcher assigns procedure requests to work

What is non-repudiation? Non Repudiation: Assurance that the sender is given with proof of delivery and that the recipient is provided with proof of the sender's identity so th

Question : Context aware mobile web applications are the important to achieve ubiquity, device independence and personalization. The context provides detailed information about

Interpolation Search The next task is to implement a variable size decrease-and-conquer solution to search. See Levitin [2007] pp 190 for a detailed description of the interpol

Consider the data with categorical predictor x 1 = { green or red } and numerical predictor x 2 and the class variable y shown in the following table. The weights for a round

what do you mean by inter leasing.how it is display the frame having 525 scan lines

The customers visit the website and browse through the products, looking at pictures and products details. When the customer finds his desired product, he usually adds it to his ca

Decision Tree Learning: Furthermore there is specified in the last lecture such as the representation scheme we choose to represent our learned solutions and the way that we l

Describe the VON NEUMANN ARCHITECTURE Most  of  present  computer  designs  are  based  on  idea  developed  by  John  vonNeumann referred to as the VON NEUMANN ARCHITECTURE. V