Home arrow Java arrow Page 7 - 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 - Node Removal
(Page 7 of 9 )

The second way to force the generation of additional solutions, node removal, simply removes the last node in the current solution path and tries again. To do this, main( ) is changed so that it removes the last connection from the flight database, clears all the skip fields, and obtains a new, empty stack that is used to hold the next solution. The last connection of the previous solution is removed from the flight database by using a new method called remove( ). All the skip fields are reset by using another new method called resetAllSkip( ). The updated main( ) method, along with resetAllSkip( ) and remove( ), are shown here:

public static void main(String args[])
{
  String to, from;
  NodeR ob = new NodeR();
  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 {
        // Save the flight on top-of-stack.
        f = (FlightInfo) ob.btStack.peek();
        ob.route(to); // display current route
       
ob.resetAllSkip(); // reset all skip fields
       
/* Remove last flight in previous route
           from the flight database. */
        ob.remove(f);
       
// Reset the backtrack stack.
        ob.btStack = new Stack();
      }
    }while(!done);
  } catch (IOException exc) {
    System.out.println("Error on input.");
  }
}
// Reset all skip fields.
void resetAllSkip() {
  for(int i=0; i< numFlights; i++)
    flights[i].skip = false;
}
// Remove a connection.
void remove(FlightInfo f) {
  for(int i=0; i< numFlights; i++)
    if(flights[i].from.equals(f.from) &&
      flights[i].to.equals(f.to))
        flights[i].from = "";
}

As you can see, removing a connection is accomplished by assigning a zero-length string to the name of the departure city. Because so many changes are required, the entire node-removal program is shown here for the sake of clarity:

// Find multiple connections using node removal.
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 NodeR {
    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;
      NodeR ob = new NodeR();
      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 {
          // Save the flight on top-of-stack.
          f = (FlightInfo) ob.btStack.peek();
         
ob.route(to); // display current route
         
ob.resetAllSkip(); // reset all skip fields
         
/* Remove last flight in previous route
             from the flight database. */
          ob.remove(f);
         
// Reset the backtrack stack.
          ob.btStack = new Stack();
        }
      } while(!done);
    } 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;
      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);
 
}
}
// Reset all skip fields.
void resetAllSkip() {
  for(int i=0; i< numFlights; i++)
    flights[i].skip = false;
}
  // Remove a connection.
  void remove(FlightInfo f) {
    for(int i=0; i< numFlights; i++)
      if(flights[i].from.equals(f.from) &&
        flights[i].to.equals(f.to))
          flights[i].from = "";
  }
}

This program finds the following routes:

From? New York
To? Los Angeles
New York to Chicago to Denver to Los Angeles
Distance is 2900
New York to Chicago to Denver to Houston to Los Angeles Distance is 4400
New York to Toronto to Los Angeles
Distance is 3000

In this case, the second solution is the worst possible route, but two fairly good solutions are also found. Notice that the set of solutions found by the node-removal method differs from that found by the path-removal approach. Different approaches to generating multiple solutions can often yield different results.


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