Contents
ToggleStar Algorithm
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
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:

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.