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.
Next: Back to the Lost Keys >>
More Java Articles
More By McGraw-Hill/Osborne
|
 This article is excerpted from chapter 10 of The Art of Java, written by Herbert Schildt (McGraw-Hill/Osborne, 2004; ISBN: 0072229713). Check it out at your favorite bookstore. Buy this book now.
|
|
/ 9 
