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 is Anonymous File Transfer Protocol? Anonymous FTP: While a FTP client contacts a server, in that case, the daemon will ask for an account number or username and it

Yes, it can be used, if an accurate clock frequency is not needed. Also, the component cost is low contrast to LC or Crystal.

Q. Explain Logical shifts with example? Logical shifts LOGICAL SHIFT LEFT and LOGICAL SHIFT RIGHT insert zeros to end bit position and other bits of a word are shifted left or

Elements of Parallel Computing and Architecture  Parallel computing. Then we shall describe why we need parallel computing and what the heights of parallel processing are. We s

State about AGP The latest addition to many computer systems is the inclusion of accelerated graphics port (AGP). AGP operates at the bus clock frequency of the microprocessor.

Fully Parallel Associative Processor (FPAP):  This processor accepts the bit parallel memory organisation. FPAP has two type of this associative processor named as: Word Org

Inspirations of artificial intelligence: Artificial Intelligence research can be easily understood by following example in terms of how the following question has been answere

Question 1: (a) Describe the two fundamental characteristics of antennas explaining in detail how it affects the security of wireless networks. (b) What is a wireless cli

Q. Explain Processing of an Interrupt? The interrupt is processed as: Step 1: Number field in INT instruction is multiplied by 4 to get its entry in interrupt vector table.

What is delegation? Delegation gives a proper mechanism to achieve the desired code reuse. The method is caught in the desired class and forwarded to another class for actual i