A. Sedeño Noda, M. M. B. Pascoal
En este trabajo, consideramos el problema de los K mejores caminos conectando un par de nodos en un grafo sin ciclos dirigido (DAG) con longitudes arbitrarias. Demostramos que el árbol conteniendo el k-ésimo mejor camino difiere sólo en un arco con alguno de los (k-1) árboles conteniendo los (k-1) primeros mejores caminos. Esto nos permite diseñar un algoritmo de complejidad temporal O(m + K(n + logK)) y complejidad espacial O(K + m) para redes con longitudes reales. En el caso de DAGs con longitudes enteras la complejidad temporal se reduce a O(m + Kn). Un estudio computacional revela que el algoritmo propuesto supera en la práctica a los algoritmos existentes en la literatura.
Palabras clave: optimización combinatoria, algoritmos de caminos mínimos, k mejores soluciones
Programado
XA4 Optimización combinatoria y optimización entera
18 de abril de 2012 09:00
Sala París
