Algoritmo exacto para el problema de etiquetado de bordes en DAG

Estoy implementando alguna parte del sistema que requiere ayuda. Por lo tanto, lo estoy enmarcando como un problema gráfico para que sea independiente del dominio.

Problema: se nos da un gráfico acíclico dirigido . Sin pérdida de generalidad, suponga que tiene exactamente un vértice fuente y exactamente un vértice sumidero ; dejar que denota el conjunto de todos los caminos dirigido desde a en . También se nos da un conjunto de vértices . El problema es asignar pesos enteros no negativos a los bordes de , por lo que dos caminos en tienen el mismo peso si y solo si contienen el mismo subconjunto de vértices en $G=(V,E)$ $G$ $s$ $t$ $P$ $s$ $t$ $G$ $R \subseteq V$ $G$ $P$ . (El peso de una ruta es la suma de los pesos de sus bordes). El rango de pesos de las rutas en debe ser lo más pequeño posible. $R$ $P$

Actualmente mi enfoque no parece eficiente; Solo estoy buscando algunas referencias a la literatura o algunas buenas ideas. Cualquier otra cosa también es apreciada.

Editar: ¿Hay una prueba de dureza para este problema? ¿La numeración compacta siempre existe?

ds.algorithms reference-request co.combinatorics graph-algorithms directed-acyclic-graph usuario5153
fuente

por favor aclare "El rango de pesos de las rutas en P debe ser óptimo". ¿Son los pesos solo enteros? ¿Se nos permiten pesos negativos? ¿Óptimo significa "un rango lo más pequeño posible" o significa algo más?

Artem Kaznatcheev

He editado la pregunta. Gracias por tu comentario. los pesos deben ser enteros no negativos y el rango debe ser lo más pequeño posible.

user5153

Una estrategia simple para llegar a una solución válida sería asignar una potencia diferente de dos a cada vértice v en R, usar ese número como el peso de todos los bordes entrantes a v, y asignar un peso cero a todos los bordes restantes. Obviamente, esto podría no ser óptimo, pero al menos da un límite superior en el rango necesario. ¿Alguna vez es una mejora hacer que diferentes bordes a través del mismo vértice en R tengan pesos diferentes entre sí, o puede simplificar el problema haciendo que los pesos vayan con vértices en lugar de bordes?

David Eppstein

Por cierto, la respuesta de DavidEppstein muestra que el peso total máximo de una ruta es

. Esto es estricto con las constantes. Como ejemplo, puede tomar el gráfico

O (2^{| R |})

$O(2^{|R|})$

G = (V, E)

$G = (V, E)$

V = [n] \cup {s, t}

$V = [n] \cup \{s, t\}$

. Deje también

. Hay

rutas diferentes en

, y dado que cada ruta tiene un peso entero no negativo, al menos uno necesita tener un peso de al menos

E = {(i, j) : i < j} \cup {(s, 1), (n, t), (s, t)}

$E = \{(i, j): i<j\} \cup \{(s, 1), (n, t), (s, t)\}$

R = [n]

$R = [n]$

2^{n}

$2^n$

R

$R$

2^{n} - 1

$2^n -1$

Sasho Nikolov

claro, quise decir apretado en el peor de los casos (en realidad escribí eso en la primera versión de este comentario que se perdió). pensé que sería bueno establecer primero algunos límites absolutos, ya que nadie ha abordado el problema de optimización todavía.

Sasho Nikolov

No he oído hablar de este problema exactamente en la literatura [tal vez alguien más lo ha hecho], sin embargo, como un "problema cercano", me parece que el árbol de expansión mínima tendría propiedades útiles para resolver su problema. por ejemplo, tal vez generar dos árboles de expansión mínima a partir del vértice de origen y el vértice de sincronización, y propagarlos hacia afuera hasta que se toquen, etc., podría resolver el problema o dar una respuesta cercana. antes de que alguien me diga sobre esto aquí, por favor entiendo que estoy extendiendo la idea de que el MST se genere a partir de un vértice dado [normalmente comienza desde el borde más corto en todo el gráfico]. si no funciona, sería curioso por la razón.

vzn
fuente

Lo sentimos, pero no veo la relevancia de esta respuesta a esta pregunta.

David Eppstein

tal vez tienes una mejor idea de lo que está hablando? ¿Tiene sentido para usted como se dijo?

vzn

Necesita asignar pesos a los bordes. ¿Cómo ayudaría el cálculo de un MST?

Nicholas Mancuso

ok al leerlo, y sin que nadie más propusiera una respuesta, parecía que el problema podría convertirse en dos partes: (1) asignar pesos basados en criterios / restricciones, (2) encontrar caminos más cortos basados en esos pesos. Parece que MST podría ser útil en (2). ¡o tal vez no! (por ejemplo, quizás 1/2 están estrechamente acoplados)

vzn

No. Los árboles de expansión mínima son solo para gráficos no dirigidos; Se dirige el gráfico de entrada. Además, los árboles de expansión mínima solo están relacionados superficialmente con los caminos más cortos.

Jeff

Algoritmo exacto para el problema de etiquetado de bordes en DAG

Respuestas: