Home arrow Java arrow Page 5 - 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 Hill-Climbing Search
(Page 5 of 9 )

A search algorithm that attempts to find a route that minimizes the number of connections uses the heuristic that the longer the length of the flight, the greater the likelihood that it takes the traveler closer to the destination; therefore, the number of connections is minimized. In the language of AI, this is an example of hill climbing.

The hill-climbing algorithm chooses as its next step the node that appears to place it closest to the goal (that is, farthest away from the current position). It derives its name from the analogy of a hiker being lost in the dark, halfway up a mountain. Assuming that the hiker’s camp is at the top of the mountain, even in the dark the hiker knows that each step that goes up is a step in the right direction.

Working only with the information contained in the flight-scheduling database, here is how to incorporate the hill-climbing heuristic into the routing program: Choose the connecting flight that is as far away as possible from the current position in the hope that it will be closer to the destination. To do this, modify the find( ) routine, as shown here:

// Given from, find the farthest away connection. FlightInfo find(String from)
{
 
int pos = -1;
 
int dist = 0;
 
for(int i=0; i < numFlights; i++) {
    if(flights[i].from.equals(from) &&
      !flights[i].skip)
    {
      // Use the longest flight.
     
if(flights[i].distance > dist) {
        pos = i;
        dist = flights[i].distance;
      
}
    }
  }
  if(pos != -1) {
    flights[pos].skip = true; // prevent reuse
    FlightInfo f = new FlightInfo(flights[pos].from,
                        
flights[pos].to,
                         flights[pos].distance);
    return f;
  }
  return null;
}

The find( ) routine now searches the entire database, looking for the connection that is farthest away from the departure city.

The entire hill-climbing program follows:

// Find connections using hill climbing.
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 Hill {
  final int MAX = 100;
 
// 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;
    Hill ob = new Hill();
    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 FlightInf
o(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 the farthest away connection.   
    FlightInfo find(String from)
    {
      
int pos = -1;
      int dist = 0;
      
for(int i=0; i < numFlights; i++) {
        if(flights[i].from.equals(from) &&
          !flights[i].skip)
       
{
          // Use the longest flight.
          if(flights[i].distance > dist) {
            
pos = i;
            dist = flights[i].distance;
          }
        }
      }
     
if(pos != -1) {
        flights[pos].skip = true; // prevent reuse
       
FlightInfo f = new FlightInfo(flights[pos].from,
                            
flights[pos].to,
                             flights[pos].distance);
        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);
    }
  }
}

When the program is run, the solution is

From? New York
To? Los Angeles
New York to Denver to Los Angeles
Distance is 2800

This is quite good! The route contains the minimal number of stops on the way (only one), and it is the shortest route. Thus, it found the best possible route.

However, if the Denver to Los Angeles connection did not exist, the solution would not be quite so good. It would be New York to Denver to Houston to Los Angeles—a distance of 4300 miles! In this case, the solution would climb a “false peak,” because the connection to Houston would not take us closer to the goal of Los Angeles. Figure 10-7 shows the first solution as well as the path to the false peak.


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