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
Protocol used to monitor and control network devices operates at? Protocol operates at application layer to monitor and control network devices operates.

How many types of size categories and data classes are there? There are five size categories (0-4) and 11 data classes only three of which are suitable for application tables:

Resolution Method: For a minor miracle occurred in 1965 where Alan Robinson published his resolution method as uses a method to generalised version of the resolution rule of i

Define clock rate? The clock rate is given by, R=1/P, where P is the length of single clock cycle.

Problem 1. Explain briefly the process of matching production rules against working memory 2. What are the different kinds of knowledge that need to be represented in AI? Ex

Introduction to object oriented Analysis & design: tools In case of OOAD, Unified Modelling Language (UML) is a well accepted language. It is used for constructing, visualizin

Discuss the various enhanced services that can be made available to the subscribers because of stored program control. One of the instant benefits of stored program control is

why they are essential in a bus oriented system? Ans) In a multiplexed bus system, many devices are linked to a common bus. If 2 or more devices attempt to use the bus at the si

Q. Creating a New Directory in DOS? You can create any directory under any directory in the hard disk or floppy disk. The command to create a new directory is MKDIR or MD. To c

CMOS circuits consume power ? Ans. As in CMOS one device is ON and one is Always OFF therefore power consumption is low or can say less than TTL.