Home arrow Java arrow Page 4 - 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 - An Analysis of the Depth-First Search
(Page 4 of 9 )

The depth-first approach found a good solution. Also, relative to this specific problem, depth-first searching found this solution on its first try with no backtracking—this is very good; but had the data been organized differently, finding a solution might have involved considerable backtracking. Thus, the outcome of this example cannot be generalized. Moreover, the performance of depth-first searches can be quite poor when a particularly long branch with no solution at the end is explored. In this case, a depth-first search wastes time not only exploring this chain but also backtracking to the goal.


The Breadth-First Search

The opposite of the depth-first search is the breadth-first search. In this method, each node on the same level is checked before the search proceeds to the next deeper level. This traversal method is shown here with C as the goal:

 

Although thinking in terms of a binary tree–structured search space makes it easy to describe the actions of a breadth-first search, many search spaces, including our flight example, are not binary trees. So precisely what constitutes “breadth” is a bit subjective in that it is defined by the problem at hand. As it relates to our flight example, the breadth-first approach is implemented by checking if any flight leaving the departure city connects to a flight that reaches the destination. In other words, before advancing to another level, the destinations of all connections of connecting flights are checked.

To make the route-seeking program perform a breadth-first search, you need to make an alteration to isflight( ), as shown here:

/* Determine if there is a route between from and to using
   breadth-first search. */
void isflight(String from, String to)
{
  int dist, dist2;
  FlightInfo f;
 
// This stack is needed by the breadth-first search.  
  Stack resetStck = new Stack();
  // See if at destination.
  dist = match(from, to);
  if(dist != 0) {
   
btStack.push(new FlightInfo(from, to, dist));
    return;
  }
 
/* Following is the first part of the breadth-first 
     modification. It checks all connecting flights
     from a specified node. */
 
while((f = find(from)) != null) {
    resetStck.push(f);
    if((dist = match(f.to, to)) != 0) {
     
resetStck.push(f.to);
      btStack.push(new FlightInfo(from, f.to, f.distance)); 
      btStack.push(new FlightInfo(f.to, to, dist));
      return;
   
}
  }
 
/* The following code resets the skip fields set by 
     preceding while loop. This is also part of the 
     breadth-first modification. */
 
int i = resetStck.size();
  for(; i!=0; i--)
    resetSkip((FlightInfo) resetStck.pop());
 
// 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);
  }
}

Two changes have been made. First, the while loop checks all flights leaving from the departure city (from) to see if they connect with flights that arrive at the destination city. Second, if the destination is not found, the skip fields of those connecting flights are cleared by calling resetSkip( ). The connections that need to be reset are stored on their own stack, called resetStck, which is local to isflight( ). Resetting the skip flags is necessary to enable alternative paths that might involve those connections.

The resetSkip( ) method is shown here:

// Reset skip field of specified flight.
void resetSkip(FlightInfo f) {
  for(int i=0; i< numFlights; i++)
    if(flights[i].from.equals(f.from) &&
      flights[i].to.equals(f.to))
        flights[i].skip = false;
}

To try the breadth-first search, substitute the new version of isflight( ) into the preceding search program and then add the resetSkip( ) method. When run, it produces the following solution:

From? New York
To? Los Angeles
New York to Toronto to Los Angeles
Distance is 3000

Figure 10-6 shows the breadth-first path to the solution.

An Analysis of the Breadth-First Search

In this example, the breadth-first search performed fairly well, finding a reasonable solution. As before, this result cannot be generalized because the first path to be found depends on the physical organization of the information. The example does illustrate, however, how depth-first and breadth-first searches often find different paths through the same search space.

Breadth-first searching works well when the goal is not buried too deeply in the search space. It works poorly when the goal is several layers deep. In this case, a breadth-first search expends substantial effort during the backtrack stage.

 
 Figure 10-6.  The breadth-first path to a solution


Adding Heuristics

Neither the depth-first nor the breadth-first search attempts to make any educated guesses about whether one node in the search space is closer to the goal than another. Instead, they simply move from one node to the next using a prescribed pattern until the goal is finally found. This may be the best you can do for some situations, but often a search space contains information that you can use to increase the probability that a search will reach its goal faster. To take advantage of such information, you must add heuristic capabilities to the search.

Heuristics are simply rules that increase the likelihood that a search will proceed in the correct direction. For example, imagine that you are lost in the woods and need a drink of water. The woods are so thick that you cannot see far ahead, and the trees are too big to climb to get a look around. However, you know that rivers, streams, and ponds are most likely in valleys; that animals frequently make paths to their watering places; that when you are near water it is possible to “smell” it; and that you can hear running water. So, you begin by moving downhill because water is unlikely to be uphill. Next, you come across a deer trail that also runs downhill. Knowing that this may lead to water, you follow it. You begin to hear a slight rushing off to your left. Knowing that this may be water, you cautiously move in that direction. As you move, you begin to detect the increased humidity in the air; you can smell the water. Finally, you find a stream and have your drink. In this situation, the heuristic information used to find the water did not guarantee success, but it did increase the probability of an early success. In general, heuristics improve the odds in favor of quickly finding a goal.

Most often, heuristic search methods are based on maximizing or minimizing some constraint. In the problem of scheduling a flight from New York to Los Angeles, there are two possible constraints that a passenger may want to minimize. The first is the number of connections that have to be made. The second is the length of the route. Remember, the shortest route does not necessarily imply the fewest connections, or vice versa. In this section, two heuristic searches are developed. The first minimizes the number of connections. The second minimizes the length of the route. Both heuristic searches are built on the depth-first search framework.


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