Contenus

Toggle## Star 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

**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**.

**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;Yesx belongs to T thenFinished: Solution foundOtherwiseFor everythingy successor of x doYesy does not belong to F U O or g (y)> g (x) + k (x, y) then g (y) End IfEnd ForEnd ifEnd 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.