Home arrow Java arrow Page 3 - AI-Based Problem Solving
JAVA

AI-Based Problem Solving


Java is well-suited the programming discipline of artificial intelligence. Java's string-handling capabilities and Stack class make it easy to handle many types of AI-based code. If you would like to learn more about using Java to solve AI problems, keep reading. This article is excerpted from chapter ten of The Art of Java, written by Herbert Schildt (McGraw-Hill/Osborne, 2004; ISBN: 0072229713).

Author Info:
By: McGraw-Hill/Osborne
Rating: 4 stars4 stars4 stars4 stars4 stars / 30
June 02, 2005
TABLE OF CONTENTS:
  1. · AI-Based Problem Solving
  2. · Search Techniques
  3. · The Depth-First Search
  4. · An Analysis of the Depth-First Search
  5. · The Hill-Climbing Search
  6. · An Analysis of Hill Climbing
  7. · Node Removal
  8. · Finding the “Optimal” Solution
  9. · Back to the Lost Keys

print this article
SEARCH DEVARTICLES

AI-Based Problem Solving - The Depth-First Search
(Page 3 of 9 )

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.

 

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.
    FlightInfo 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 {
      System.out.print("From? ");
      from = br.readLine();
      System.out.print("To? ");
      to = br.readLine();
     
ob.isflight(from, to);
     
if(ob.btStack.size() != 0)
        ob.route(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:

// Initialize the flight database.
void setup()
{
 
addFlight("New York", "Chicago", 900);
 
addFlight("Chicago", "Denver", 1000);
 
addFlight("New York", "Toronto", 500);
 
addFlight("New York", "Denver", 1800);
 
addFlight("Toronto", "Calgary", 1700);
 
addFlight("Toronto", "Los Angeles", 2500);
 
addFlight("Toronto", "Chicago", 500);
 
addFlight("Denver", "Urbana", 1000);
 
addFlight("Denver", "Houston", 1000);
 
addFlight("Houston", "Los Angeles", 1500);
 
addFlight("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.\n");
}

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;
     
}
    }
   
return 0; // not found
  }

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)
      {
        F
lightInfo 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 a ctually 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;
 
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);
  }
  else if(btStack.size() > 0) {
   
// Backtrack and try another connection.
   
f = (FlightInfo) 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 FlightInfo 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)
{
 
Stack rev = new Stack();
 
int dist = 0;
 
FlightInfo 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 = (FlightInfo) rev.pop();
   
System.out.print(f.from + " to ");
   
dist += f.distance;
  }
 
System.out.println(to);
  System.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.
    FlightInfo 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 {
      System.out.print("From? ");
      from = br.readLine();
      System.out.print("To? ");
      to = br.readLine();
      ob.isflight(from, to);
      if(ob.btStack.size() != 0)
        ob.route(to);
    } catch
(IOException exc) {
      System.out.println("Error on input.");
    }
  }
 
// Initialize the flight database.
  void setup()
  {
    addFlight("New York", "Chicago", 900);
    addFlight("Chicago", "Denver", 1000);
    addFlight("New York", "Toronto", 500);
    addFlight("New York", "Denver", 1800);
    addFlight("Toronto", "Calgary", 1700);
    addFlight("Toronto", "Los Angeles", 2500);
    addFlight("Toronto", "Chicago", 500);
    addFlight("Denver", "Urbana", 1000);
    addFlight("Denver", "Houston", 1000);
    addFlight("Houston", "Los Angeles", 1500);
    addFlight("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.\n");
    
}
   
// Show the route and total distance.
    void route(String to)
    {
     
Stack rev = new Stack();
      int dist = 0;
      FlightInfo 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 = (FlightInfo) rev.pop();
        System.out.print(f.from + " to ");
        dist += f.distance;
     
}
      
System.out.println(to);
      System.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;
       
}
      }
      return 0; // not found
    }
    
// 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;
    }
    // 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);
      }
      else if(btStack.size() > 0) {
       
// Backtrack and try another connection.
        f = (FlightInfo) 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

 
Figure 10-5.  The depth-first path to a solution


blog comments powered by Disqus
JAVA ARTICLES

- Java Too Insecure, Says Microsoft Researcher
- Google Beats Oracle in Java Ruling
- Deploying Multiple Java Applets as One
- Deploying Java Applets
- Understanding Deployment Frameworks
- Database Programming in Java Using JDBC
- Extension Interfaces and SAX
- Entities, Handlers and SAX
- Advanced SAX
- Conversions and Java Print Streams
- Formatters and Java Print Streams
- Java Print Streams
- Wildcards, Arrays, and Generics in Java
- Wildcards and Generic Methods in Java
- Finishing the Project: Java Web Development ...

Watch our Tech Videos 
Dev Articles Forums 
 RSS  Articles
 RSS  Forums
 RSS  All Feeds
Write For Us 
Weekly Newsletter
 
Developer Updates  
Free Website Content 
Contact Us 
Site Map 
Privacy Policy 
Support 

Developer Shed Affiliates

 




© 2003-2017 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials