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 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 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.
Next: An Analysis of Hill Climbing >>
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 
