Máster de Cultura Científica EHU/UPNA 2023/2024 Introducción a la Inteligencia Artificial. Tarea 3.

La tarea consiste en apuntar qué tipos de problemas no podrían ser resueltos por el algoritmo A *.  

 

El algoritmo A* (A estrella) es un algoritmo de búsqueda informada que se utiliza para encontrar el camino más corto entre un punto de origen y un final en problemas de grafos complejos. Y lo hace apoyándose en información heurística, datos que se aportan para apostar por aquellas rutas o nodos por las que hay más posibilidad de encontrar una solución óptima y que, por tanto, vale la pena desarrollar en detrimento de otras. Así se asegura reducir la cantidad de búsqueda requerida para encontrar una solución. Cuanto mejor sea esta información, mejor será el algoritmo. El algoritmo tiene en cuenta, además, el coste de llegar del punto A al Z, y se busca siempre que sea el menor posible. De esta forma, siempre que haya una solución, encontrarán una óptima.

El algoritmo A estrella fue presentado por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael y es el más utilizado para aplicar a problemas de pathfinding o búsqueda de caminos: el algoritmo buscará el más rápido y con menor coste. De esta forma, el algoritmo está detrás de la programación de agentes que son capaces de moverse de forma autónoma por un entorno con obstáculos (como un videojuego), o un robot; se utiliza en resolución de juegos de mesa; en pilotaje automático en aeronavegación o transporte; y en otras aplicaciones como enrutar datos de voz en redes de telefonía, minimizar la distribución de componentes en circuitos impresos o para generar planes automatizados en una cadena.

Por sus características, el algoritmo no puede ser aplicado en problemas donde no estén definidos el punto de origen o el de llegada, donde no haya una solución o ésta no se pueda desarrollar en etapas a través de una secuencia lógica. Tampoco podría aplicarse en problemas en los que las etapas no estén claramente definidas y haya factores que sean cambiantes o dinámicos y tampoco en problemas grandes ya que la cantidad de memoria requerida para ponerlo en marcha es exponencial con respecto al tamaño del problema.