Home arrow Java arrow Page 6 - 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 / 29
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 - 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.


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-2014 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials