Algorithme exact pour le problème d'étiquetage des bords dans DAG

J'implémente un système dont une partie nécessite de l'aide. Je le conçois donc comme un problème de graphe pour le rendre indépendant du domaine.

Problème: On nous donne un graphe acyclique dirigé . Sans perte de généralité, supposons que a exactement un sommet source et exactement un sommet puits ; laisser représentent l'ensemble de tous les chemins orientés de à dans . Nous sommes également donné un ensemble de sommets . Le problème est d'attribuer des poids entiers non négatifs aux bords de , de sorte que deux chemins dans ont le même poids si et seulement s'ils contiennent le même sous-ensemble de sommets dans $G=(V,E)$ $G$ $s$ $t$ $P$ $s$ $t$ $G$ $R \subseteq V$ $G$ $P$ . (Le poids d'un chemin est la somme des poids de ses bords.) La plage de poids des chemins dans doit être aussi petite que possible. $R$ $P$

Actuellement, mon approche ne semble pas efficace; Je cherche juste des références à la littérature ou de bonnes idées. Tout autre chose est également apprécié.

Edit: Existe - t-il une preuve de dureté pour ce problème? La numérotation compacte existe-t-elle toujours?

ds.algorithms reference-request co.combinatorics graph-algorithms directed-acyclic-graph user5153
la source

veuillez préciser "La plage de poids des chemins dans P doit être optimale." Les poids ne sont-ils que des entiers? Sommes-nous autorisés à pondérer négativement? Est-ce que optimal signifie "une plage aussi petite que possible" ou signifie-t-il autre chose?

Artem Kaznatcheev

j'ai édité la question. Merci pour votre commentaire. les poids doivent être des entiers non négatifs et la plage doit être aussi petite que possible.

user5153

Une stratégie simple pour trouver une solution valide serait d'attribuer une puissance différente de deux à chaque sommet v dans R, d'utiliser ce nombre comme poids de tous les bords entrants à v, et d'affecter le poids zéro à tous les bords restants. Évidemment, cela peut ne pas être optimal, mais cela donne au moins une limite supérieure sur la plage nécessaire. Est-ce jamais une amélioration de faire en sorte que différents bords passant par le même sommet dans R aient des poids différents les uns des autres, ou pouvez-vous simplifier le problème en faisant en sorte que les poids correspondent aux sommets plutôt qu'aux bords?

David Eppstein

La réponse de BTW @ DavidEppstein montre que le poids total maximum d'un chemin est

. C'est serré aux constantes. À titre d'exemple, vous pouvez prendre le graphique

O (2^{| R |})

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

G = (V, E)

$G = (V, E)$

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

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

. Soit également

. Il y a

chemins différents sur

, et comme chaque chemin a un poids entier non négatif, au moins un doit avoir un poids d'au moins

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

bien sûr, je voulais dire serré dans le pire des cas (j'ai en fait écrit cela dans la première version de ce commentaire qui s'est perdu). a pensé qu'il serait bon de fixer d'abord quelques limites absolues, car personne n'a encore abordé le problème d'optimisation.

Sasho Nikolov

Je n'ai pas entendu parler de ce problème exactement dans la littérature [peut-être que quelqu'un d'autre en a], mais en tant que "problème proche", il me semble que l' arbre couvrant minimum aurait des propriétés utiles pour résoudre votre problème. par exemple, la génération de deux arbres couvrant au minimum à partir du sommet source et du sommet de synchronisation, et leur propagation vers l'extérieur jusqu'à ce qu'ils se touchent, etc. pourrait résoudre le problème ou donner une réponse proche. avant que quelqu'un ne me touche ici, veuillez comprendre que j'étends quelque peu l'idée du MST à générer à partir d'un sommet donné [normalement, il part du bord le plus court de tout le graphique]. si cela ne fonctionne pas, je serais curieux de savoir pourquoi.

vzn
la source

Désolé, mais je ne vois pas la pertinence de cette réponse à cette question.

David Eppstein

peut-être avez-vous une meilleure idée de ce dont il parle? est-ce que cela a du sens pour vous comme indiqué?

vzn

Il doit attribuer des poids aux bords. Comment le calcul d'un MST aiderait-il cela?

Nicholas Mancuso

ok à la lecture, et avec personne d'autre ne proposant une réponse, il semblait que le problème pourrait être converti en deux parties - (1) attribuer des poids en fonction de critères / restrictions, (2) trouver les chemins les plus courts en fonction de ces poids. semble que MST pourrait être utile sur (2). ou peut être pas! (par exemple, peut-être 1/2 sont étroitement couplés)

vzn

Non. Les arbres s'étendant sur un minimum sont uniquement destinés aux graphiques non orientés; le graphe d'entrée est dirigé. De plus, les arbres s'étendant sur un minimum ne sont que superficiellement liés aux chemins les plus courts.

Jeffε

Algorithme exact pour le problème d'étiquetage des bords dans DAG

Réponses: