Home arrow Java arrow Page 2 - 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 - Search Techniques
(Page 2 of 9 )

There are several ways to search for a solution. The four most fundamental are

  • Depth first
  • Breadth first
  • Hill climbing
  • Least cost

In the course of this chapter, each of these searches is examined.

Evaluating a Search

Evaluating the performance of an AI-based search technique can be complicated. Fortunately, for our purposes we are concerned only with these two measurements:

  • How quickly a solution is found
  • How good the solution is

There are several types of problems for which all that matters is that a solution, any solution, be found with the minimum effort. For these problems, the first measurement is especially important. In other situations, the quality of the solution is more important.

The speed of a search is affected both by the size of the search space and by the number of nodes actually traversed in the process of finding the solution. Because backtracking from dead ends is wasted effort, you want a search that seldom retraces its steps.

In AI-based searching, there is a difference between finding the best solution and finding a good solution. Finding the best solution can require an exhaustive search because sometimes this is the only way to know that the best solution has been found. Finding a good solution, in contrast, means finding a solution that is within a set of constraints—it does not matter if a better solution might exist.

As you will see, the search techniques described in this chapter all work better in certain situations than in others, so it is difficult to say whether one search method is always superior to another. But some search techniques have a greater probability of being better for the average case. In addition, the way a problem is defined can sometimes help you choose an appropriate search method.


The Problem

Now let us consider the problem that we will use various searches to solve. Imagine that you are a travel agent and a rather quarrelsome customer wants you to book a flight from New York to Los Angeles with XYZ Airlines. You try to tell the customer that XYZ does not have a direct flight from New York to Los Angeles, but the customer insists that XYZ is the only airline that he will fly. Thus, you must find connecting flights between New York and Los Angeles. You consult XYZ’s scheduled flights, shown here:

New York to Chicago

900 miles

Chicago to Denver

1000 miles

New York to Toronto

500 miles

New York to Denver

1800 miles

Toronto to Calgary

1700 miles

Toronto to Los Angeles

2500 miles

Toronto to Chicago

500 miles

Denver to Urbana

1000 miles

Denver to Houston

1000 miles

Houston to Los Angeles

1500 miles

Quickly you see that there are connections that enable your customer to fly from New York to Los Angeles. The problem is to write a Java program that does the same thing that you just did in your head!

A Graphic Representation

The flight information in XYZ’s schedule can be translated into the directed graph shown in Figure 10-3. A directed graph is simply a graph in which the lines connecting each node

 
Figure 1-3.  A directed graph of XYZ's flight schedule

include an arrow to indicate the direction of motion. In a directed graph, you cannot travel against the direction of the arrow.

To make things easier to understand, we can redraw this graph in a treelike fashion, as shown in Figure 10-4. Refer to this version for the rest of this chapter. The goal, Los Angeles, is circled. Notice also that various cities appear more than once to simplify the construction of the graph. Thus, the treelike representation does not depict a binary tree. It is simply a visual convenience.

Now we are ready to develop the various search programs that will find paths from New York to Los Angeles.

 
              Figure 10-4.  A tree version of XYZ's flight schedule


The FlightInfo Class

Writing a program to find a route from New York to Los Angeles requires a database that contains the information about XYZ’s flights. Each entry in the database must contain the departure and destination cities, the distance between them, and a flag that aids in backtracking. This information is held in a class called FlightInfo, shown here:

  // 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;
    }
  }

This class will be used by all the search techniques described in the remainder of the chapter.


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