Resumen

La búsqueda de rutas, o pathfinding, permite vincular los nodos de un grafo utilizando arcos predefinidos. Estos están asociados a una longitud (o coste). Es posible, también, buscar la ruta con el menor coste, siendo el coste un kilometraje, un tiempo o incluso un precio (por ejemplo, la gasolina consumida).

Existen varios algoritmos, cada uno con sus particularidades.

Cuando se intenta saber si existe un camino, sin buscar el más corto, podemos utilizar algoritmos de búsqueda exhaustiva en profundidad o en anchura. Si se sabe, de manera global, en qué dirección ir, la búsqueda en profundidad puede resultar interesante (siempre que se le precise bien el orden para recorrer los nodos vecinos).

La búsqueda en anchura produce, generalmente, mejores resultados y es, sobre todo, más genérica. En ambos casos, se avanza de nodo en nodo y se memorizan los nodos adyacentes descubiertos, que visitaremos posteriormente. Se diferencian en la estructura utilizada para almacenar los nodos vecinos: una pila para la búsqueda en profundidad y una cola para la búsqueda en anchura.

El algor ...

Si desea saber más, le proponemos el siguiente libro:
couv_DPT2INT.png
60-signet.svg
Versión impresa
20-ecran_lettre.svg
Versión online
41-logo_abonnement.svg
En ilimitado con la suscripción ENI
130-boutique.svg
En la tienda oficial de ENI
Anterior
Implementación
Siguiente
Presentación del capítulo