La llegada de los ordenadores e internet supusieron un cambio en nuestras vidas. Solo hay que pensar en la cantidad de vocabulario nuevo que hemos aprendido e introducido en nuestras conversaciones. Spam, hacker o algoritmo son algunas de ellas. De estos últimos hablaremos hoy. Un algoritmo no es más que una secuencia de pasos ordenados que permiten resolver un problema. La realidad es que, aunque el término esté actualmente de moda, los algoritmos están muy presentes en nuestras vidas. Y es que seguro que alguna vez has montado un mueble siguiendo las instrucciones de un manual.
Hoy vamos a hablar sobre el “algoritmo A*”, que se utiliza para calcular el camino más corto y barato, siempre que exista, entre un nodo origen y un objetivo.
A* es un algoritmo de búsqueda en grafos de tipo heurístico. Esta palabra proviene del griego “heuriskein” y significa descubrir o encontrar. En el ser humano la heurística es innata ya que cada día tenemos que tomar decisiones y resolver problemas. En inteligencia artificial se busca algo similar. Ante un problema con un tamaño de búsqueda grande el tiempo para encontrar la solución no es asumible. De ahí que el algoritmo A* parta de conocimiento adicional con el objetivo de conseguir resultados de buena calidad en un tiempo razonable.
Este algoritmo se usa en muchos videojuegos para determinar el recorrido que el personaje u objeto debe hacer o, por ejemplo, para resolver el cubo de Rubik con la menor cantidad de movimientos.
¿Qué problemas no va a poder resolver este algoritmo?
Aquellos en los que la heurística que se proporciona no está bien definida. Por otro lado, como almacena todos los posibles nodos de cada estado, requiere mucha memoria (exponencial respecto al tamaño del problema). De ahí que los problemas con muchos nodos sean complicados de resolver. También tendrá limitaciones cuando existan objetos móviles o el terreno se vaya modificando. Esto puede ocurrir, por ejemplo, en algunos videojuegos.
A pesar de estas limitaciones, los algoritmos han llegado para facilitarnos el trabajo. Y es que gracias a ellos podemos resolver cada día muchos problemas de forma fácil y rápida, con mucha precisión.
No hay comentarios:
Publicar un comentario