Star Algorithm

Contents

The idea of the A star or A star or A* algorithm is to avoid developing paths estimated to be too expensive compared to known ones. For this the algorithm will refer to a function of evaluation of its total cost. The principle is similar to branch&bound or branch&price.

Evaluation function

Let f(n) be an evaluation function for a vertex not, h(n) a heuristic estimated cost to go to a final state, and g(n) the actual cost to reach the top not. Then f (n) = h (n) + g (n). The function f (n) can be described as the total estimated cost to go to a final state through not.

The heuristic must be admissible, i.e. h(n)≤h'(n) where h'(n) is the true cost to go from not to a final state. The heuristic never overestimates the true distance. And it is consistent, that is to say that for all y descending from x, h(x)≤h(y)+cost(x to y).

Star Algorithm

Note s the initial state, T the set of terminal states, k(x,y) the cost of x To y, F the set of expanded states – whose successors have been generated (closed set) – and O the set of generated but not developed states. The A star algorithm is as follows:

O As long as O <> Ø do Extract from O the element x tq f (x) is minimal; Insert x into F;
    Yes x belongs to T then Finished: Solution found
    Otherwise
      For everything y successor of x do
        Yes y does not belong to F U O or g (y)> g (x) + k (x, y) then g (y) End If
      End For
    End if
  End While / CODE +

Example

To illustrate the A star algorithm, we will take the 8-puzzle problem as an example. This problem is a 3 * 3 matrix containing 8 boxes filled with the numbers 1 to 8 and one empty box. Each square can move to an adjacent square in the matrix, and only to an empty square. In this case, we allow the value of the box with the empty box. The objective of the 8-puzzle is to sort the boxes in ascending order from left to right and top to bottom of the matrix. Concretely, it is a tease.

The heuristic used for this example is Manhattan Distance. This distance is the sum of the “as the crow flies” movements to be made so that each square is in the right place. It is indeed an admissible and consistent heuristic because we consider that all the movements of the squares are legal. The function g(n) will have the value not, the number of movements made to reach the configuration not.

Let's take a random starting configuration, we have for first iteration the following tree:

The algorithm has in the set F the root, and in the set O the 4 generated configurations. The configuration on the right has the smallest estimate of the total cost, so it is removed from O to be explored and finally placed in F. We obtain the following tree:

We have found a final solution such that its cost is minimal, the A star algorithm stops.