Pathfinding
Pathfinding o ruta es el trazado, mediante una aplicación informática, de la ruta más corta entre dos puntos. Es una variante más práctica para resolver laberintos . Este campo de investigación se basa en gran medida en el algoritmo de Dijkstra para encontrar el camino más corto en un gráfico ponderado .
La búsqueda de rutas está estrechamente relacionada con el problema de la ruta más corta , dentro de la teoría de grafos , que examina cómo identificar la ruta que mejor cumple con algunos criterios (la más corta, la más barata, la más rápida, etc.) entre dos puntos de una red grande.
En esencia, un método de búsqueda de rutas busca en un gráfico comenzando en un vértice y explorando los nodos adyacentes hasta que se alcanza el nodo de destino, generalmente con la intención de encontrar la ruta más barata. Aunque los métodos de búsqueda de gráficos, como la búsqueda en amplitud , encontrarían una ruta si se les diera el tiempo suficiente, otros métodos, que "exploran" el gráfico, tenderían a llegar antes al destino. Una analogía sería una persona que cruza una habitación; en lugar de examinar todas las rutas posibles de antemano, la persona generalmente caminaría en la dirección del destino y solo se desviaría del camino para evitar una obstrucción y hacer las desviaciones lo más pequeñas posible.
Dos problemas principales de la búsqueda de rutas son (1) encontrar una ruta entre dos nodos en un gráfico ; y (2) el problema del camino más corto: encontrar el camino más corto óptimo . Los algoritmos básicos, como la búsqueda en amplitud y en profundidad, abordan el primer problema agotando todas las posibilidades; a partir del nodo dado, iteran sobre todas las rutas potenciales hasta que alcanzan el nodo de destino. Estos algoritmos se ejecutan en tiempo lineal, donde V es el número de vértices y E es el número de aristas entre vértices.
El problema más complicado es encontrar el camino óptimo. El enfoque exhaustivo en este caso se conoce como el algoritmo de Bellman-Ford , que produce una complejidad de tiempo de , o tiempo cuadrático. Sin embargo, no es necesario examinar todos los caminos posibles para encontrar el óptimo. Algoritmos como A * y el algoritmo de Dijkstra eliminan estratégicamente las rutas, ya sea mediante heurística o mediante programación dinámica . Al eliminar rutas imposibles, estos algoritmos pueden lograr complejidades de tiempo tan bajas como . [1]
Los algoritmos anteriores se encuentran entre los mejores algoritmos generales que operan en un gráfico sin preprocesamiento. Sin embargo, en los sistemas prácticos de enrutamiento de viajes, se pueden lograr incluso mejores complejidades de tiempo mediante algoritmos que pueden preprocesar el gráfico para lograr un mejor rendimiento. [2] Uno de esos algoritmos son las jerarquías de contracción .
