AIBased Problem Solving
by Herb Schildt
To conclude this book, we will examine a topic from an interesting discipline of programming: artificial intelligence (AI). As explained earlier, the goal of this book is to show the richness and power of the Java language. Perhaps nothing demonstrates that better than its application to the demanding realm of artificial intelligence. Java's powerful string-handling capabilities and Stack class streamline many types of AI-based code. Java's object model keeps the code clean, as does its garbage collection facility. As this final chapter shows, Java is a language well suited to the AI developer.
The field of artificial intelligence is comprised of several fascinating areas, but fundamental to many AI-based applications is problem solving. Essentially, there are two types of problems. The first type can be solved through the use of some sort of deterministic procedure that is guaranteed success, such as the computation of the sine of an angle or the square root of a value. These types of problems are easily translated into algorithms that a computer can execute. In the real world, however, few problems lend themselves to such straightforward solutions. Instead, many problems can be solved only by searching for a solution. It is this type of problem solving with which AI is concerned. It is also the type of searching that is explored in this chapter.
To understand why searching is so important to AI, consider the following. One of the early goals of AI research was the creation of a general problem solver. A general problem solver is a program that can produce solutions to all sorts of different problems about which it has no specific, designed-in knowledge. It is an understatement to say that such a program would be highly desirable. Unfortunately, a general problem solver is as difficult to realize as it is tantalizing. One complication is the sheer size and complexity of many real-world situations. Because a general problem solver must search for a solution through what might be a very large, mazelike universe of possibilities, finding ways to search such an environment is a priority. Although we won't attempt something as ambitious as a general problem solver in this chapter, we will explore several AI-based search techniques that are applicable to a wide variety of problems.
Representation and Terminology
Imagine that you have lost your car keys. You know that they are somewhere in your house, which looks like this:
|
Bedroom 2 / |
Bedroom 1 |
/ | ||
|
Hall / | ||||
|
Master bedroom |
Living room | |||
You are standing at the front door (where the X is). As you begin your search, you check the living room. Then you go down the hall to the first bedroom, through the hall to the second bedroom, back to the hall, and to the master bedroom. Not having found your keys, you backtrack further by going back through the living room. Finally, you find your keys in the kitchen. This situation is easily represented by a graph, as shown in Figure 10-1. Representing search problems in graphical form is helpful because it provides a convenient way to depict the way a solution was found.
With the preceding discussion in mind, consider the following terms, which will be used throughout this chapter:
|
Terminal node |
A node that ends a path |
|
Search space |
The set of all nodes |
|
Goal |
The node that is the object of the search |
|
Heuristics |
Information about whether any specific node is a better next choice than another |
Solution path A directed graph of the nodes visited en route to the goal
Solution path A directed graph of the nodes visited en route to the goal
In the example of the lost keys, each room in the house is a node; the entire house is the search space; the goal, as it turns out, is the kitchen; and the solution path is shown in Figure 10-1. The bedrooms, kitchen, and the bath are terminal nodes because they lead nowhere. Heuristics are not represented on a graph. Rather, they are techniques that you might employ to help you better choose a path.
Start
Living room
Start
Living room
Figure 10-1 The solution path to find the missing keys
Combinatorial Explosions
Given the preceding example, you may think that searching for a solution is easy—you start at the beginning and work your way to the conclusion. In the extremely simple case of the lost keys, this is not a bad approach because the search space is so small. But for many problems (especially those for which you would want to use a computer) the number of nodes in the search space is very large, and as the search space grows, so does the number of possible paths to the goal. The trouble is that often, adding another node to the search space adds more than one path. That is, the number of potential pathways to the goal can increase in a nonlinear fashion as the size of the search space grows. In a nonlinear situation, the number of possible paths can quickly become very large.
For instance, consider the number of ways three objects—A, B, and C—can be arranged on a table. The six possible permutations are
|
A |
C |
B |
|
B |
C |
A |
|
B |
A |
C |
|
C |
B |
A |
You can quickly prove to yourself that these six are the only ways that A, B, and C can be arranged. However, you can derive the same number by using a theorem from the branch of mathematics called combinatorics—the study of the way things can be combined. According to the theorem, the number of ways that N objects can be arranged is equal to N! (N factorial). The factorial of a number is the product of all whole numbers equal to or less than itself down to 1. Therefore, 3! is 3 x 2 x 1, or 6. If you had four objects to arrange, there would be 4!, or 24, permutations. With five objects, the number is 120, and with six it is 720. With 1000 objects the number of possible permutations is huge! The graph in Figure 10-2 gives you a visual feel for what is sometimes referred to as a combinatorie explosion. Once there are more than a handful of possibilities, it very quickly becomes difficult to examine (indeed, even to enumerate) all the arrangements.
This same sort of combinatorial explosion can occur in paths through search spaces. Because of this, only the simplest of problems lend themselves to exhaustive searches. An exhaustive search is one that examines all nodes. Thus, it is a "brute-force" technique. Brute force always works but is not often practical for large problems because it consumes too much time, too many computing resources, or both. For this reason, AI-based search techniques were developed.
- Figure 10-2 A combinatorie explosion with factorials
Search Techniques
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 Problem
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:
|
Flight |
Distance |
|
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 |
|
Denver to Los Angeles |
1000 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 10-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.
New York
New York
Chicago Toronto
Denver
Chicago Toronto
Denver
- Denver ( Las Angeles ) Chicago Calgary { Los Angeles )
- Los Angeles ) Houston Urbana
- Los Angeles ) Houston Urbana
- Los Angeles )
Figure 10-4 A tree version of XYZ's flight schedule
The FlightInfo Class
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.
The Depth-First Search
The depth-first search explores each possible path to its conclusion before another path is tried. To understand exactly how this works, consider the tree that follows. F is the goal.
- Start
A depth-first search traverses the graph in the following order: ABDBEBACF. If you are familiar with trees, you recognize this type of search as an inorder tree traversal. That is, the path goes left until a terminal node is reached or the goal is found. If a terminal node is reached, the path backs up one level, goes right, and then left until either the goal or a terminal node is encountered. This procedure is repeated until the goal is found or the last node in the search space has been examined.
As you can see, a depth-first search is certain to find the goal because in the worst case it degenerates into an exhaustive search. In this example, an exhaustive search would result if G were the goal.
The depth-first approach is encapsulated within the Depth class, which begins like this:
class Depth {
final int MAX = 100; // maximum number of connections
// This array holds the flight information.
Flightlnfo flights[] = new FlightInfo[MAX];
int numFlights = 0; // number of entries in flight array
Stack btStack = new Stack(); // backtrack stack public static void main(String args[])
String to, from;
BufferedReader br = new
BufferedReader(new InputStreamReader(System.in));
try {
- out.print("From? "); from = br.readLine(); System.out.print("To? "); to = br.readLine();
- isflight(from, to);
} catch (IOException exc) {
System.out.println("Error on input.");
An array of FlightInfo objects called flights is created, which holds the flight information. The size of this array is set by use of the final variable MAX. The number of flights actually stored in the array is held in numFlights. Note that it would have been possible to store the flight information in one of Java Collections classes, such as in an ArrayList. Doing so would allow arbitrarily sized lists of information. However, because we are storing information about only a few flights, an array is used for the sake of simplicity and clarity.
The Stack object that will be used for backtracking is created, and a reference to it is stored in btStack. As you will see, the backtrack stack is very important to all the search techniques.
Inside main( ), the setup( ) method is called, which initializes the flight information. Next, the user is prompted for the departure and destination cities. Then, isflight( ) is called to find a flight or a set of connecting flights between the two cities, which in this example are New York and Los Angeles. Finally, if a route between the two cities is found, it is displayed. Now, let's look at the various pieces.
The setup( ) method works by repeatedly calling the addFlight( ) method, which adds a flight to the flights array. The value of numFlights is incremented with each added flight. Thus, when setup( ) returns, numFlights is equal to the number of flights in the database. The setup( ) and addFlight( ) methods are shown here:
addFlight addFlight addFlight addFlight addFlight addFlight addFlight addFlight addFlight addFlight addFlight
ze the flight database.
"New York", "Chicago", 9 00); "Chicago", "Denver", 1000); "New York", "Toronto", 500); "New York", "Denver", 1800); "Toronto", "Calgary", 1700); "Toronto", "Los Angeles", 2500) "Toronto", "Chicago", 500); "Denver", "Urbana", 1000); "Denver", "Houston", 1000); "Houston", "Los Angeles", 1500) "Denver", "Los Angeles", 1000);
// Put flights into the database.
void addFlight(String from, String to, int dist) {
if(numFlights < MAX) { flights[numFlights] =
new FlightInfo(from, to, dist);
numFlights++;
else System.out.println("Flight database full.Xn");
To find a route between New York and Los Angeles, several support methods are needed. The first is match( ), which determines if there is a flight between two cities. If no such flight exists, it returns zero; or if there is a flight, it returns the distance between the two cities. This method is shown here:
/* If there is a flight between from and to, return the distance of flight; otherwise, return 0. */
int match(String from, String to) {
for(int i=numFlights-1; i > -1; i--) { if(flights[i].from.equals(from) && flights[i].to.equals(to) && !flights[i].skip)
flights[i].skip = true; // prevent reuse return flights[i].distance;
The next support method is find( ). Given a departure city, find( ) searches the database for any connection. If a connection is found, the FlightInfo object associated with that connection is returned. Otherwise, null is returned. Thus, the difference between match( ) and find() is that match() determines if there is a flight between two specific cities, whereas find( ) determines if there is a flight from a given city to any other city. The find( ) method follows:
// Given from, find any connection.
FlightInfo find(String from) {
for(int i=0; i < numFlights; i++) { if(flights[i].from.equals(from) && !flights[i].skip)
FlightInfo f = new FlightInfo(flights[i].from, flights[i].to, flights[i].distance); flights[i].skip = true; // prevent reuse return f;
return null;
In both match( ) and find( ), connections that have the skip field set to 1 are bypassed. Also, if a connection is found, its skip field is set. This manages backtracking from dead ends, preventing the same connections from being tried over and over again.
Now consider the code that actually finds the connecting flights. It is contained in the isflight( ) method, the key routine in finding a route between two cities. It is called with the names of the departure and destination cities.
// Determine if there is a route between from and to.
void isflight(String from, String to) {
int dist;
Flightlnfo f;
// See if at destination.
btStack.push(new FlightInfo(from, to, dist)); return;
// Try another connection.
btStack.push(new FlightInfo(from, to, f.distance)); isflight(f.to, to);
// Backtrack and try another connection, f = (Flightlnfo) btStack.pop(); isflight(f.from, f.to);
Let's examine this method closely. First, the flight database is checked by match( ) to see if there is a flight between from and to. If there is, the goal has been reached, the connection is pushed onto the stack, and the method returns. Otherwise, it uses find( ) to find a connection between from and any place else. The find( ) method returns the Flightlnfo object describing the connection, if one is found, or null if no connecting flights are available. If there is such a flight, this connection is stored in f, the current flight is pushed onto the backtrack stack, and isflight( ) is called recursively, with the city in f.to becoming the new departure city. Otherwise, backtracking takes place. The previous node is removed from the stack and isflight( ) is called recursively. This process continues until the goal is found.
For example, if isflight( ) is called with New York and Chicago, the first if would succeed and isflight() would terminate because there is a direct flight from New York to Chicago. The situation is more complex when isflight( ) is called with New York and Calgary. In this case, the first if would fail because there is no direct flight connecting these two cities. Next, the second if is tried by attempting to find a connection between New York and any other city. In this case, find( ) first finds the New York to Chicago connection, this connection is pushed onto the backtrack stack, and isflight() is called recursively with Chicago as the starting point. Unfortunately, there is no path from Chicago to Calgary and several false paths are followed. Eventually, after several recursive calls to isflight( ) and substantial backtracking, the connection from New York to Toronto is found, and Toronto connects to Calgary. This causes isflight( ) to return, unraveling all recursive calls in the process. Finally, the original call to isflight( ) returns. You might want to try adding println( ) statements in isflight( ) to see precisely how it works with various departure and destination cities.
It is important to understand that isflight( ) does not actually return the solution—it generates it. Upon exit from isflight( ), the backtrack stack contains the route between New York and Calgary. That is, the solution is contained in btStack. Furthermore, the success or failure of isflight( ) is determined by the state of the stack. An empty stack indicates failure; otherwise, the stack holds a solution.
In general, backtracking is a crucial ingredient in AI-based search techniques. Backtracking is accomplished through the use of recursion and a backtrack stack. Almost all backtracking situations are stack-like in operation—that is, they are first in, last out. As a path is explored, nodes are pushed onto the stack as they are encountered. At each dead end, the last node is popped off the stack and a new path, from that point, is tried. This process continues until either the goal is reached or all paths have been exhausted.
You need one more method, called route( ), to complete the entire program. It displays the path and the total distance. The route( ) method is shown here:
// Show the route and total distance.
void route(String to) {
FlightInfo f;
// Reverse the stack to display route.
for(int i=0; i < num; i++) rev.push(btStack.pop());
for(int i=0; i < num; i++) { f = (Flightlnfo) rev.pop(); System.out.print(f.from + " to "); dist += f.distance;
- out.println(to);
- out.println("Distance is " + dist);
Notice the use of a second stack called rev. The solution stored in btStack is in reverse order, with the top of the stack holding the last connection and the bottom of the stack holding the first connection. Thus, it must be reversed in order to display the connection in the proper sequence. To put the solution into its proper order, the connections are popped from btStack and pushed onto rev.
The entire depth-first search program follows:
- Find connections using a depth-first search, import java.util.*; import java.io.*;
- 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;
class Depth {
final int MAX = 100; // maximum number of connections
// This array holds the flight information. Flightlnfo flights[] = new FlightInfo[MAX];
int numFlights = 0; // number of entries in flight array
Stack btStack = new Stack(); // backtrack stack public static void main(String args[]) {
String to, from; Depth ob = new Depth(); BufferedReader br = new
BufferedReader(new InputStreamReader(System.in)); ob.setup(); try {
- out.print("From? "); from = br.readLine(); System.out.print("To? "); to = br.readLine();
- isflight(from, to);
if(ob.btStack.size() != 0) ob.route(to); } catch (IOException exc) {
System.out.println("Error on input.");
// Initialize the flight database.
addFlight( addFlight( addFlight( addFlight( addFlight( addFlight( addFlight( addFlight( addFlight( addFlight( addFlight(
New York", "Chicago", 9 00) Chicago", "Denver", 1000); New York", "Toronto", 5 00) New York", "Denver", 18 00) Toronto", "Calgary", 1700) Toronto", "Los Angeles", 2500) Toronto", "Chicago", 500); Denver", "Urbana", 1000); Denver", "Houston", 1000); Houston", "Los Angeles", 1500) Denver", "Los Angeles", 1000);
// Put flights into the database.
void addFlight(String from, String to, int dist) {
if(numFlights < MAX) { flights[numFlights] =
new FlightInfo(from, to, dist);
numFlights++;
else System.out.println("Flight database full.Xn");
// Show the route and total distance, void route(String to)
Stack rev = new Stack(); int dist = 0; Flightlnfo f; int num = btStack.size();
// Reverse the stack to display route. for(int i=0; i < num; i++) rev.push(btStack.pop());
for(int i=0; i < num; i++) { f = (Flightlnfo) rev.pop(); System.out.print(f.from + " to "); dist += f.distance;
- out.println(to);
- out.println("Distance is " + dist);
/* If there is a flight between from and to, return the distance of flight; otherwise, return 0. */
int match(String from, String to) {
for(int i=numFlights-1; i > -1; i--) { if(flights[i].from.equals(from) && flights[i].to.equals(to) && !flights[i].skip)
flights[i].skip = true; // prevent reuse return flights[i].distance;
// Given from, find any connection.
Flightlnfo find(String from) {
for(int i=0; i < numFlights; i++) { if(flights[i].from.equals(from) && !flights[i].skip)
Flightlnfo f = new FlightInfo(flights[i].from, flights[i].to, flights[i].distance); flights[i].skip = true; // prevent reuse return f;
return null;
// Determine if there is a route between from and to.
void isflight(String from, String to) {
int dist; FlightInfo f;
// See if at destination, dist = match(from, to); if(dist != 0) {
btStack.push(new FlightInfo(from, to, dist)); return;
// Try another connection, f = find(from); if(f != null) {
btStack.push(new FlightInfo(from, to, f.distance)); isflight(f.to, to);
// Backtrack and try another connection, f = (Flightlnfo) btStack.pop(); isflight(f.from, f.to);
Notice that main( ) prompts you for both the city of origin and the city of destination. This means that you can use the program to find routes between any two cities. However, the rest of this chapter assumes that New York is the origin and Los Angeles is the destination.
When run with New York as the origin and Los Angeles as the destination, the following solution is displayed. As Figure 10-5 shows, this is indeed the first solution that would be found by a depth-first search. It is also a fairly good solution.
From? New York To? Los Angeles
New York to Chicago to Denver to Los Angeles Distance is 2900
Start New York
Chicago Toronto Denver
Denver Los Angeles Chicago Calgary Los Angeles
I Los Angeles ) Houston Urbana
Los Angeles
Figure 10-5 The depth-first path to a solution
An Analysis of the Depth-First Search
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:
- Start
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);
// Backtrack and try another connection.
f = (Flightlnfo) 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.
Start New York
Chicago
Toronto
Denver
Denver ( Los Angeles ) Chicago Calgary Los Angeles
First Solution
Los Angeles
Houston
Urbana
Post a comment