Algoritmo de tiempo lineal para encontrar

8

Definición. Dado un gráficosol=(V,mi) y dos vértices s y t, la k-shortest-caminos problema es encontrar el k caminos sencillos más cortos entre s y t en sol.

Tenga en cuenta que la longitud de estos caminos no es necesariamente igual, y los vértices s y t son necesariamente k-conectado. Me preguntaba si hay un tiempo lineal (en términos denorte y metro) 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 altaO(Kn(metro+nortelosolnorte)). Además, el otro artículo de Epstein " Encontrar las k rutas más cortas " presenta un algoritmo que encuentra elk rutas más cortas que no son necesariamente simples con tiempo de ejecución O(norte+metro+k).

¿Existe un algoritmo de tiempo lineal para el k-simple-shortest-caminos problema?

orezvani
fuente
El algoritmo de @DW Eppstein encuentra caminos que no son necesariamente simples. OP quiere un algoritmo similar, posiblemente en el mismo tiempo de ejecución, que encuentre elkcaminos sencillos más cortos. El algoritmo de clasificación de Yen es demasiado lento para eso.
Yuval Filmus

Respuestas:

7

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 computakcaminos ó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:

ingrese la descripción de la imagen aquí

La figura muestra un dígrafo cuya solución óptima (desde el vértice de origen s al vértice de la meta t) es el camino π1:s,UNA,si,C,re,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áfico G(V,E) dónde V es el conjunto de vértices y u,vE,u,vV 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 el k El problema de las rutas óptimas es el algoritmo de Eppstein (Eppstein, 1998) que se ejecuta en O(El |miEl |+El |VEl |Iniciar sesiónEl |VEl |+k). Sin embargo, este algoritmo requiere que el gráfico se dé explícitamente.Kalivia 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 en O(kEl |VEl |(El |miEl |+El |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(El |miEl |+El |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 kcaminos más cortos Inteligencia artificial, 175 (18), 2129-2154.

Eppstein, D. (1998). Encontrar elkcaminos más cortos SIAM Journal on Computing, 28 (2), 652-673.

Hershberger, J., Maxel, M. y Suri, S. (2007). Encontrar elkcaminos 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 parakcaminos sencillos más cortos. Redes, 12, 411-427.

Lawler, EL (1972). Un procedimiento para calcular elkmejores 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 elkrutas sin bucles más cortas en una red. Management Sciences, 17, 712-716.

Yen, JY (1972). Otro algoritmo para encontrar elkrutas de red sin bucles más cortas. Actas de la 41ª Sociedad de Investigación de Operaciones de Gestión de América, 20.

Carlos Linares López
fuente
Gracias, esto realmente funciona en O(norte+metro)en gráficos no ponderados. De hecho, un artículo más reciente (mencionado en la pregunta) me hizo pensar que su tiempo de ejecución debe ser mejor que el de Kotah; Me dio una impresión equivocada.
orezvani
Feliz de escuchar que te gusta @kezzos
Carlos Linares López