At the forefront of Artificial Intelligence

Simple Tree Searches

This essay will cover very basic tree searches, the depth-first and breadth-first. In artificial intelligence, we use trees to represent a lot of things, from sentence structures, equations and even game states. Often, a method of searching the trees to find a specified goal is required - these algorithms are the simplest methods to do this.

Depth-first

As the name implies, the depth-first search transverses a tree all the way down a leaf node, before travelling back and searching again. In English, that sentence is best seen in a diagram:

The tree on the left is the tree we are interested in, with the bolded nodes being goals that will meet our goal criteria (whatever they might be). Now, the image on the left is the track depth-first algorithm will take (in red). It will travell down the leftmost node, until it gets to a leaf node (a node with no children). Then it will travel up to the previous node and explore any additional children that node might have. The blue arrows merely show how the algorithm would continue searching if it didn't find a goal state. How does this differ from the breadth-first search?

Breadth-first

Simple, instead of exploring the depth-first, it explores the breadth of the tree! Again, here is our diagram pair to help you visualize it:

Again, red arrows should how the algorithm would search until it found a goal state, and the blue arrows show how it would continue. You can see from this example that the breadth-first algorithm is a lot quicker, but it is not always the case, it all depends on your tree and the goal states you are looking for. We will look at the pros and cons of the two methods in a minute, but let us first look at the algorithms behind them.

The Algorithms

The algorithms are so similar I will present them to you side-by-side:

Depth-first

list CLOSED, OPEN = [StartNode] Mainloop: If OPEN = NULL, Stop // No goal! Set N = OPEN[0] if N is a goal node, stop. // Solution! Remove N from OPEN If N is in CLOSED goto Mainloop Add N to CLOSED Prepend any children of N to OPEN Goto Mainloop

Breadth-first

list CLOSED, OPEN = [StartNode] Mainloop: If OPEN = NULL, Stop // No goal! Set N = OPEN[0] if N is a goal node, stop. // Solution! Remove N from OPEN If N is in CLOSED goto Mainloop Add N to CLOSED Append any children of N to OPEN Goto Mainloop

This looks a bit confusing at first, but it will clear up upon explanation of OPEN and CLOSED. The OPEN list contains nodes that have not been looked at, and CLOSED contains all the nodes that have been explored. So, initially CLOSED is empty and OPEN is initialized to OPEN.

Now, in the first iteration of the loop, we set N to the first element of OPEN (in this case StartNode). StartNode is not a goal node, so we continue. We remove N from the OPEN list, and check whether it is in CLOSED. It won't be, so we add it. We then check for any children of N, and put those on the OPEN list to be explored. Perhaps another diagram and a step-through is necessary.

Depth-first Step-through

Iteration 0: OPEN = [StartNode], CLOSED = []
Iteration 1: OPEN = [b,c], CLOSED = [StartNode]
Iteration 2: OPEN = [d,e,c], CLOSED = [b,StartNode]
Iteration 3: OPEN = [e,c], CLOSED = [d,b,StartNode]
Iteration 4: OPEN = [f,g,c], CLOSED = [e,d,b,StartNode]
Iteration 5: F is a goal node!

If you still don't understand, use the above information and the algorithm. Now draw the diagram on a piece of paper and step through it bit by bit. The algorithm is not hard to figure out once you can visualize it. A breadth-first step-through will be pointless since our example doesn't step through that many times.

Notice where the depth-first and breadth-first algorithms differ though, child items are prepended on the list in depth-first, but appended in breadth-first.

Conclusion

The pros and cons of the each method normally are extremely relative to the tree is question, and the problem but hand. Breadth-first searches will always find the closest solution, but depth-first searches can be quicker under some circumstances (when there isn't a close solution) and the depth-first tends to use less memory.

Submitted: 06/11/2000

Article Toolbar

BibTeX entry