Ordenamiento topológico positivo

45

Supongamos que tengo un gráfico acíclico dirigido con pesos de números reales en sus vértices. Quiero encontrar un orden topológico del DAG en el que, para cada prefijo del orden topológico, la suma de los pesos no sea negativa. O si prefiere la terminología de la teoría del orden, tengo un orden parcial ponderado y quiero una extensión lineal para que cada prefijo tenga un peso no negativo. ¿Qué se sabe sobre este problema? ¿Es NP completo o solucionable en tiempo polinómico?

ds.algorithms directed-acyclic-graph partial-order David Eppstein
fuente

44

Pruebe el algoritmo codicioso en este gráfico: 1 -> 2 -> 3, 1 -> 4 -> 5, los pesos de vértice son 1: +2, 2: -2, 3: +3, 4: -1 , 5: -2. El algoritmo codicioso comenzaría con v1, luego elegiría v4 y luego se atascaría. El orden correcto es v1, v2, v3, v4, v5.

Robin Kothari

2

"Algunos de los problemas de distancia de Frechet que JeffE y otros han estado viendo" - ¡Buena abstracción! Para beneficio de otros, aquí hay una versión: supongamos que se le da un gráfico de plano ponderado por el borde G, y dos vértices sy tn la cara externa. Desea transformar una ruta de límite de s a t en la otra mediante una secuencia de movimientos elementales. Cada movimiento reemplaza la ruta actual con su diferencia simétrica con algún límite de cara. ¿Qué tan rápido podemos encontrar la secuencia mve que minimiza la longitud máxima de la ruta en evolución?

Jeffε

3

Tsuyoshi, perdón por eso, intenté agregar una nueva línea mientras comentaba y esto hizo que mi comentario se cortara. Entonces, la idea es que tienes una cuerda atada firmemente alrededor de tu muñeca y quieres saber si puedes quitártela. Su muñeca está representada como una malla poligonal, cuyas celdas son elementos de un orden parcial (más cerca de la cuerda antes, más cerca de apagado más adelante en el orden). El peso de una celda es la diferencia en longitudes entre sus límites internos y externos.

David Eppstein

1

@David: Gracias por la explicación. Esta vez puedo entender cómo se relaciona con la pregunta actual, ¡y es interesante!

Tsuyoshi Ito

3

Una observación no tan útil pero divertida: este problema es equivalente al problema de secuenciación de una sola máquina con plazos y restricciones de precedencia donde el tiempo de procesamiento de cada trabajo puede ser negativo . Con el tiempo de procesamiento no negativo, este problema está en P (Lawler y Mooer 1969 jstor.org/stable/2628367 ), y si existe una solución, entonces existe una solución que es independiente del tiempo de procesamiento. Esto se rompe claramente si algunos trabajos tienen un tiempo de procesamiento negativo.

Tsuyoshi Ito

18

Este problema parece ser muy similar a SECUENCIAR PARA MINIMIZAR EL COSTO ACUMULADO MÁXIMO, problema [SS7] en Garey & Johnson . Esto es:

$T$ $\prec$ $T$ $c(t) \in Z$ $t \in T$ $c(t) < 0$ $K \in Z$

$\sigma$ $T$ $t \in T$ $t'$ $\sigma(t') \leq \sigma(t)$ $K$

$K$ $c(t) \in \{-1,0,1\}$ $t \in T$

mhum
fuente

77

K = 0

$K=0$

c

$c$

- K

$-K$

K

$K$

c

$c$

- 1

$-1$

@mhum: estoy trabajando en un informe técnico sobre resultados relacionados y me gustaría citarlo. ¿Me darías tu nombre real? Si lo desea, puede enviarme un correo electrónico, o simplemente quedarse anon ...

domotorp

9

Bueno, mi respuesta es mi pregunta de la cual resulta que si pudieras resolver este problema en P, también podrías resolver otro problema abierto: ordenamiento topológico positivo, toma 3

Editar: este problema también resultó ser NP-completo, por lo que su problema ya está NP-completo si su DAG tiene solo dos niveles, es decir, si no hay rutas dirigidas con dos bordes.

domotorp
fuente

3

Si entiendo el problema correctamente, creo que la precedencia restringió el problema de programación de una sola máquina para minimizar la suma ponderada de los tiempos de finalización (1 | prec | \ sum wc) puede reducirse al problema que le interesa. En el problema 1 | prec | \ sum wc tenemos n trabajos, cada uno con un peso no negativo y un tiempo de procesamiento, un poset en los trabajos y queremos una extensión lineal de los trabajos de modo que la suma ponderada de los tiempos de finalización de los trabajos sea minimizado. El problema es NP-completo aunque suponemos que el tiempo de procesamiento de cada trabajo es igual a 1. ¿Tiene algún sentido?

monaldo
fuente

Definitivamente es una posibilidad interesante. Pero, ¿cómo hace la reducción de tal manera que el criterio de optimización (minimizar la suma de los tiempos de finalización) se transforme en restricciones (prefijos no negativos)?

David Eppstein

No conozco este resultado de completitud NP del problema de programación, pero creo que se refiere al problema de decisión de decidir si hay una extensión lineal tal que la suma ponderada de los tiempos de finalización del trabajo sea como máximo K, por lo tanto, no creo La distinción entre un criterio de optimización y una restricción es importante aquí. Sin embargo, no he entendido cómo representar la restricción en la suma ponderada de los tiempos de finalización en el problema actual.

Tsuyoshi Ito

Creo que la reducción no es tan fácil como pensaba al principio. Ya no estoy seguro de mi respuesta.

monaldo

Acabo de darme cuenta de un error en mi comentario anterior. Cuando lo publiqué, pensé que representar una restricción en la suma no ponderada era fácil (de ahí el énfasis en la ponderación ), pero eso era completamente incorrecto.

Tsuyoshi Ito

2

¿Qué pasa si siempre tomamos el elemento máximo (en el orden parcial) con el menor peso? Después de agotar los elementos, los devolvemos en orden inverso como la salida.

Daniel Martin
fuente

El problema es invariable bajo la transformación de revertir el ordenamiento parcial y negar todos los pesos. Así que no veo cómo esto puede ser diferente del algoritmo codicioso hacia adelante que Robin K dio un contraejemplo en los comentarios.

David Eppstein

Pero este método funciona para su ejemplo: primero, se elegiría el vértice 5, luego el vértice 4, luego 3, 2 y finalmente 1. Entonces, el orden final sería 1, 2, 3, 4, 5. De hecho, no No creo que sea difícil demostrar que este método funciona. Suponga que tiene una solución que no tiene un elemento máximo (sumidero) de peso mínimo en la última posición. Luego puede encontrar otra solución que tenga esta propiedad, simplemente cambiando la posición de dicho elemento para que dure y preservando el resto tal como está. Proceda por inducción sobre lo que queda, y obtendrá una prueba formal.

Daniel Martin

Sí ... no funciona ... 1 -> 2 -> 3, 1 -> 4 con pesos 4, -7, 6, 3 respectivamente.

Daniel Martin

1

Este problema me recuerda muchos árboles de decisión. Consideraría este tipo de solución, que trata de elegir siempre el camino más prometedor, pero mirando todo el subgráfico:

Comenzando desde los nodos de sumidero, avance hacia las fuentes, un nivel a la vez. Mientras haces esto, dale peso a cada borde. Este peso debe representar la cantidad mínima que tendrá que "pagar" o "ganará" atravesando el subgráfico comenzando desde el nodo al que apunta el borde. Supongamos que estamos en el nivel i + 1 y estamos subiendo al nivel i. Esto es lo que haría para asignar un peso para un borde que apunta a un nodo de nivel i:

edge_weight = señalando_nodo_peso.
Encuentre el borde a partir del "nodo señalador" con el peso máximo. Deje que este peso sea next_edge_weight.
edge_weight + = next_edge_weight

Luego, cree el orden de la siguiente manera:

Sea S la frontera de búsqueda, es decir, el conjunto de nodos para seleccionar a continuación.
Seleccione el nodo para que (node_weight + maximum_edge_weight) se maximice.
Elimine el nodo del gráfico y S. Agregue los "hijos" del nodo a S.
Si el gráfico no está vacío, vaya al paso 1.
Detener.

La idea es atravesar esos subgrafos que darán la mayor ganancia posible primero, para poder soportar el costo de los subgrafos de peso negativo más tarde.

chazisop
fuente

Ordenamiento topológico positivo

Respuestas: