A*
Los algoritmos de búsqueda nacen por la necesidad de crear un mecanismo de navegación autónoma, bien sea de robots, coches, o personajes en un videojuego. Algunos de los más conocidos son A*, LPA*, o D*.
El algoritmo de búsqueda A* (pronunciado “A asterisco” o “A start”) se clasifica dentro de los algoritmos de búsqueda. El algoritmo A encuentra, siempre y cuando se cumplan unas determinadas condiciones, el camino de menor coste* entre un nodo origen y uno objetivo.
La complejidad computacional del algoritmo está íntimamente relacionada con la calidad de la heurística que se utilice en el problema. En el caso peor, con una heurística de pésima calidad, la complejidad será exponencial, mientras que en el caso mejor, con una buena, el algoritmo se ejecutará en tiempo lineal.
Para que esto último suceda, se debe cumplir que donde h’ es una heurística óptima para el problema, como por ejemplo, el coste real de alcanzar el objetivo.
Dijkstra
El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de los vértices en un grafo con pesos en cada arista.
La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el tablero, el algoritmo se detiene. El algoritmo es una especialización de la búsqueda de costo uniforme, y como tal, no funciona en tableros con aristas de coste negativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidos de la búsqueda nodos que en próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).
Una de sus aplicaciones más importantes reside en el campo de la telemática, gracias a el, podemos resolver caminos con muchos nodos, los cuales serian muy complicados de hacer sin dicho algoritmo, encontrando así las rutas más cortas entre un origen y todos los destinos en una red.
