AI-Based Problem Solving

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 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.

Now 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:

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!

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

Writing 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.