Depth−First is the second tutorial on AI search or pathfinding algorithms. Well, to begin with, there isn‘t much to say about depth first algorithm. It is mainly the breadth−first algorithm with a stack data structure, rather than a queue. Here is the pseudo code changed:

1. Let stack be a stack data structure
2. Add initial node to top of the stack
3. If stack is empty, then quit − a path could not be found
4. Let node be the node at the top of the stack
   1. If node is the goal node, then quit − a path has been found
   2. Expand node and push all its derived nodes to the top of the stack
5. Repeat from step 3

The only changes in the code are the data structure queue to stack. And this only occurs in our Problem and DepthFirst classes. Here is the Problem class changed:

⁄⁄ this class has operations to
⁄⁄ process our nodes and check
⁄⁄ the goal node
class Problem {
     public:
          ⁄⁄ our constructor that takes the initial
          ⁄⁄ location of the cell and the location of our goal cell
          ⁄⁄ and creates the initial node.
          ⁄⁄Problem(const Cell& start, const Cell& goal, int* map, int nrows, int ncols);

          ⁄⁄ our initial node
          Node* initialNode; // our initial node

          ⁄⁄ this method tells us if the node
          ⁄⁄ passed in the arguments is our goal node
          ⁄⁄ that is, it compares the row and column of the node
          ⁄⁄ with the row and column of our goal cell
          bool isGoal(Node* node);

          ⁄⁄ this method applies the operations specific to our
          ⁄⁄ problem and generates the successors of the node
          void successors(Node* node, stack& _stack);
     private:
          ⁄⁄ this method is called by the successors method
          ⁄⁄ and tells us if by applying the operator
          ⁄⁄ defined by opindex is a valid successor
          bool expand(Node* node, Cell& cell, int opindex, string& oper);
          int* map; // our grid map
          Cell goal; // our goal cell
          int ncols; // the number of columns in the map
          int nrows; // the number of rows in the map
          ⁄⁄ it is used for the id of each node
          static int totalnodes; // the total number of nodes generated
};

And here is our DepthFirst class:

⁄⁄ this class implements our
⁄⁄ breadth first search algorithm
class DepthFirst {
     public:
          ⁄⁄ our constructor that takes a problem
          ⁄⁄ to solve
          DepthFirst(Problem& problem);

          ⁄⁄ this is our search method
          ⁄⁄ it returns 0 (null) if there isn't a
          ⁄⁄ solution or a node if it found a solution
          Node* search();
     private:
          stack _stack; ⁄⁄ our stack data structure
          Problem problem; ⁄⁄ the problem to be solved
};

and its search method:

⁄⁄ our search algorithm
Node* BreadthFirst::search() {
     Node* node; ⁄⁄ our node

     ⁄⁄ while our stack is not empty
     while (!_stack.empty()) {
          node = _stack.top(); ⁄⁄ get the node at the top of the stack
          _stack.pop(); ⁄⁄ remove it from the top of the stack
          ⁄⁄ check if this is our goal
          if (problem.isGoal(node))
               return node; ⁄⁄ return it as a result if this is our goal

          ⁄⁄ get the successors of this node
          ⁄⁄ and append them to the queue
          problem.successors(node, _stack);
     }

     return 0; ⁄⁄ not solution was found
}

If you have read the breadth−first tutorial, you should be able to recognise this code and also understand it, as it is the same, except for the data structure used.

But there is one thing that you have to know and that is what I have left for last. First, I have changed the start and goal nodes in the map because of a particular reason I am going to explain below. First let‘s have a look at the map:

The reason why I have chosen this particular start and goal nodes, is because the depth−first search can get stuck going down the wrong path. This happens if the problem has a very deep or infinite search trees. Therefore, depth−first search will never be able to recover for an unlucky choice at one of the nodes near the top of the tree. The search will always continue downward without backing up, even when a shallow soution exists. Thus, on these problems depth−first search will either get stuck in a infinite loop and never return a solution, or it may eventually find a solution path that is longer than the optimal solution. The start node and goal node I have chosen gives us a solution, which is by far non−optimal. You can try this map with the Breadth−First class to see the difference. If I had use the same map used in the breadth−first search class, than our search would get stuck in an infinite loop. It is always clearer when you play with it. If you use a map with smaller cells, than you get a better chance of finding a solution (which is non−optimal, of course). Play around with the map size and the choice of start and goal nodes to see.

The source code for this tutorial can be downloaded from here. I was wondering if this was really necessary. But anyway, just provide it. You could just change the code from the breadth−first algorithm.

That‘s it for this tutorial.

If you have any queries, do not hesitate to concact me.

All the best

Fidel.