« Topics Navigator « || Inicio || » Clustering por K-medi… »

Algoritmo A*

Última modificación: 27 de Mayo de 2017, y ha tenido 1466 vistas

Etiquetas utilizadas: || || ||

La familia de los algoritmos de búsqueda informada, frente a los de búsqueda ciega, es aquella que posee una información extra sobre la estructura del espacio en el que se realiza la búsqueda, lo que les permite alcanzar más rápidamente (o con menor coste) su objetivo final.

El problema de algunos algoritmos de búsqueda informada en estructuras de relativa complejidad (como puede ser el algoritmo voraz) es que se guían exclusivamente o bien por una función heurística (que les "orienta" dónde puede estar el camino mejor, pero no tienen la seguridad), o por el coste real de desplazarse de un nodo a otro (como los algoritmos de escalada), pudiéndose dar el caso de que sea necesario realizar un movimiento de coste mayor para alcanzar la solución. Es por ello bastante normal pensar que un buen algoritmo de búsqueda informada debería tener en cuenta ambos factores, el valor heurístico de los nodos y el coste real del recorrido.

El algoritmo de búsqueda A* se clasifica dentro de estos algoritmos de búsqueda informada. Fue presentado por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael, siguiendo el esquema de utilizar una función heurística junto a el calculo del coste real del camino recorrido, y siempre y cuando se cumplan unas determinadas condiciones, calcula el camino de menor coste entre el origen y el objetivo.

Puedes obtener más información acerca de algoritmos informados, y temas relacionados, en la página de la asignatgura de Inteligencia Artificial que llevo en este mismo sitio.

« Topics Navigator « || Inicio || » Clustering por K-medi… »