AI-Based Problem Solving - An Analysis of Hill Climbing
(Page 6 of 9 )
Actually, hill climbing provides fairly good solutions in many circumstances because it tends to reduce the number of nodes that need to be visited before a solution is found. However, it can suffer from three maladies. First, there is the problem of false peaks, as just described. In this case, extensive backtracking may result. The second problem relates to plateaus, a situation in which all next steps look equally good (or bad). In this case, hill climbing is no better than depth-first searching. The final problem is that of a ridge. In this case, hill climbing really performs poorly because the algorithm causes the ridge to be crossed several times as
Figure 10-7. The hill-climbing path to a solution and to a false peak
backtracking occurs. In spite of these potential troubles, hill climbing often increases the probability of finding a good solution.
The Least-Cost Search The opposite of a hill-climbing search is a least-cost search. This strategy is similar to standing in the middle of a street on a big hill while wearing roller skates. You have the definite feeling that it’s a lot easier to go down rather than up! In other words, a least-cost search takes the path of least resistance.
Applying a least-cost search to the flight-scheduling problem implies that the shortest connecting flight is taken in all cases so that the route found has a good chance of covering the shortest distance. Unlike hill climbing, which attempts to minimize the number of connections, a least-cost search attempts to minimize the number of miles.
To use a least-cost search, you must again alter find( ), as shown here:
// Given from, find closest connection.
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;
}
Using this version of find( ), the solution is
From? New York
To? Los Angeles
New York to Toronto to Los Angeles
Distance is 3000
As you can see, the search found a good route—not the best, but acceptable. Figure 10-8 shows the least-cost path to the goal.
An Analysis of the Least-Cost Search Least-cost searches and hill climbing have the same advantages and disadvantages, but in reverse. There can be false valleys, lowlands, and gorges. In this specific case, the least-cost search worked about as well as the hill-climbing search.
Figure 10-8. The least-cost to a solution
Finding Multiple Solutions Sometimes it is valuable to find several solutions to the same problem. This is not the same as finding all solutions (an exhaustive search). Instead, multiple solutions offer a representative sample of the solutions present in the search space.
There are several ways to generate multiple solutions, but only two are examined here. The first is path removal, and the second is node removal. As their names imply, generating multiple solutions without redundancy requires that solutions already found be removed from the system. Remember that neither of these techniques attempts to find all solutions. Finding all solutions is a different problem that usually is not attempted because it implies an exhaustive search.
Path Removal The path-removal method of generating multiple solutions removes all nodes from the database that form the current solution and then attempts to find another solution. In essence, path removal prunes limbs from the tree. To find multiple solutions by using path removal, you just need to alter main( ) in the depth-first search, as shown here, and change the name of the search class to PathR:
public static void main(String args[])
{
String to, from;
PathR ob = new PathR();
BufferedReader br = new
BufferedReader(new InputStreamReader(System.in));
boolean done = false;
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);
} catch (IOException exc) {
System.out.println("Error on input.");
}
}
Here, a do loop is added that iterates until the backtrack stack is empty. Recall that when the backtrack stack is empty, no solution (in this case, no additional solution) has been found. No other modifications are needed because any connection that is part of a solution will have its skip field marked. Consequently, such a connection can no longer be found by find( ) and cannot be part of the next solution, nor can it be refound. Of course, a new backtrack stack must be obtained to hold the next solution.
The path-removal method finds the following solutions:
From? New York
To? Los Angeles
New York to Chicago to Denver to Los Angeles
Distance is 2900
New York to Toronto to Los Angeles
Distance is 3000
New York to Denver to Houston to Los Angeles
Distance is 4300
The search found the three solutions. Notice, however, that none are the best solution.
Next: Node Removal >>
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 
