A star algorithm

The idea of the algorithm A* or A star, is to avoid developing paths estimated too expensive compared to those known. For that 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 n, h(n) be an estimated cost heuristic to go to a final state, and g(n) be the real cost to reach the vertex n. Then f(n)=h(n)+g(n). The function f(n) can be described as the estimated total cost to go to a final state through n.
The heuristic must be admissible, i.e. h(n)≤h'(n) where h'(n) is the true cost to go from n to a final state. The heuristic never overestimates the true distance. And it is consistent, that is to say that for all y a successor of x, h(x)≤h(y)+cost(x to y).

Algorithm

Let s be the initial state, T the set of terminal states, k(x, y) the cost from x to y, F the set of developed states – whose successors have been generated (set of closed) – and O all the states generated but not developed. The algorithm of A* is as follows:

1.  Initialize the open list
2.  Initialize the closed list
    put the starting node on the open 
    list (you can leave its f at zero)

3.  while the open list is not empty
    a) find the node with the least f on 
       the open list, call it "q"

    b) pop q off the open list
  
    c) generate q's 8 successors and set their 
       parents to q
   
    d) for each successor
        i) if successor is the goal, stop search
          successor.g = q.g + distance between 
                              successor and q
          successor.h = distance from goal to 
          successor (This can be done using many 
          ways, we will discuss three heuristics- 
          Manhattan, Diagonal and Euclidean 
          Heuristics)
          
          successor.f = successor.g + successor.h

        ii) if a node with the same position as 
            successor is in the OPEN list which has a 
           lower f than successor, skip this successor

        iii) if a node with the same position as 
            successor  is in the CLOSED list which has
            a lower f than successor, skip this successor
            otherwise, add  the node to the open list
     end (for loop)
  
    e) push q on the closed list
    end (while loop)

Example

We will take as an example the problem of the 8-puzzle. This problem is a 3*3 matrix containing 8 boxes filled with numbers from 1 to 8 and an empty box. Each box can move on an adjacent box in the matrix, and only on an empty box. 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 from top to bottom of the matrix.

The heuristic used for this example is the Manhattan Distance. This distance is the sum of the movements « as the crow flies » to make each box 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 for value n the number of displacements carried out to reach the configuration n.

Let’s take a random configuration of departure, we have for first iteration the following tree:

astarbegin

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 get the following tree:

astar

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

 

Publicités