Exakter Algorithmus für Kantenbeschriftungsprobleme in der DAG

Ich implementiere einen Teil des Systems, für den Hilfe erforderlich ist. Ich gestalte es daher als Grafikproblem, um es domänenunabhängig zu machen.

Problem: Wir erhalten den gerichteten azyklischen Graphen . Ohne Einschränkung der Allgemeinheit wird angenommen, dass genau einen Quellenscheitelpunkt und genau einen Senkenscheitelpunkt ; lassen die Menge aller Pfade von gerichteten bezeichnen zu in . Wir sind auch eine Reihe von Eckpunkten gegeben . Das Problem besteht darin, den Kanten von nicht negative ganzzahlige Gewichte zuzuweisen , sodass zwei beliebige Pfade in genau dann dasselbe Gewicht haben, wenn sie dieselbe Teilmenge von Eckpunkten in enthalten $G=(V,E)$ $G$ $s$ $t$ $P$ $s$ $t$ $G$ $R \subseteq V$ $G$ $P$ . (Das Gewicht eines Pfades ist die Summe der Gewichte seiner Kanten.) Der Bereich der Gewichte von Pfaden in sollte so klein wie möglich sein. $R$ $P$

Derzeit scheint mein Ansatz nicht effizient zu sein. Ich bin nur auf der Suche nach Literaturhinweisen oder guten Einsichten. Alles andere wird ebenfalls geschätzt.

Edit: Gibt es einen Härtebeweis für dieses Problem? Existiert die Kompaktnummerierung immer?

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

Bitte erläutern Sie: "Der Wertebereich der Pfade in P sollte optimal sein." Sind Gewichte nur ganze Zahlen? Dürfen wir negative Gewichte? Bedeutet optimal "eine möglichst kleine Reichweite" oder etwas anderes?

Artem Kaznatcheev

Ich habe die Frage bearbeitet. vielen Dank für Ihren Kommentar. Die Gewichte sollten nicht negative ganze Zahlen sein und der Bereich sollte so klein wie möglich sein.

user5153

Eine einfache Strategie, um eine gültige Lösung zu finden, besteht darin, jedem Eckpunkt v in R eine andere Zweierpotenz zuzuweisen, diese Zahl als Gewichtung aller eingehenden Kanten für v zu verwenden und allen verbleibenden Kanten die Gewichtung Null zuzuweisen. Natürlich ist dies möglicherweise nicht optimal, aber es gibt zumindest eine Obergrenze für den benötigten Bereich. Ist es jemals eine Verbesserung, verschiedene Kanten durch denselben Scheitelpunkt in R mit unterschiedlichen Gewichten zu versehen, oder können Sie das Problem vereinfachen, indem Sie die Gewichte mit Scheitelpunkten anstatt mit Kanten kombinieren?

David Eppstein

BTW @ DavidEppsteins Antwort zeigt, dass das maximale Gesamtgewicht eines Pfades

. Dies ist eng mit Konstanten. Als Beispiel können Sie den Graphen

und

O (2^{| R |})

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

G = (V, E)

$G = (V, E)$

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

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

. Sei auch

. Es gibt

verschiedene Pfade auf

, und da jeder Pfad ein nicht negatives ganzzahliges Gewicht hat, muss mindestens einer ein Gewicht von mindestens

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

klar, ich meinte im schlimmsten fall tight (das habe ich eigentlich in der ersten version dieses kommentars geschrieben, die verloren gegangen ist). Ich dachte, es wäre gut, zuerst einige absolute Grenzen festzulegen, da sich noch niemand mit dem Optimierungsproblem befasst hat.

Sasho Nikolov

Ich habe nicht genau in der Literatur von diesem Problem gehört [vielleicht hat es jemand anderes], aber als "naheliegendes Problem" scheint mir der minimale Spannbaum nützliche Eigenschaften zu haben, um Ihr Problem zu lösen. Beispielsweise könnte das Erzeugen von zwei minimalen Spannbäumen ausgehend vom Quellscheitelpunkt und dem Synchronisierungsscheitelpunkt und deren Weitergabe nach außen, bis sie sich berühren, usw. das Problem lösen oder eine genaue Antwort geben. bevor mich hier jemand darauf anspricht, verstehe ich, dass ich die Idee des MST etwas erweitere, das ausgehend von einem gegebenen Scheitelpunkt erzeugt werden soll [normalerweise beginnt es mit der kürzesten Kante in der gesamten Grafik]. Wenn es nicht funktioniert, wäre ich neugierig auf den Grund.

vzn
quelle

Entschuldigung, aber ich sehe die Relevanz dieser Antwort auf diese Frage nicht.

David Eppstein

Vielleicht hast du eine bessere Idee, wovon er spricht? macht es für dich sinn wie gesagt

vzn

Er muss Kanten Gewichte zuweisen . Wie würde die Berechnung eines MST dazu beitragen?

Nicholas Mancuso

Ok, wenn Sie es lesen und niemand anderes eine Antwort vorschlägt, scheint es, als könnte das Problem in zwei Teile umgewandelt werden. (1) Weisen Sie Gewichte basierend auf Kriterien / Einschränkungen zu. Scheint, dass MST für (2) nützlich sein könnte. oder vielleicht nicht! (zB vielleicht 1/2 sind eng miteinander verbunden)

vzn

Nein. Die minimalen Spannweiten gelten nur für ungerichtete Diagramme. Der Eingabediagramm ist gerichtet. Darüber hinaus sind minimale Spannbäume nur oberflächlich mit kürzesten Wegen verbunden.

Jeffs

Exakter Algorithmus für Kantenbeschriftungsprobleme in der DAG

Antworten: