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).
To conclude this book, we will examine a topic from an interesting discipline of programming: artificial intelligence (AI). As explained earlier, the goal of this book is to show the richness and power of the Java language. Perhaps nothing demonstrates that better than its application to the demanding realm of artificial intelligence. Java’s powerful string-handling capabilities and Stack class streamline many types of AI-based code. Java’s object model keeps the code clean, as does its garbage collection facility. As this final chapter shows, Java is a language well suited to the AI developer.
The field of artificial intelligence is comprised of several fascinating areas, but fundamental to many AI-based applications is problem solving. Essentially, there are two types of problems. The first type can be solved through the use of some sort of deterministic procedure that is guaranteed success, such as the computation of the sine of an angle or the square root of a value. These types of problems are easily translated into algorithms that a computer can execute. In the real world, however, few problems lend themselves to such straightforward solutions. Instead, many problems can be solved only by searching for a solution. It is this type of problem solving with which AI is concerned. It is also the type of searching that is explored in this chapter.
To understand why searching is so important to AI, consider the following. One of the early goals of AI research was the creation of a general problem solver. A general problem solver is a program that can produce solutions to all sorts of different problems about which it has no specific, designed-in knowledge. It is an understatement to say that such a program would be highly desirable. Unfortunately, a general problem solver is as difficult to realize as it is tantalizing. One complication is the sheer size and complexity of many real-world situations. Because a general problem solver must search for a solution through what might be a very large, mazelike universe of possibilities, finding ways to search such an environment is a priority. Although we won’t attempt something as ambitious as a general problem solver in this chapter, we will explore several AI-based search techniques that are applicable to a wide variety of problems.
Representation and Terminology
Imagine that you have lost your car keys. You know that they are somewhere in your house, which looks like this:
You are standing at the front door (where theX is). As you begin your search, you check the living room. Then you go down the hall to the first bedroom, through the hall to the second bedroom, back to the hall, and to the master bedroom. Not having found your keys, you backtrack further by going back through the living room. Finally, you find your keys in the kitchen. This situation is easily represented by a graph, as shown in Figure 10-1. Representing search problems in graphical form is helpful because it provides a convenient way to depict the way a solution was found.
With the preceding discussion in mind, consider the following terms, which will be used throughout this chapter:
A discrete point
A node that ends a path
The set of all nodes
The node that is the object of the search
Information about whether any specific node is a better next choice than another
In the example of the lost keys, each room in the house is a node; the entire house is the search space; the goal, as it turns out, is the kitchen; and the solution path is shown in Figure 10-1. The bedrooms, kitchen, and the bath are terminal nodes because they lead nowhere. Heuristics are not represented on a graph. Rather, they are techniques that you might employ to help you better choose a path.
Figure 10-1. The solution path to find the missing keys
Given the preceding example, you may think that searching for a solution is easy—you start at the beginning and work your way to the conclusion. In the extremely simple case of the lost keys, this is not a bad approach because the search space is so small. But for many problems (especially those for which you would want to use a computer) the number of nodes in the search space is very large, and as the search space grows, so does the number of possible paths to the goal. The trouble is that often, adding another node to the search space adds more than one path. That is, the number of potential pathways to the goal can increase in a nonlinear fashion as the size of the search space grows. In a nonlinear situation, the number of possible paths can quickly become very large.
For instance, consider the number of ways three objects—A, B, and C—can be arranged on a table. The six possible permutations are
You can quickly prove to yourself that these six are the only ways that A, B, and C can be arranged. However, you can derive the same number by using a theorem from the branch of mathematics called combinatorics—the study of the way things can be combined. According to the theorem, the number of ways that N objects can be arranged is equal to N!(N factorial). The factorial of a number is the product of all whole numbers equal to or less than itself down to 1. Therefore, 3! is 3 × 2 × 1, or 6. If you had four objects to arrange, there would be 4!, or 24, permutations. With five objects, the number is 120, and with six it is 720. With 1000 objects the number of possible permutations is huge! The graph in Figure 10-2 gives you a visual feel for what is sometimes referred to as a combinatoric explosion. Once there are more than a handful of possibilities, it very quickly becomes difficult to examine (indeed, even to enumerate) all the arrangements.
This same sort of combinatorial explosion can occur in paths through search spaces. Because of this, only the simplest of problems lend themselves to exhaustive searches. An exhaustive search is one that examines all nodes. Thus, it is a “brute-force” technique. Brute force always works but is not often practical for large problems because it consumes too much time, too many computing resources, or both. For this reason, AI-based search techniques were developed.
Figure 10-2. A combinatoric explosion with factorials