Algoritmos exhaustivos de búsqueda de rutas

Estos primeros algoritmos no son "inteligentes": se denominan exhaustivos, puesto que no utilizan ningún conocimiento relativo al problema para proceder. En el peor de los casos, comprueban todas las rutas posibles para determinar si existe alguna ruta entre ambos nodos.

Además, nada indica que la ruta encontrada sea la más corta. Sin embargo, son muy fáciles de implementar.

1. Búsqueda en profundidad Búsqueda:en profundidad

Se trata del algoritmo que probamos de manera natural en un laberinto: buscamos avanzar lo más rápido posible y, si nos bloqueamos, volvemos a la última intersección que hemos encontrado y probamos una nueva ruta.

Este algoritmo no permite determinar el camino más corto, sino simplemente encontrar un camino.

a. Principio y pseudo-código

Su funcionamiento es bastante sencillo.

En primer lugar, seleccionamos el orden en que recorreremos los nodos y, a continuación, aplicaremos este orden para avanzar lo máximo posible. Si nos bloqueamos, volvemos atrás, y probamos la siguiente posibilidad.

El recorrido en profundidad permite, por tanto, determinar la existencia de una ruta, pero no tiene en cuenta la longitud de los arcos, y por tanto no permite saber si se ha encontrado el camino más corto.

Además, el resultado obtenido depende en gran medida del orden escogido para recorrer el grafo, el orden óptimo depende de cada problema y no puede determinarse a priori. A menudo...

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
Ejemplo en cartografía
Siguiente
Algoritmos "inteligentes"