Según wikipedia, el algoritmo A* (A estrella) es un algoritmo de búsqueda en grafos de tipo heurístico. No sé vosotras, pero yo leo esto y me quedo impresionada por las palabras tan chulas que he leído, pero sin tener ni idea de qué significa. Así que vamos a entenderlo poco a poco.
Para empezar, un algoritmo es un conjunto de instrucciones u operaciones que permiten solucionar un problema. Este algoritmo es un algoritmo de búsqueda en grafos, lo que indica que partimos de un conjunto de nodos conectados entre sí, algo como lo que vemos en la siguiente imagen:
Por último, que sea de tipo heurístico implica que se basa en reglas que permiten escoger aquellas ramas del espacio de estados que llevan a las posibles soluciones del problema.
La función del algoritmo A* es encontrar el camino que implique menos costes entre un nodo de origen y un nodo final.
Así, en resumen, el algoritmo A* consiste en un conjunto de instrucciones que nos permiten movernos entre nodos encontrando el camino que supone un menor coste.
Este algoritmo fue el que se usó para que el ordenador Deep Blue ganase al ajedrez al campeón mundial Kasparov en 1998. Dicho así suena a que es un algoritmo bastante potente (que lo es), pero no es perfecto, sino que tiene algunos inconvenientes y hay problemas que no puede resolver.
El principal problema de este algoritmo es que requiere de mucha memoria, requiriendo más y más espacio (de manera exponencial) cuanto mayor sea el tamaño del problema. Esto ocurre porque tiene que evaluar todas las posibles soluciones en cada momento. Por esta complejidad computacional, este algoritmo no podría solucionar problemas que sean demasiado grandes.
Otro problema que tiene el algoritmo A* es que maneja una información limitada y estática. Por lo tanto, problemas que necesiten de dinamismo o que sean cambiantes tampoco podrían ser resueltos por el algoritmo.
Comentarios
Publicar un comentario