ALGORITMO A ESTRELLA

Fecha: 7  Noviembre  2014

OBJETIVO DE CLASE E INTRODUCCIÓN

El objetivo de la clase era que los alumnos compartan temas de exposición designada a cada uno de ellos. Además antes de iniciar con las clases la docente compartió un avance del contenido que ha futuro se iba a socializar.

Una pequeña introducción de que es el algoritmo de A* podría se argumentar que este tipo de algoritmo es uno de los más utilizados para trazar rutas de un lugar a otro. Por otro lado los sistemas de viajes en la vida real son los más beneficiados gracias a A * estrella.  Además A* se basa en la mejora de características que   de algoritmos creados anterior a este

 

MARCO TEÓRICO

DEFINICIÓN

En ciencias de la computación, A * (pronunciado «Una estrella» (escuchar)) es un algoritmo informático que se utiliza ampliamente en la búsqueda de caminos y el gráfico de recorrido, el proceso de planear una ruta eficiente transitable entre puntos, llamados nodos. Destaca por su rendimiento y precisión, goza de amplio uso. Sin embargo, en los sistemas con los viajes de enrutamiento prácticos, se superó en general por medio de algoritmos que pueden pre-proceso de la gráfica para lograr un mejor rendimiento, (Delling etall. 2009)aunque otros trabajos ha encontrado A * sea superior a otros enfoques(Zeng & Church. 2014)

Peter Hart, Nils Nilsson y Bertram Raphael del Instituto de Investigación de Stanford (ahora SRI International) describieron por primera vez el algoritmo en 1968(Hart, etall. 1968). Se trata de una extensión de 1959 el algoritmo de Edsger Dijkstra. A * logra un mejor rendimiento tiempo usando heurística

 

A * es como el algoritmo de Dijkstra en que se puede utilizar para encontrar un camino más corto. A * es como Greedy Best-First-Búsqueda en que puede utilizar una heurística para guiar a sí mismo. En el caso simple, es tan rápido como Greedy Best-First-Buscar:

 

A * algoritmo de búsqueda

 

La heurística de búsqueda hace uso del hecho de que la mayoría de los espacios de problemas proporcionan alguna información que distingue entre los estados en términos de la probabilidad de que conduce a una meta. Esta información se llama una función de evaluación heurística (Pearl & Korf, 1987). En otras palabras, el objetivo de una búsqueda heurística es reducir el número de nodos buscado en la búsqueda de un objetivo (Kopec y Marsland, 2001).

 

Mejor forma primera búsqueda más utilizado se llama A *, que se pronuncia como una estrella. Se trata de un método de búsqueda heurística, y se utiliza para minimizar el costo de búsqueda en un problema dado (BOLC y Cytowski, 1992). Su objetivo es encontrar la ruta de menor costo desde un nodo inicial dado a la meta específica. Es una forma extendida de primero el mejor algoritmo de búsqueda. Mejor algoritmo de primera búsqueda trata de encontrar una solución para reducir al mínimo el coste total de la ruta de búsqueda, también. Sin embargo, la diferencia de Best-First Search es que A * también tiene en cuenta el costo desde el principio, y no simplemente el costo local del nodo sido anteriormente. Lo mejor primera búsqueda encuentra un estado objetivo en cualquier espacio del problema predeterminado. Sin embargo, no puede garantizar que va a elegir el camino más corto hacia la meta (Pearl & Korf, 1987). Por ejemplo, si hay dos opciones para elegir, uno de los cuales es un largo camino desde el punto inicial, pero tiene una estimación ligeramente más corto de la distancia a la meta, y otro que está muy cerca de su estado inicial, pero tiene un poco más largo estimación de la distancia al objetivo, primero el mejor búsqueda siempre optar por ampliar siguiente el estado con la estimación más corto. El algoritmo A * soluciona este inconveniente particular, la mejor primera de búsqueda (Pearl & Korf, 1987).

En resumen, un algoritmo * busca en todas las rutas posibles desde el punto de partida hasta que encuentra el camino más corto o más barato a un objetivo. Los términos como camino más corto, el más barato el costo aquí se refiere a una noción general. Podría ser algún otro término alternativo dependiendo del problema. Por ejemplo, en un problema mapa el costo se sustituye por la distancia plazo (Cawsey, 1998). Esto puede reducir la necesidad de buscar todas las posibles vías en un espacio de búsqueda, y el resultado en solución más rápida. A * evalúa mediante la combinación de los nodos g (n) y h (n). En la terminología estándar que se utiliza cuando se habla de A *:

CONCLUSIÓN

Según lo analizado anteriormente se puede concluir que A* está catalogado con unos de los mejores algoritmos de búsquedas en grafos o arboles binarios, debido a su forma de como maneja sus costes. Por otro lado la retroalimentación de la docente es un plus muy importante para hacer que los conocimientos adquiridos permanezcan vigentes.

A estrella es la mejora de algoritmos que estaban antes de que este algoritmo haya existido.

 REFERENCIAS

Delling, D; Sanders, P; Schultes, D; Wagner, D. 2009.  «Engineering route planning algorithms». Algorithmics of Large and Complex Networks: Design, Analysis, and Simulation. Springer.  volume 5515

Zeng, W; Church,  L. 2009. «Finding shortest paths on real road networks: the case for A*». International Journal of Geographical Information Science.  Volume 23

Hart, P; Nilsson, N; Raphael, B. 1968.  «A Formal Basis for the Heuristic Determination of Minimum Cost Paths». IEEE Transactions on Systems Science and Cybernetics. Vol 4

Bolc, L; & Cytowski, J. 1992. Search Methods for Artificial Intelligence. London: Academic Press.

Cawsey, A. (1998). The Essence of Artificial Intelligence. Upper Saddle River, NJ: Prentice Hall. ISBN:0135717795

Kopec, D. & Marsland, T.A. 2001. Search. Retrieved October 10 2008, Formato PDF. Disponible en: http://www.cs.ualberta.ca/~tony/RecentPapers/Draft.5.2.pdf

Pearl, J. & Korf, R. 1987. Search techniques. Annual Review of Computer Science, 451-467. Vol 3

Russell, S. J., & Norvig, P. (2003). Artificial Intelligence: A Modern Approach. Upper Saddle River, NJ: Prentice Hall. ISBN:0136042597