AI-Based Problem Solving - Search Techniques
(Page 2 of 9 )
There are several ways to search for a solution. The four most fundamental are
- Depth first
- Breadth first
- Hill climbing
- Least cost
In the course of this chapter, each of these searches is examined.
Evaluating a Search Evaluating the performance of an AI-based search technique can be complicated. Fortunately, for our purposes we are concerned only with these two measurements:
- How quickly a solution is found
- How good the solution is
There are several types of problems for which all that matters is that a solution, any solution, be found with the minimum effort. For these problems, the first measurement is especially important. In other situations, the quality of the solution is more important.
The speed of a search is affected both by the size of the search space and by the number of nodes actually traversed in the process of finding the solution. Because backtracking from dead ends is wasted effort, you want a search that seldom retraces its steps.
In AI-based searching, there is a difference between finding the best solution and finding a good solution. Finding the best solution can require an exhaustive search because sometimes this is the only way to know that the best solution has been found. Finding a good solution, in contrast, means finding a solution that is within a set of constraints—it does not matter if a better solution might exist.
As you will see, the search techniques described in this chapter all work better in certain situations than in others, so it is difficult to say whether one search method is always superior to another. But some search techniques have a greater probability of being better for the average case. In addition, the way a problem is defined can sometimes help you choose an appropriate search method.
The ProblemNow let us consider the problem that we will use various searches to solve. Imagine that you are a travel agent and a rather quarrelsome customer wants you to book a flight from New York to Los Angeles with XYZ Airlines. You try to tell the customer that XYZ does not have a direct flight from New York to Los Angeles, but the customer insists that XYZ is the only airline that he will fly. Thus, you must find connecting flights between New York and Los Angeles. You consult XYZ’s scheduled flights, shown here:
New York to Chicago | 900 miles |
Chicago to Denver | 1000 miles |
New York to Toronto | 500 miles |
New York to Denver | 1800 miles |
Toronto to Calgary | 1700 miles |
Toronto to Los Angeles | 2500 miles |
Toronto to Chicago | 500 miles |
Denver to Urbana | 1000 miles |
Denver to Houston | 1000 miles |
Houston to Los Angeles | 1500 miles |
Quickly you see that there are connections that enable your customer to fly from New York to Los Angeles. The problem is to write a Java program that does the same thing that you just did in your head!
A Graphic Representation The flight information in XYZ’s schedule can be translated into the directed graph shown in Figure 10-3. A directed graph is simply a graph in which the lines connecting each node
Figure 1-3. A directed graph of XYZ's flight schedule
include an arrow to indicate the direction of motion. In a directed graph, you cannot travel against the direction of the arrow.
To make things easier to understand, we can redraw this graph in a treelike fashion, as shown in Figure 10-4. Refer to this version for the rest of this chapter. The goal, Los Angeles, is circled. Notice also that various cities appear more than once to simplify the construction of the graph. Thus, the treelike representation does not depict a binary tree. It is simply a visual convenience.
Now we are ready to develop the various search programs that will find paths from New York to Los Angeles.
Figure 10-4. A tree version of XYZ's flight schedule
The FlightInfo ClassWriting a program to find a route from New York to Los Angeles requires a database that contains the information about XYZ’s flights. Each entry in the database must contain the departure and destination cities, the distance between them, and a flag that aids in backtracking. This information is held in a class called FlightInfo, shown here:
// Flight information.
class FlightInfo {
String from;
String to;
int distance;
boolean skip; // used in backtracking
FlightInfo(String f, String t, int d) {
from = f;
to = t;
distance = d;
skip = false;
}
}
This class will be used by all the search techniques described in the remainder of the chapter.
Next: The Depth-First 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 
