Definición. Dado un gráfico y dos vértices y , la -shortest-caminos problema es encontrar el caminos sencillos más cortos entre y en .
Tenga en cuenta que la longitud de estos caminos no es necesariamente igual, y los vértices y son necesariamente -conectado. Me preguntaba si hay un tiempo lineal (en términos de y ) algoritmo para este problema.
He visto algunos artículos en la literatura, como " Una nueva implementación del algoritmo de rutas sin bucles de clasificación del yen ", pero la complejidad del tiempo es realmente alta. Además, el otro artículo de Epstein " Encontrar las k rutas más cortas " presenta un algoritmo que encuentra el rutas más cortas que no son necesariamente simples con tiempo de ejecución .
¿Existe un algoritmo de tiempo lineal para el -simple-shortest-caminos problema?
Respuestas:
En primer lugar, la respuesta que se aplica aquí ya fue dada por Raphael en los comentarios a la pregunta: " Dado que ni siquiera sabemos cómo encontrar un camino más corto simple en tiempo lineal, lo dudo " . A continuación, Por lo tanto, supondré que está interesado en conocer los mejores algoritmos disponibles en el estado actual de la técnica. A continuación, describo el mejor límite para el peor de los casos (que yo sepa) pero también un algoritmo que podría ejecutarse en tiempo lineal en algunos casos específicos.
Pero antes de describir los últimos desarrollos en el estado del arte, quería enfatizar la importancia de los senderos simples en este problema específico. De hecho, muchas personas pasan por alto la importancia de este requisito y algunas ni siquiera lo entienden a primera vista.
Cuando se calcula la ruta más corta desde un vértice inicial hasta un vértice objetivo, la ruta óptima es necesariamente simple , es decir, no repite ningún vértice. Sin embargo, cuando se computak caminos óptimos, el segundo, tercero, ... los mejores caminos podrían no ser simples. Para demostrarlo, proporciono aquí un ejemplo que ha sido ligeramente adaptado de Hershberger, Maxel & Suri, 2007:
La figura muestra un dígrafo cuya solución óptima (desde el vértice de origens al vértice de la meta t ) es el camino π1: ⟨ S , A , B , C, D , t ⟩ con un costo igual a 5. Si no se requiere que las rutas sean simples, entonces las rutas óptimas segunda y tercera son π2: ⟨ S , A , B , C,D,C,D,t⟩ y π3:⟨s,A,B,A,B,C,D,t⟩ ambos con un costo igual a 7. Sin embargo, si se requiere que las rutas sean simples, entonces las rutas óptimas segunda y tercera serían π2:⟨s,F,t⟩ y π3:⟨s,G,t⟩ con costos 10 y 11, respectivamente.
Dado un gráficoG(V,E) dónde V es el conjunto de vértices y ⟨u,v⟩∈E,u,v∈V si hay un borde entre vértices u y v , el estado actual de la técnica para este problema, según mi leal saber y entender, se describe a continuación:
La primera mejora significativa para resolver elk El problema de las rutas óptimas es el algoritmo de Eppstein (Eppstein, 1998) que se ejecuta en O(|E|+|V|log|VEl | +k) . Sin embargo, este algoritmo requiere que el gráfico se dé explícitamente.K∗ alivia este requisito manteniendo la baja complejidad (Aljazzar & Leue, 2011) y, además, permite la aplicación de heurísticas admisibles. En ambos casos, la salida calculada por estos algoritmos no son necesariamente rutas simples.
En caso de que se requiera que las rutas sean simples, los mejores resultados se deben a Yen (Yen, 1971, 1972), generalizado más tarde por Lawler (Lawler, 1972), que puede implementar estructuras de datos modernas enO ( k | VEl | ( | EEl | + | VEl | Iniciar sesiónEl | VEl | )) peor de los casos. En el caso de gráficos no dirigidos, Katoh, Ibaraki y Mine (Katoh, Ibaraki & Mine, 1982) mejoran el algoritmo de Yen paraO ( k ( | EEl | + | VEl | Iniciar sesiónEl | VEl | )) hora. Mientras que el peor caso asintótico de Yen está destinado a enumerark los senderos más cortos y simples en un gráfico dirigido permanecen invictos (de nuevo, ¡que yo sepa!), se han hecho varios intentos para superarlo en la práctica.
Uno de esos trabajos se debe a John Hershberger et al., Quien introdujo un algoritmo de rutas de reemplazo que se sabe que falla apenas. Como resultado, su algoritmo ofrece una aceleración que crece linealmente con el número promedio de bordes en elk caminos más cortos pero, en algunos casos (como gráficos aleatorios), esta aceleración se minimiza.
Espero que esto ayude,
Bibliografía
Aljazzar, H. y Leue, S. (2011).K∗ : Un algoritmo de búsqueda heurística para encontrar el k caminos más cortos Inteligencia artificial, 175 (18), 2129-2154.
Eppstein, D. (1998). Encontrar elk caminos más cortos SIAM Journal on Computing, 28 (2), 652-673.
Hershberger, J., Maxel, M. y Suri, S. (2007). Encontrar elk caminos simples más cortos: un nuevo algoritmo y su implementación. Transacciones ACM en Algoritmos, 3 (4), 45-46
Katoh, N., Ibaraki, T. y Mine, H. (1982). Un algoritmo eficiente parak caminos sencillos más cortos. Redes, 12, 411-427.
Lawler, EL (1972). Un procedimiento para calcular elk mejores soluciones a problemas de optimización discreta y su aplicación al problema de la ruta más corta. Management Science, 18, 401-405.
Yen, JY (1971). Encontrar elk rutas sin bucles más cortas en una red. Management Sciences, 17, 712-716.
Yen, JY (1972). Otro algoritmo para encontrar elk rutas de red sin bucles más cortas. Actas de la 41ª Sociedad de Investigación de Operaciones de Gestión de América, 20.
fuente