El algoritmo A*

El algoritmo A* se utiliza para resolver problemas cuando se desean encontrar caminos mínimos entre una posición inicial origen y una final objetivo. Este algoritmo conocido también como A estrella fue propuesto por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael. Como ya se ha dicho es un algoritmo, o conjunto de pasos a dar para la solución de un problema, para solucionar problemas de pathfinding, búsqueda de caminos.



Es un algoritmo heurístico, basado en el estudio de las diversas opciones, que se ha utilizado mucho desde cuando se creó. Este algoritmo valora todas las opciones para cada movimiento proponiendo un camino ha seguir.

El mayor problema de este algoritmo es que precisa de mucha memoria para poder proponer soluciones ya que en cada paso evalúa todos los movimientos posibles proponiendo los más adecuados que en ocasiones pueden ser varios. Para problemas relativamente sencillos puede ser adecuado pero a medida que se complica el problema la necesidad de memoria crece exponencialmente.

Otro problema que puede presentar es que no es muy adecuado para problemas dinámicos o que varíen una vez empezado el análisis de la solución. Ya que el algoritmo asigna unos valores a cada celda en función de su proximidad o lejanía tanto desde el origen como al objetivo. Si variamos las condiciones parece que el resultado obtenido so sería el idóneo.

A medida que se consigan computadoras mas potentes y con mayor velocidad computacional puede ser que el algoritmo A* se capaz de resolver satisfactoriamente cada vez problemas mas complejos.


Referencias:

https://www.lanshor.com/pathfinding-a-estrella/

https://es.wikipedia.org/wiki/Algoritmo_de_b%C3%BAsqueda_A*

http://www.cs.umss.edu.bo/doc/material/mat_gral_139/Busqueda%20A%20estrella-2.pdf

http://www.cs.us.es/~fsancho/?e=42


Imagen:

https://malnuer.es/wp-content/uploads/2015/07/algoritmo_a_star.png


Comentarios

Publicar un comentario

Entradas populares de este blog

Ciencia: ¿de lo general a lo particular, o viceversa?

Imagen
Distinguir que método, inductivo o deductivo, se ha utilizado en una determinada investigación parece una tarea sencilla pero, en mi caso, he tenido que reflexionar y leerme unos cuantos artículos para poder elegir dos artículos en los que sea claro cual de los métodos mencionados se ha utilizado. En una investigación o racionamiento deductivo, como bien se explica en este articulo de Sol Martos publicado en cinconoticias.com, se parte de unas premisas que se aceptan como leyes o principios generales y mediante el razonamiento, la toma de datos o diseño de experimentos se llega a una conclusión particular. El camino que se realiza va desde un principio general a lo particular. En una investigación donde se utiliza el método deductivo, sin embargo, el camino que se realiza va en sentido contrario al mencionado. Mediante este método se toman unos datos o se realizan unas observaciones concretas o particulares y lo que se intenta es de buscar una ley o conclusión que justifique las obs
Leer más

Inteligencia artificial: evolución continua

Imagen
La inteligencia artificial se empezó a desarrollar en los años 50 del siglo pasado y desde entonces el concepto ha ido evolucionando y tomando nuevos significados. En un inicio la inteligencia artificial hacia referencia al sueño de construir máquinas capaces de razonar al estilo de los humanos, lo que se conocía como inteligencia artificial fuerte. Por otro lado también podemos hacer referencia a la inteligencia artificial débil o estrecha que se refiere a la capacidad de una máquina de resolver un tipo concreto o específico de problema, como puede ser el caso del ordenador que es capaz de jugar al ajedrez mejor que los humanos, pero no son capaces de realizar otra tareas para las que no están previamente entrenados. Por otro lado tenemos otro aspecto o rama de la inteligencia artificial, el aprendizaje automático. Consiste, básicamente, en que el ordenador vaya adquiriendo conocimientos mediante la experiencia supervisada. Con la ayuda de perceptrónes, que son redes neuronales artifi
Leer más

Los Algoritmos de Google

Imagen
Es bien conocido que Google es el buscador mas utilizado en todo el mundo. Se estima que Google acapara mas del 92% del mercado y este liderazgo lo mantiene con mucha ventaja. El segundo posicionado es el motor de búsqueda Bing con el 2,34% del mercado al que le sigue el buscador Yahoo con el 1,6%. Queda claro que la herramienta favorita de los usuarios, si lugar a dudas, es el todopoderoso y omnipresente Google. Google, que en sus inicios se llamaba BackRub, se creó como un proyecto universitario de los estudiantes de posgrado Larry Page y Sergey Brin en 1996. Ambos estudiantes de ciencias de la computación en la universidad de Stanford. El cambio de nombre, en referencia al termino gúgon que es el número 10 elevado a 100, se realizó en 1997. El nombre nos hace recordar este número tan grande haciéndonos conscientes de la gran cantidad de información disponible en la web con la que el motor de búsqueda tiene que trabajar en todo momento. El 27 de 1998 se crea la compañía Google in
Leer más