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
Q. What is a virtual address? Von Neumann had suggested that execution of a program is possible only if program and data are residing in memory. In such a condition program len

program for finding the area under the curve   #include float start_point, /* GLOBAL VARIABLES */ end_point, total_area; int

Make ensure that "Use dynamic keyboard shortcuts" option in "Interface" tab of Preferences dialog is enabled, then go to the menu selection you are interested in. Keeping it select

Explain the two fundamental models of inter process communication. Two kinds of message passing system are given as: (a) Direct Communication : Along with direct communicat

Weight Training Calculations: However we have more weights in our network than in perceptrons but we firstly need to introduce the notation as: w ij just to specify the weigh

Q. When gravity is the merely force acting on an object the object is in what? Answer:- One respond is that it is in free-fall in a vacuum to eliminate atmospheric drag.

Static or Dynamic - artificial intelligence An environment is static if it doesn't change while an agent's program is making the decision about how to act. When programming ag

How do subroutines help in program writing? Some of the significant characteristics of Subroutine that help in program writing are: A subroutine is named, each have a

Explain about the Flash memories These are re-writable non-volatile memories evolved from EEPROM; they are generally connected to the USB port on the computer enabling a user t

Message in C++ : * Objects converse by sending messages to each other. * A message is sent to invoke a method in C++.   Method in C++: * Gives response to a message