Algoritmo de estrella
La idea del algoritmo A star o A star o A* es evitar desarrollar caminos estimados demasiado caros en comparación con los conocidos. Para ello el algoritmo se referirá a una función de evaluación de su coste total. El principio es similar a branch&bound o branch&price.
Función de evaluación
Algoritmo de estrella
Nota s el estado inicial, T el conjunto de estados terminales, k(x,y) el costo de X Para y, F el conjunto de estados expandidos – cuyos sucesores han sido generados (conjunto cerrado) – y O el conjunto de estados generados pero no desarrollados. El algoritmo de una estrella es el siguiente:
O Siempre que O <> Ø extraiga de O el elemento x tq f (x) es mínimo; Inserte x en F;
sí x pertenece a T entonces Terminado: Solución encontrada
De lo contrario
Por todo y sucesor de x do
sí y no pertenece a F U O o g (y)> g (x) + k (x, y) entonces g (y) End If
Fin para
Terminara si
Finalizar mientras / CODIGO +
Ejemplo
Para ilustrar el algoritmo de la estrella A, tomaremos como ejemplo el problema de los 8 rompecabezas. Este problema es una matriz de 3*3 que contiene 8 casillas llenas con los números del 1 al 8 y una casilla vacía. Cada cuadrado puede moverse a un cuadrado adyacente en la matriz, y solo a un cuadrado vacío. En este caso, permitimos el valor de la casilla con la casilla vacía. El objetivo del rompecabezas de 8 es ordenar las casillas en orden ascendente de izquierda a derecha y de arriba a abajo de la matriz. Concretamente, es un teaser.
La heurística utilizada para este ejemplo es Distancia de Manhattan. Esta distancia es la suma de los movimientos “a vuelo de pájaro” que hay que hacer para que cada casilla quede en el lugar correcto. Efectivamente es una heurística admisible y consistente porque consideramos que todos los movimientos de las casillas son legales. La función g(n) tendrá el valor no, el número de movimientos realizados para llegar a la configuración no.
Tomemos una configuración inicial aleatoria, tenemos para la primera iteración el siguiente árbol:
El algoritmo tiene en el conjunto F la raíz, y en el conjunto O las 4 configuraciones generadas. La configuración de la derecha tiene la estimación más pequeña del costo total, por lo que se quita de O para ser explorada y finalmente se coloca en F. Obtenemos el siguiente árbol:
Hemos encontrado una solución final tal que su costo es mínimo, el algoritmo de una estrella se detiene.
