Star Algorithm

Contenus

The idea of the A star or A star or A * algorithm is to avoid developing paths considered too expensive compared to known ones. For this, the algorithm will refer to a function for evaluating 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 towards a final state. Heuristics never overestimate true distance. And it is consistent, i.e. 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 developed states - whose successors have been generated (set of closed) - and O the set of states generated but not developed. 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 the Manhattan Distance. This distance is the sum of the movements "as the crow flies" to perform 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 boxes are legal. The function g (n) will have the value not, the number of movements made to reach the configuration not.

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

shortest path algorithm A star algorithm A*

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 be placed in F. We get the following tree:

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