AI-Based Problem Solving - An Analysis of the Depth-First Search
(Page 4 of 9 )
The depth-first approach found a good solution. Also, relative to this specific problem, depth-first searching found this solution on its first try with no backtracking—this is very good; but had the data been organized differently, finding a solution might have involved considerable backtracking. Thus, the outcome of this example cannot be generalized. Moreover, the performance of depth-first searches can be quite poor when a particularly long branch with no solution at the end is explored. In this case, a depth-first search wastes time not only exploring this chain but also backtracking to the goal.
The Breadth-First Search The opposite of the depth-first search is the breadth-first search. In this method, each node on the same level is checked before the search proceeds to the next deeper level. This traversal method is shown here with C as the goal:
Although thinking in terms of a binary tree–structured search space makes it easy to describe the actions of a breadth-first search, many search spaces, including our flight example, are not binary trees. So precisely what constitutes “breadth” is a bit subjective in that it is defined by the problem at hand. As it relates to our flight example, the breadth-first approach is implemented by checking if any flight leaving the departure city connects to a flight that reaches the destination. In other words, before advancing to another level, the destinations of all connections of connecting flights are checked.
To make the route-seeking program perform a breadth-first search, you need to make an alteration to isflight( ), as shown here:
/* Determine if there is a route between from and to using
breadth-first search. */
void isflight(String from, String to)
{
int dist, dist2;
FlightInfo f;
// This stack is needed by the breadth-first search.
Stack resetStck = new Stack();
// See if at destination.
dist = match(from, to);
if(dist != 0) {
btStack.push(new FlightInfo(from, to, dist));
return;
}
/* Following is the first part of the breadth-first
modification. It checks all connecting flights
from a specified node. */
while((f = find(from)) != null) {
resetStck.push(f);
if((dist = match(f.to, to)) != 0) {
resetStck.push(f.to);
btStack.push(new FlightInfo(from, f.to, f.distance));
btStack.push(new FlightInfo(f.to, to, dist));
return;
}
}
/* The following code resets the skip fields set by
preceding while loop. This is also part of the
breadth-first modification. */
int i = resetStck.size();
for(; i!=0; i--)
resetSkip((FlightInfo) resetStck.pop());
// Try another connection.
f = find(from);
if(f != null) {
btStack.push(new FlightInfo(from, to, f.distance));
isflight(f.to, to);
}
else if(btStack.size() > 0) {
// Backtrack and try another connection.
f = (FlightInfo) btStack.pop();
isflight(f.from, f.to);
}
}
Two changes have been made. First, the while loop checks all flights leaving from the departure city (from) to see if they connect with flights that arrive at the destination city. Second, if the destination is not found, the skip fields of those connecting flights are cleared by calling resetSkip( ). The connections that need to be reset are stored on their own stack, called resetStck, which is local to isflight( ). Resetting the skip flags is necessary to enable alternative paths that might involve those connections.
The resetSkip( ) method is shown here:
// Reset skip field of specified flight.
void resetSkip(FlightInfo f) {
for(int i=0; i< numFlights; i++)
if(flights[i].from.equals(f.from) &&
flights[i].to.equals(f.to))
flights[i].skip = false;
}
To try the breadth-first search, substitute the new version of isflight( ) into the preceding search program and then add the resetSkip( ) method. When run, it produces the following solution:
From? New York
To? Los Angeles
New York to Toronto to Los Angeles
Distance is 3000
Figure 10-6 shows the breadth-first path to the solution.
An Analysis of the Breadth-First Search In this example, the breadth-first search performed fairly well, finding a reasonable solution. As before, this result cannot be generalized because the first path to be found depends on the physical organization of the information. The example does illustrate, however, how depth-first and breadth-first searches often find different paths through the same search space.
Breadth-first searching works well when the goal is not buried too deeply in the search space. It works poorly when the goal is several layers deep. In this case, a breadth-first search expends substantial effort during the backtrack stage.
Figure 10-6. The breadth-first path to a solution
Adding Heuristics
Neither the depth-first nor the breadth-first search attempts to make any educated guesses about whether one node in the search space is closer to the goal than another. Instead, they simply move from one node to the next using a prescribed pattern until the goal is finally found. This may be the best you can do for some situations, but often a search space contains information that you can use to increase the probability that a search will reach its goal faster. To take advantage of such information, you must add heuristic capabilities to the search.
Heuristics are simply rules that increase the likelihood that a search will proceed in the correct direction. For example, imagine that you are lost in the woods and need a drink of water. The woods are so thick that you cannot see far ahead, and the trees are too big to climb to get a look around. However, you know that rivers, streams, and ponds are most likely in valleys; that animals frequently make paths to their watering places; that when you are near water it is possible to “smell” it; and that you can hear running water. So, you begin by moving downhill because water is unlikely to be uphill. Next, you come across a deer trail that also runs downhill. Knowing that this may lead to water, you follow it. You begin to hear a slight rushing off to your left. Knowing that this may be water, you cautiously move in that direction. As you move, you begin to detect the increased humidity in the air; you can smell the water. Finally, you find a stream and have your drink. In this situation, the heuristic information used to find the water did not guarantee success, but it did increase the probability of an early success. In general, heuristics improve the odds in favor of quickly finding a goal.
Most often, heuristic search methods are based on maximizing or minimizing some constraint. In the problem of scheduling a flight from New York to Los Angeles, there are two possible constraints that a passenger may want to minimize. The first is the number of connections that have to be made. The second is the length of the route. Remember, the shortest route does not necessarily imply the fewest connections, or vice versa. In this section, two heuristic searches are developed. The first minimizes the number of connections. The second minimizes the length of the route. Both heuristic searches are built on the depth-first search framework.
Next: The Hill-Climbing Search >>
More Java Articles
More By McGraw-Hill/Osborne
|
 This article is excerpted from chapter 10 of The Art of Java, written by Herbert Schildt (McGraw-Hill/Osborne, 2004; ISBN: 0072229713). Check it out at your favorite bookstore. Buy this book now.
|
|
/ 9 
