HotLink Menu in RightSide Column 
Last Updated 6292010 


C++ DepthFirst Print Goal Path()Of course, no selfrespecting program wouldn't tell about the great work, it has just accomplished. For this reason, a little routine needs to display the path taken to arrive at our intended location:
A description of the code is given below:
C++ DepthFirst Main()Now that all of the necessary functions have been created. We can take this puppy for a test spin, and see what kind of results come out. Don't forget to complete the data table, and declare the functions, somewhere before they are used. We will need to make a couple of minor modifications to main, so it calls out the DepthFirst Search and prints the results. Listed below is the change to the main( ) function:
Cutting and pasting all of the above code examples, and placing them in a file called r5.cpp, adding in the necessary function declaration statements like: bool DepthFirstSearch(string, string); then compiling the file with the GNU C++ linux compiler gives us the following output:
Well, according to this result, we were better off with the BreadthFirst Search. I would suppose that sometimes the DepthFirst search might outperform the BreadthFirst Search, depending on how we stack the dataset. The timecomplexity of the BreadthFirst search is bounded by the size of the state space (which may be infinite). A depthfirst tree search, on the other hand, may generate all of the O(b^{m}) nodes in the search tree, where m is the maximum depth of any node; this can be much greater than the size of the state space. Note that m itself can be much larger than d (the depth of the shallowest solution) and is infinite if the tree is unbounded. So far, depthfirst search seems to have no clear advantage over breadthfirst search, so why even consider it? The reason is space complexity. For a graph search, there is no advantage whatsoever, but, a depthfirst tree search needs to store only a single path from the root to a leaf node, along with the remaining unexpanded sibling nodes for each node on the path. Once a node has been expanded, it can be removed from memory as soon as all of it's descendants have been fully explored as shown in figure DFS1. For a state space with branching factor b and maximum depth m, depthfirst search requires only O(bm) nodes. Using the same assumptions as for Figure BFS19 and assuming that nodes at the same depth as the goal node have no successors, we find that depthfirst search would require 156 kilobytes instead of 10 exabytes at depth d=16, a factor of 7 trillion times less space. This has led to the adoption of depthfirst tree search as the basic workhorse of many areas of AI, including constraint satisfaction, propositional satisfiability, and logic programming. We will now focus on the treesearch version of depthfirst search. A variant of depthfirst search called backtracking search uses still less memory. In backtracking, only one successor is generated at at time rather than all successors; each partially expanded node remembers which successor to generate next. In this way, only O(m) is needed rather than O(bm). Backtracking search facilitates yet another memory and time saving trick: the idea of generating a successor by modifying the current state description rather than copying it first. This reduces the memory requirements to just one state description and O(m) actions. For this to work, we must be able to undo each modification when we go back to generate the next successor. For problems with large state descriptions, such as robotic assembly, these techniques are critical to success. Depth Limited SearchThe embarrasing failure of depthfirst search in infinite state spaces can be alleviated by supplying depthfirst search with a predetermined depthlimit of l. That is, nodes at depth l are treated as if they have no successors. This approach is called Depth Limited Search. The depth limit solves the infinitepath problem. Unfortunately, it also introduces an additional source of incompleteness if we choose l<d, that is, the shallowest goal is beyond the depth limit (which is likely when d is unknown). Depth Limited Search will also be nonoptimal if we choose l>d. Its time complexity is O(b^{l}) and its space complexity is O(bl). Depthfirst search can be viewed as a special case of depthlimited search with l=∞. Sometimes, depth limits can be based on knowledge of the problem. For example, on the map of Romania there are 20 cities. Therefore, we know that if there is a solution, it must be of length 19 at the longest, so l=19 is a possible choice. But, in fact, if we studied the map carefully, we would discover that any city can be reached from any other city in at most 9 steps. This number, known as the diameter of the state space, gives us a better depth limit, which leads to a more efficient depthlimited search. For most problems, however, we will not know a good depth limit until we have solved the problem. Depthlimited search can be implemented as a simple modification to the general treegraph or graphsearch algorithm. Alternatively, it can be implemented as a simple recursive algorithm. Notice that depthlimited search has two modes of failure:
In order to continue with this guide, and start the discussion of Iterative Deepening Depth Search: Press the Button below: 
Big O Notation NP Completeness Intelligent Agents Formulating Problems Toy Problems Vacuum World 8 Queens The Knuth Sequence Real World Problems Route Finding Problems Touring Problems Traveling Salesperson Problem VLSI Layout Robot Navigation Automatic Assembly Sequencing Search Algorithm Infrastructure Child Node Creation Measuring Algorithm Performance BreadthFirst Search BreadthFirst Characteristics C++ BreadthFirst Search Code BreadthFirst Data Structure BreadthFirst Make Map BreadthFirst Make Neighbor BreadthFirst Point of Origin BreadthFirst Initial Listing BreadthFirst Get Child City C++ BreadthFirst Search Code UniformCost Search DepthFirst C++ Solution DepthFirst Data Structure DepthFirst Display Data DepthFirst Initial Listing DepthFirst Path Record DepthFirst Main() DepthLimited Search Bidirectional Search Comparing Strategies Greedy BestFirst A* Search Optimality of A* A* Search Data Structure A* Search Data Entry C++ Min Priority Queue C++ A* Headers & Prototypes C++ A* Search Main() 