Home arrow Java arrow Page 8 - 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 - Finding the “Optimal” Solution
(Page 8 of 9 )

All of the previous search techniques were concerned, first and foremost, with finding a solution—any solution. As you saw with the heuristic searches, efforts can be made to improve the likelihood of finding a good solution; but no attempt was made to ensure that an optimal solution was found. However, at times you may want only the optimal solution. Keep in mind that “optimal,” as it is used here, simply means the best route that can be found by using one of the multiple-solution generation techniques—it may not actually be the best solution. (Finding the best solution would, of course, require the prohibitively time-consuming exhaustive search.)

Before leaving the well-used flight scheduling example, consider a program that finds the optimal route given the constraint that distance is to be minimized. To do this, the program employs the path-removal method of generating multiple solutions and uses a least-cost search to minimize distance. The key to finding the shortest path is to keep a solution that is shorter than the previously generated solution. When there are no more solutions to generate, the optimal solution remains.

The entire “optimal solution” program is shown here. Notice that the program creates an additional stack, called optimal, which holds the optimal solution, and an instance variable, called minDist, which keeps track of the distance. There are also changes to route( ) and some minor modifications to main( ).

// Find "optimal" solution using least-cost.
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 Optimal {
  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
 
Stack optimal; // holds optimal solution
 
int minDist = 10000;
 
public static void main(String args[])
 
{
    String to, from;
    Optimal ob = new Optimal();
    BufferedReader br = new
     
BufferedReader(new InputStreamReader(System.in)); 
    boolean done = false;
    FlightInfo f;
   
ob.setup();
   
try {
     
System.out.print("From? ");
      from = br.readLine();
      System.out.print("To? ");
      to = br.readLine();
      do {
       
ob.isflight(from, to);
       
if(ob.btStack.size() == 0) done = true;
       
else {
          ob.route(to);
          ob.btStack = new Stack();
       
}
      } while(!done);
      // Display optimal solution.
      if(ob.optimal != null) {
        System.out.println("Optimal solution is: ");
       
int num = ob.optimal.size();
       
for(int i=0; i < num; i++) {
          f = (FlightInfo) ob.optimal.pop(); 
          System.out.print(f.from + " to ");
       
}
        System.out.println(to);
        System.out.println("Distance is " + ob.minDist);
      }
    } 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");
  }
 
// Save shortest route.
  void route(String to)
  {
   
int dist = 0;
    FlightInfo f;
    int num = btStack.size();
    Stack optTemp = new Stack();
   
for(int i=0; i < num; i++) {
      f = (FlightInfo) btStack.pop();
      optTemp.push(f); // save route
      dist += f.distance;
   
}
    // If shorter, keep this route
   
if(minDist > dist) {
      optimal = optTemp;
      minDist = 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 using least-cost. 
  FlightInfo find(String from)
  {
   
int pos = -1;
    int dist = 10000; // longer than longest route
   
for(int i=0; i < numFlights; i++) {
      if(flights[i].from.equals(from) &&
        !flights[i].skip)
     
{
        // Use the shortest 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);
   
}
  }
}

The output from the program is shown here:

From? New York
To? Los Angeles
Optimal solution is:
New York to Chicago to Denver to Los Angeles
Distance is 2900

In this case, the “optimal” solution is not quite the best one, but it is still a very good one. As explained, when using AI-based searches, the best solution to be found by one search technique will not always be the best solution that exists. You might want to try substituting another search technique in the preceding program, observing what type of “optimal” solution it finds.

The one inefficiency in the preceding method is that all paths are followed to their conclusion. An improved method would stop following a path as soon as the length equaled or exceeded the current minimum. You might want to modify this program to accommodate such an enhancement.


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