Algorithm A * is surely most widespread to solve the problems of search for an optimal path. The general principle of an algorithm of type A is based on a heuristic approach of the problem. A cost function integrates two concepts:

• the cost of the path already covered and
• the heuristic cost of the remaining path to cover.

The guarantee of the convergence and the optimality of the solution are of course related to the quality of the heuristics.

The principle of optimality is based on the fact that if a path is optimal, then any under-path of this path is optimal too. That means that for any node it is enough to preserve the best path in term of cost. The algorithm is described as A * if the heuristic estimate of the cost of the remaining path to cover is optimistic, i.e. always lower than or equal to its real value.

The principle is based on an treelike search in the space of the possible states. An ordered list of the states contains the nodes to be studied accompanied with their cost.

The classification follows the ascending order of the costs, most promising first.

• At each stage of the process, if possible, the most promising node is developed, i.e. replaced by all its successors, then the cost is calculated for each new node.
• This new list is arranged in ascending cost order and finally inserted in the ordered list.
• If the goal is reached and the solution satisfactory, the process stops, because the optimal solution is found.
• If not, the most promising among the under-goals, kept in reserve in the list, is explored.

The cost function is of additive type. For a node n' successor of the node n, it has the following form:

A second list memorizes the nodes which describe the current path. At the end of the process it contains the optimal path between the initial point and the final point.