Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

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

No description
by

camilo jimenez

on 11 October 2012

Comments (0)

Please log in to add your comment.

Report abuse

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

Búsqueda 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. Búsqueda por el método algorítmico A* É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. Motivación
y
descripción El problema de algunos algoritmos de búsqueda en grafos informados, como puede ser el algoritmo voraz, es que se guían en exclusiva por la función heurística, la cual puede no indicar el camino de coste más bajo, o por el coste real de desplazarse de un nodo a otro (como los algoritmos de escalada), pudiéndose dar el caso de que sea necesario realizar un movimiento de coste mayor para alcanzar la solución. Es por ello bastante intuitivo el hecho de que un buen algoritmo de búsqueda informada debería tener en cuenta ambos factores, el valor heurístico de los nodos y el coste real del recorrido.
Conseguir buenas soluciones (óptimas).
Ganar en eficiencia (reduciendo el árbol de búsqueda). Objetivo de la búsqueda A:
g(n): coste del camino hasta n
h(n): heurística del nodo, estimación del coste de un camino óptimo desde n hasta un estado final
f (n): estimación del coste total de una solución óptima que pasa por n Idea: asignar a cada nodo n un valor f (n) = g(n) + h(n)
Ordenando la cola de ABIERTOS en orden crecienterespecto a f Seleccionar siempre el nodo con menor valor de f Propiedades de A* Solucion Solución encontrada: I-W-K-M-F
Óptima (heurística admisible)
Nodos analizados: 8
Aunque en este caso se analizan más nodos (se ha
explorado parcialmente un camino equivocado), la solución
óptima está asegurada
Nótese que se generan dos nodos distintos con el mismo
estado K (pero distinto camino) Cuando un algoritmo de tipo A utiliza una función heurística h (n) que es una corta inferior de h* (n) . recordemos que h* (n) es el coste real del camino optimo de n a un nodo terminal .Entonces el algoritmo A recibe el nombre de A*. el interés de dicho algoritmo A* se puede resumir en dos propiedades fundamentales:

1.Si existe un camino solución, entonces aplicando el algoritmo A* tendremos garantía de encontrar el camino optimo . esta propiedad se conoce con el nombre de admisibilidad del algoritmo A*. Algoritmo A* 2.Dadas dos funciones heurísticas admisibles H1 (n) <<h* (n) y h2 (n) <h* (n) tales que h1 (n) <h2 (n)1 para todos los nodos del grafico implícito, entonces el algoritmo A* utilizando la función menos informada h1 (n) expandirá como mínimo los mismos nodos que expandiría usando h2 (n). esta propiedad nos dice que los algoritmos A* tienden a expandir menos nodos cuando h (n) se acerca a h*(n).

Donde C (ni, nj) es el coste del camino optimo entre los nodos ni y nj – podemos asegurar que cada nodo seleccionado por A* se encuentra con seguridad en el camino solución: el crecimiento de la complejidad es lineal con la profundidad de búsqueda (N). f (n) = g(n) + h(n): Coste real del plan (camino) de mínimo coste que pasa por n.

f* (n) = g(n) + h*(n): estimación de f Función heurística de A*: 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 Implementación algoritmo A* en pseudocódigo La complejidad del algoritmo está íntimamente relacionada con la calidad de la heurística que se utilice en el problema. En el caso peor, con una heurística de pésima calidad, la complejidad será exponencial, mientras que en el caso mejor, con una buena , el algoritmo se ejecutará en tiempo lineal. Para que esto último suceda, se debe cumplir que
h´(x)<=g(y)-g(x)+h´(y)
Donde h* es una heurística óptima para el problema, como por ejemplo, el coste real de alcanzar el objetivo Compeljidad Como todo algoritmo de búsqueda en amplitud, A* es un algoritmo completo: en caso de existir una solución, siempre dará con ella.
Si para todo nodo n del grafo se cumple g(n)=0, nos encontramos ante una búsqueda voraz. Si para todo nodo n del grafo se cumple h(n)=0, A* pasa a ser una búsqueda de coste uniforme no informada.
Para garantizar la optimalidad del algoritmo, la función  debe ser admisible, esto es, que no sobrestime el coste real de alcanzar el nodo objetivo. Propiedades De no cumplirse dicha condición, el algoritmo pasa a denominarse simplemente A, y a pesar de seguir siendo completo, no se asegura que el resultado obtenido sea el camino de coste mínimo. Asimismo, si garantizamos que  es consistente (o monótona), es decir, que para cualquier nodo  y cualquiera de sus sucesores, el coste estimado de alcanzar el objetivo desde n no es mayor que el de alcanzar el sucesor más el coste de alcanzar el objetivo desde el sucesor. Realizado por: Camilo Jimenez
Daniel Aljure
Daniel Alarcon gracias....
Full transcript