algorithm - sort - Tipo topológico con una función objetivo
topological sort c++ (2)
Tengo un DAG con N nodos, es decir, 1, 2, ..., N , y cada nodo tiene un peso (podemos llamarlo tiempo) x_1, x_2, ..., x_N . Quiero hacer una clasificación topológica, pero la dificultad es que tengo una función objetiva al ordenar. Mi función objetivo es minimizar el tiempo total entre varios pares de nodos.
Por ejemplo, tengo un DAG con 6 nodos, y quiero una clasificación topológica específica tal que (1,3) + (2,4) se minimice, donde (A,B) denota el tiempo entre dos nodos A y B. Por ejemplo, si tenemos un tipo [1, 6, 3, 2, 5, 4, 7] , (1,3) = x_6 y (2,4) = x_5 . Basado en el DAG, quiero encontrar una clasificación que minimice (1,3) + (2,4) .
He estado pensando en este problema por un tiempo. Genere todos los ordenamientos topológicos posibles ( enlace de referencia) y calcule la función objetivo una por una siempre es una posible solución, pero lleva mucho tiempo si N es grande. También me sugirieron usar la poda de la sucursal cuando genero todos los géneros posibles (no estoy muy familiarizado con la sucursal, pero creo que eso no reducirá drásticamente la complejidad).
Algún algoritmo (óptimo o heurístico) para este tipo de problema? Sería perfecto si el algoritmo también se puede aplicar a otras funciones objetivas, como minimizar el tiempo de inicio total para algunos nodos. Cualquier sugerencia es apreciada.
PD: O, alternativamente, ¿es posible formular este problema como un problema de optimización de entero lineal?
Una forma de resolver esto es la siguiente:
Primero ejecutamos el algoritmo de ruta más corta All-Pairs Floyd-Warshall . Este algoritmo puede codificarse esencialmente en 5 líneas de código y se ejecuta en O(V^3) tiempo. Genera los caminos más cortos entre cada par de vértices en el gráfico, es decir, genera la matriz VXV de trayectos más cortos como su salida.
Es trivial modificar este algoritmo para que también podamos obtener el recuento de vértices incluidos en cada una de las rutas O(N^2) . Entonces ahora podemos eliminar todos los caminos que tienen menos de N vértices. Para las rutas restantes, las ordenamos por su costo y luego probamos cada una de ellas para ver si no se infringe la propiedad de clasificación topológica. Si esta propiedad no es violada, entonces hemos encontrado nuestro resultado deseado.
El último paso anterior, es decir, probar el orden topológico, se puede realizar en O (V + E) para cada una de las rutas O (V ^ 2). Esto produce el peor tiempo de ejecución de O(V^4) . Sin embargo, en la práctica esto debería ser rápido porque Floyd-Warshall puede ser muy amigable con la caché y estaríamos probando solo una pequeña fracción de O (N ^ 2) caminos en realidad. Además, si su DAG no es denso, entonces podría optimizar también las pruebas topológicas con las estructuras de datos apropiadas.
Aquí hay una idea:
Para simplificar, primero suponga que tiene un solo par para optimizar (comentaré más adelante sobre el caso general) y suponga que ya tiene su gráfico ordenado topológicamente en una matriz.
Tome el segmento de matriz que comienza en el nodo inferior (en términos de su orden topológico ) del par, digamos l , y terminando en el nodo superior, digamos h . Para cada nodo individual ordenado entre l y h , calcule si está limitado desde abajo por l y / o limitado desde arriba por h . Puede calcular la propiedad anterior marcando los nodos en un BFS "hacia arriba" desde l , cortando en nodos ordenados por encima de h ; y de manera similar, este último al marcar en un BFS "hacia abajo" desde h , cortando en nodos ordenados debajo de l . La complejidad de cualquiera de los pases será O (B * L), donde B es el factor de ramificación, y L es la cantidad de nodos originalmente clasificados entre l y h .
Ahora, todos los nodos que no están acotados desde arriba por h pueden moverse por encima de h , y todos los nodos que no están acotados desde abajo por l pueden moverse por debajo de l (los dos conjuntos pueden superponerse), todo sin violar la clasificación topológica del array, siempre que se conserve el orden original ordenado dentro de cada grupo de nodos reubicado hacia arriba o hacia abajo.
Este mismo procedimiento se puede aplicar a tantos pares como sea necesario, siempre que los segmentos que cortan del orden de clasificación original no se superpongan.
Si dos pares se superponen, digamos (l1, h1) y (l2, h2) , de modo que, por ejemplo, l1 <l2 <h1 <h2 en el orden original ordenado , tiene los dos casos siguientes:
1) En el caso trivial donde h1 y l2 no están relacionados en el orden topológico , entonces usted debería poder optimizar los dos pares mayormente de forma independiente el uno del otro, solo aplicando algún cuidado para mover l2 sobre h1 o h1 debajo de l2 ( pero no por ejemplo, h1 por debajo de l1 , si eso resultara posible).
2) Si l2 <h1 en el orden topológico , puede tratar ambos pares como el par único (l1, h2) , y luego posiblemente aplicar el procedimiento una vez más a (l2, h1) .
Como no está claro lo que el proceso completo logrará en el caso de superposición no trivial, especialmente si tiene patrones superpuestos más complicados, puede ser mejor tratar a todos los pares uniformemente, independientemente de la superposición. En este caso, la orden puede procesarse repetidamente mientras que cada ejecución produce una mejora con respecto a la anterior (no estoy seguro si el procedimiento será monótono en términos de la función objetivo, aunque probablemente no).