Algoritmo A*

algoritmo la* - Wikilingue - Encydia

Algoritmo A* (Se lee: La-estrella) es un algoritmo para Búsqueda de Camino. Él busca el camino en un grafo de un vértice inicial hasta un vértice final. Él es la combinación de aproximaciones heurísticas como del algoritmo Best-first Search y de la formalidade del Algoritmo de Dijkstra.

El algoritmo fue descrito por primera vez en 1968 por Peter Hart, Nils Nilsson, y Bertram Raphael. En la publicación de ellos, él fue llamado de algoritmo A; usando este algoritmo con una heurística pertinente se alcanza un comportamiento óptimo, y pasó a ser conocido por A*.

Su aplicación va desde aplicativos para encontrar rutas de desplazamiento entre localidades la resolución de problemas, como la resolución de uno quiebra-cabezas. Él es muy usado en juegos.

Algoritmo

Inicialice Q con el nodo de búsqueda (S) cómo única entrada;
Si Q está vacía, interrumpa. Si no, escoja el mejor elemento de Q ;
Si el estado (n) es un objetivo, retorne n;
(De otro modo) Remueva n de Q ;
Encuentre los descendientes del estado (n) que no están en visitados y cree todas las extensiones de n para cada descendiente;
Añada los caminos extendidos a Q y vaya al paso 2;

Función heuristica f = h+g;
h(n) es una estimativa de la distancia de un estado hasta el objetivo;
g es la largura;
Ya la estimativa de la largura total es suministrada por f ;
Q es una lista de los caminos expandidos;

Una estimativa que siempre subestima la largura real del camino atiene el objetivo es llamada de admisible. El uso de una estimativa admisible garantiza que la búsqueda de coste-uniforme aún encontrará el más pequeño camino.