-- A* -- (A asterisco o A estrella)

Integrantes del equipo:

Norma Angélica Villatoro Pérez
Deydre Itzel Molina Espinosa
Alexander Vázquez Sarmiento
Everardo Martínez Vázquez
José de Jesús Sánchez de la Cruz
Josué Caleb Molina Zepeda

**************************************************************************************

Búsqueda por el método algorítmico A*

El algoritmo de búsqueda A*(pronunciado “A asterisco” o “A estrella”) se clasifica dentro de los algoritmos de búsqueda en  grafos. Presentado por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael, el algoritmo A* encuentra, siempre y cuando se cumplan unas determinadas condiciones, el camino de menor coste entre un nodo origen y uno objetivo.

Él método 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.

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.

Método.

La búsqueda del algoritmo  A* busca mejorar la ramificación y acotación utilizando la programación dinámica. La heurística busca el aumento  en la eficiencia en la búsqueda.

Para que el algoritmo A * pueda  encontrar la ruta más óptima y admisible debe usarse la heurística

Demostración

Animación onda de choque (k) - ver una búsqueda A *

Algoritmo

1.- formar una cola de Q  caminos parciales. Dejar  que la inicial Q consiste en la de costo-cero,  a cero-paso por camino desde la raíz a ninguna parte.

2.-Hasta que Q está vacío o el objetivo se ha llegado a determinar si el primer camino

  En Q llega a la meta.

     a. Si lo hace, no hacer nada

     b. si no:

              2b1. Retire el primer camino de Q

           2b2. Formulario de nuevos caminos mediante la ampliación de un paso.

           2b3. Añadir los nuevos caminos a la Q

           2b4.If dos o más caminos llegan (o contener) un nodo común,

                  Eliminar todos menos el camino que llega al nodo común con

                  el más bajo costo. (Programación dinámica)

           2B5. clase Q por la suma del costo real de la medida heurística (la

          Estimación de límite inferior de los costes restantes.)

3.- Si el objetivo es alcanzado, se llega al el éxito, si no se obtiene  el fracaso.

Aplicación de 2B4  REQUIERE  una lista separada de los nodos que han sido

Ampliado y los costos más bajos asociados con llegar a ellos.

Evaluación.

La búsqueda es completada. Si todos los nodos  son abiertos y si el resultado es encontrado, si esto sucede es finalizado.

Costo de la búsqueda

La eficiencia de este tipo de búsqueda es muy difícil de precisar. Por lo tanto no puede ser representado con una expresión matemática

Óptima

Este algoritmo encontrará definitivamente la ruta más eficiente a través del espacio del Estado.

Siguiente: redondear al alza

Atrás: Marca y atado con subestima

IMPLEMENTACION PSEUDOCODIGO

Tratar punto

.:= . // coste del camino hasta . caso . = . perteneciente a () si g(.) < g(.) entonces // (-----) // nos quedamos con el camino de menor coste .:= MEJORNODO actualizar g(.) y f'(.) propagar g a . de . eliminar . añadir . a ._MEJORNODO caso . = . perteneciente a )-----( si g(.) < g(.) entonces // nos quedamos con el camino de menor coste .:= MEJORNODO actualizar g(.) y f'(.) eliminar . añadir . a ._MEJORNODO caso . no estaba en ).( ni (.) añadir . a ).( añadir . a ._MEJORNODO f'(.) := g(.) + h'(.)

Implementación en pseudocódigo

ABIERTOS := [INICIAL] //inicialización CERRADOS := [] f'(INICIAL) := h'(INICIAL) repetir si ABIERTOS = [] entonces FALLO si no // quedan nodos extraer MEJORNODO de ABIERTOS con f' mí­nima // cola de prioridad mover MEJORNODO de ABIERTOS a CERRADOS si MEJORNODO contiene estado_objetivo entonces SOLUCION_ENCONTRADA := TRUE si no generar SUCESORES de MEJORNODO para cada SUCESOR hacer TRATAR_SUCESOR hasta SOLUCION_ENCONTRADA o FALLO

Tratar_Sucesor

SUCESOR.ANTERIOR := VIEJO // coste del camino hasta SUCESOR caso SUCESOR = VIEJO perteneciente a CERRADOS si g(SUCESOR) < g(VIEJO) entonces // (no si monotoní­a) // nos quedamos con el camino de menor coste VIEJO.ANTERIOR := MEJORNODO actualizar g(VIEJO) y f'(VIEJO) propagar g a sucesores de VIEJO eliminar SUCESOR añadir VIEJO a SUCESORES_MEJORNODO caso SUCESOR = VIEJO perteneciente a ABIERTOS si g(SUCESOR) < g(VIEJO) entonces // nos quedamos con el camino de menor coste VIEJO.ANTERIOR := MEJORNODO actualizar g(VIEJO) y f'(VIEJO) eliminar SUCESOR añadir VIEJO a SUCESORES_MEJORNODO caso SUCESOR no estaba en ABIERTOS ni CERRADOS añadir SUCESOR a ABIERTOS añadir SUCESOR a SUCESORES_MEJORNODO f'(SUCESOR) := g(SUCESOR) + h'(SUCESOR)

 **************************************************************************************