Estoy resolviendo un problema de optimización de búsqueda de gráficos. Necesito encontrar las k mejores rutas acíclicas más cortas a través de un gráfico ponderado dirigido.
Sé que hay una serie de algoritmos k-best exactos y aproximados, pero la mayor parte de la investigación reciente parece estar orientada hacia gráficos muy grandes y muy poco conectados (por ejemplo, enrutamiento y direcciones de carreteras), y mi gráfico no lo es.
Aspectos distintivos de mi problema:
El gráfico consta de aproximadamente 160 vértices.
El gráfico está casi completamente conectado (bidireccionalmente, entonces ~ 160 ^ 2 ~ = 25k bordes)
k será bastante pequeño (probablemente menos de 10)
La longitud máxima de la ruta probablemente será limitada y también muy pequeña (por ejemplo, 3-5 bordes)
Dije "acíclico" arriba, pero solo para reiterar: las soluciones no deben incluir ciclos. Este no es un problema para la mejor ruta más corta, pero se convierte en un problema para k-mejor; por ejemplo, considere una ruta de ruta: la segunda ruta más corta de A a B podría ser la misma que la 1 mejor, con un viaje rápido alrededor de una cuadra en alguna parte. Eso podría ser matemáticamente óptimo, pero no es una solución muy útil. ;-)
Es posible que necesitemos volver a pesar los bordes sobre la marcha para cada cálculo. Un costo de borde consiste en una suma ponderada de varios factores, y los requisitos finales (siempre que los obtengamos) pueden permitir que un usuario especifique su propia priorización de esos factores de ponderación, alterando los pesos de borde. Este es un gráfico relativamente pequeño (deberíamos poder representarlo en unos pocos cientos de KB), por lo que probablemente sea razonable clonar el gráfico en la memoria, aplicar la nueva ponderación y luego ejecutar la búsqueda en el gráfico clonado. Pero si hay un método más efectivo para realizar la búsqueda mientras se calculan los pesos sobre la marcha, me interesa.
Estoy viendo los algoritmos descritos en Santos (K algoritmos de ruta más corta), Eppstein 1997 (Encontrar las k rutas más cortas) y otros. El algoritmo de Yen es de interés, principalmente debido a la implementación de Java existente . No tengo miedo de leer los trabajos de investigación, pero pensé que valía la pena tirar los detalles de mi problema y pedir consejos para ahorrar algo de tiempo de lectura.
Y si tiene punteros a las implementaciones de Java, aún mejor.
fuente
Respuestas:
Para responder parcialmente mi propia pregunta:
Desde que publiqué esta pregunta, descubrí que necesitamos manejar pesos de borde negativos y positivos (la limitación a las rutas acíclicas / simples / sin bucle significa que la mejor solución está definida, mientras que sin esa limitación la ruta más corta a través de un gráfico con negativo- los ciclos de costos no están definidos).
El algoritmo de Yen, y la mayoría de los otros que examiné, dependen de una serie de 1 mejores búsquedas; la mayoría usa Dijkstra para esas búsquedas intermedias. Dijkstra no admite pesos de borde negativos, pero podemos sustituir a Bellman-Ford en su lugar (al menos en yenes; presumiblemente también en Lawler o Eppstein). Desarrollé una modificación de Bellman-Ford con una limitación de longitud de ruta (en bordes) y verificación de ciclo explícita durante la búsqueda (en lugar de la detección estándar del ciclo posterior a la búsqueda). La complejidad computacional es peor, pero aún manejable para mis requerimientos. Editaré esta respuesta y vincularé a un informe técnico si obtengo permiso para publicarlo.
fuente
Yo diría que esta pregunta se puede buscar fácilmente en Google y también es un duplicado:
Dicho esto, ya usé e implementé Eppstein y lo recomiendo. Lo encontré bastante elegante. Si recuerdo bien, también puede ser óptimo, y el siguiente artículo lo explica muy bien:
http://pdf.aminer.org/001/059/121/finding_the_k_shortest_paths.pdf
fuente