Chapter 2. Exploring Search Algorithms

In this chapter, we'll look at how to perform a search, and we will cover the basic requirements of implementing a search algorithm. We'll then practice by implementing Dijkstra's algorithm, before moving on to heuristics, showing how they can be used in search algorithms to improve the accuracy of search results.

In particular, we'll be focusing on the following topics:

• An introduction to searching
• Implementing Dijkstra's search
• Understanding the notion of heuristics
• A brief introduction to the A* algorithm
• Implementing an A* algorithm

An introduction to searching

Let's look at what it means to search. If we want to apply a search to any problem, we will need four pieces of input, which are referred to as the state space, and are as follows:

[S, s, O, G]

The preceding types of input can be described as follows:

• S: A set of implicitly given states—all of the states that might be explored in a search process.
• s: The start symbol—the starting point of the search.
• O: The state transition operators, which indicate how a search should proceed from one node to the next and what transitions are available to the search. This is an exhaustive list. Therefore, the state transition operator keeps track of these exhaustive lists.
• G: The goal node, pointing to where the search should end.

 

With the preceding information, we can find the following values:

• The minimum cost transaction for a goal state
• A sequence of transitions to a minimum cost goal
• A minimum cost transaction for a minimum cost goal

Let's consider the following algorithm, which...

Implementing Dijkstra's search

Now, we will look at the code for Dijkstra's search algorithm, which we discussed in the An introduction to searching section.

 

Let's get straight to the code, and look at how it works. In the previous section, the very first thing that we showed were the vertices; each vertex had certain properties. We will now create a Vertex class, as follows:

public class Vertex {
    final private String id;
    final private String name;


    public Vertex(String id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((id == null) ? 0 : id.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Vertex other ...

Understanding the notion of heuristics

Let's look at heuristics; later on, we'll look at an example.

Heuristics are an approach to problem solving, learning, and discovery. We apply heuristics when we are not sure of what the goal should be; we can apply certain estimates, and these estimates can help us to optimize our search process. If finding an optimal solution is impossible or impractical, heuristic methods can be used to speed up the process of finding a satisfactory solution.

So, let's look at an example of using heuristics.

Suppose that we have a puzzle with eight tiles, arranged as shown in the Initial State cube, and we want to arrange them as they are in the Goal State cube:

To take 1 from its Initial State to its Goal State, we have to move 1 from the first tile to the last tile in the first row.

We also have to move at least two edges (that is, 2 and 3), so that we can get 1 to its Goal State location.

There can be two values: an overestimate and an underestimate. The overestimate...

A brief introduction to the A* algorithm

We'll now look at how an A* algorithm works. In this algorithm, we'll calculate two costs. We'll be taking four pieces of input: our start state (a set of implicitly given states), a state transition operator, a goal state, and the heuristic value of each node. Based on those, we'll be calculating our actual cost, g(n) (which we also calculated in our Dijkstra's algorithm). Along with the actual cost, we'll calculate one more cost: the final cost (f(n)). The final cost will be the actual cost plus the heuristic cost (h(n)). The formula is as follows:

 

In the preceding formula, the following applies:

• g(n) is the actual cost of traversing from the initial state to state n
• h(n) is the estimated cost of reaching the goal from state n

We are given the following information:

[S,s,O,G,h]

In the preceding statement, the following applies:

• S is an implicitly given set of states
• s is the start state
• O is the state transition operator
• G is the goal
• h is the heuristic function...

Implementing an A* algorithm

We will now look at how to implement an A* algorithm. Let's start with the code. We will use the same code that we used in the Dijkstra's search algorithm. The Vertex.java file is as follows:

public class Vertex {
    final private String id;
    final private String name;


    public Vertex(String id, String name) {
        this.id = id;
        this.name = name;
    }
// public String getId() {
// return id;
// }
//
// public String getName() {
// return name;
// }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((id == null) ? 0 : id.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Vertex other = (Vertex) obj;
        if (id == null) {
            if (other...

Summary

In this chapter, you learned about heuristics, and you also learned how uniform cost and A* algorithms work.

In the next chapter, you'll learn how game playing works (in other words, how AI games work). We'll cover the rule-based system and how it works in Java.