"Verwandte" des kürzesten Wegproblems

10

Betrachten Sie einen verbundenen ungerichteten Graphen mit nicht negativen Kantengewichten und zwei unterschiedlichen Eckpunkten . Im Folgenden sind einige Pfadprobleme aufgeführt, die alle die folgende Form haben: Suchen Sie einen Pfad, sodass eine Funktion der Kantengewichte auf dem Pfad minimal ist. In diesem Sinne sind sie alle "Verwandte" des Problems des kürzesten Weges; in letzterem ist die Funktion einfach die Summe.s,tst

Hinweis: Wir suchen nach einfachen Pfaden, dh ohne wiederholte Eckpunkte. Da ich in der Literatur keine Standardnamen für diese Probleme gefunden habe, habe ich sie selbst benannt.

Pfad mit minimaler Gewichtslücke: Suchen Sie einen Pfad, sodass der Unterschied zwischen dem größten und dem kleinsten Kantengewicht auf dem Pfad minimal ist.st

Glattester Pfad: Suchen Sie einen Pfad, sodass die größte Schrittgröße auf dem Pfad minimal ist, wobei eine Schrittgröße der absolute Wert der Gewichtsdifferenz zwischen zwei aufeinanderfolgenden Kanten ist.st

Pfad mit minimaler Höhe: Definieren wir die Höhe eines Pfades durch die Summe der Schrittgrößen entlang des Pfades (siehe Definition der Schrittgröße oben). Suchen Sie einen Pfad mit minimaler Höhe.st

Pfad mit minimalem Primgewicht: Unter der Annahme, dass alle Kantengewichte positive ganze Zahlen sind, suchen Sie einen Pfad, sodass sein Gewicht eine Primzahl ist. Wenn es einen solchen Pfad gibt, suchen Sie einen mit dem kleinstmöglichen Primgewicht.st

Frage: Was ist über diese Pfadprobleme bekannt? (Und andere, die in einem ähnlichen Geist konzipiert werden könnten, indem eine andere Funktion der Gewichte angewendet wird.) Gibt es im Allgemeinen eine Anleitung, welche Funktionen der Kantengewichte in der Polynomzeit minimiert werden können und welche NP-hart sind?

Hinweis: Es ist zum Beispiel interessant, dass die Summe der Gewichte zwar leicht zu minimieren ist (dies ist das klassische Problem des kürzesten Pfades), die Minimierung des eng verwandten Durchschnitts der Gewichte auf dem Pfad jedoch NP-hart ist. (Weisen Sie allen auf und einfallenden Kanten das Gewicht 2 und allen anderen das Gewicht 1 zu. Dann ist ein minimaler durchschnittlicher Gewichtspfad der längste Pfad.)stst

Andras Farago
quelle

Antworten:

8

Hier ist eine Antwort auf das erste Problem:

Pfad mit minimaler Gewichtslücke: Suchen Sie einen Pfad, sodass der Unterschied zwischen dem größten und dem kleinsten Kantengewicht auf dem Pfad minimal ist.st

Eine Arbeit aus dem Jahr 1984 zeigt, dass wir immer dann, wenn wir die Machbarkeit (gibt es eine Lösung im ungewichteten Fall) für ein kombinatorisches Optimierungsproblem in der Polynomzeit entscheiden können, in der Polynomzeit eine Lösung finden können, die den Unterschied zwischen dem größten und dem kleinsten minimiert Kostenkoeffizient (im gewichteten Fall):

S. Martello, WR Pulleyblank, D. de Werra, P. Toth
Ausgewogene Optimierungsprobleme
Operations Research Letters 3, 1984, Seiten 275-278

Dies impliziert einen polynomiellen Zeitalgorithmus für Ihre Frage.

Gamow
quelle
1
Dies kann auch durch eine Brute-Force-Suche über alle Kantenpaare erfolgen, die das Maximum und das Minimum sowie deren Reihenfolge / Ausrichtung bilden können.
Yonatan N
3

Pfad mit minimaler Gewichtslücke : Dies kann in der Zeit gelöst werden , wobeiist die Anzahl der Kanten (vorausgesetzt, ist in der Anzahl der Eckpunkte mindestens linear). Sie können das Mindestgewicht durchlaufen und eine Binärsuche (oder effiziente Aktualisierungen) über das Höchstgewicht durchführen und die Konnektivität überprüfen. Ich weiß nicht, ob dies verbessert werden kann.O~(|E|2)|E||E|

Pfad mit minimaler Höhe (in Ihrer Terminologie): Dies kann in der Zeit gelöst werden . Sie können den Abstand (wie in der Summe der Schrittgrößen) zu allen Kanten analog zum gewöhnlichen gewichteten kürzesten Pfad berechnen. Beachten Sie, dass wiederholte Scheitelpunkte einen Pfad nicht verkürzen können. Um Scheitelpunkte mit hohem Grad effizient zu behandeln (wie bei der Vermeidung von Zeit ), können Sie einen Scheitelpunkt mit dem Grad in einen Pfad mit Scheitelpunkten mit aufteilen.O~(|E|)|E|2kk1

Pfad mit minimalem Primgewicht: Wenn die Gewichte binär sind, sollte dies NP-vollständig sein: Verwenden Sie Kanten mit Gewicht 1, mit Ausnahme der anfänglichen Kante mit hohem Gewicht, sodass nur ein Hamilton-Pfad Primgewicht hat (Gewicht ist die Summe der Kantengewichte). . (Eine Einschränkung ist, dass wir nicht bewiesen haben, dass ausreichend große Primzahlen (auch ohne minimale Primlücken) ohne Zufälligkeit schnell gefunden werden können.) Selbst für unäre Gewichte erwarte ich nicht, dass sie in P
vorliegen. Minimales Primgewicht erlaubt Selbst- Schnittpunkte: In P für unäre Gewichte. Wenn wir anstelle der Menge der Primzahlen eine Menge von Zufallszahlen mit der Dichte , dann ist sie mit der Wahrscheinlichkeit 1 inSΘ(n/logn)PSauch für binäre Gewichte: Es reicht aus, an jedem Punkt polynomiell viele (abhängig von ) niedrigste Pfadgewichte zu verfolgen . Bei Hauptgewichten müssen wir jedoch möglicherweise die Teiler der Gewichtsunterschiede diversifizieren (anstatt nur die niedrigsten Gewichte im Auge zu behalten), und es ist unklar, ob dies ausreicht.S

Glattester Weg: NP abgeschlossen. Wenn wir Selbstüberschneidungen zulassen würden, wäre dies in der Zeit lösbar , aber für die Version ohne Selbstüberschneidungen ist hier eine Reduzierung von 3-SAT mit Variablen. Haben Sie Eckpunkte plus einen Eckpunkt für jede Klausel. für jede Variable ( ) einen glatten Pfad (ggf. unter Verwendung zusätzlicher Eckpunkte) von zu , der alle Klauseln mit positivem Auftreten von durchläuft , und einen ähnlichen Pfad für Klauseln mitO~(|E|)ns=v0,v1,...,t=vnxii<nvivi+1xi¬xi. Setzen Sie das erste und letzte Kantengewicht jedes Pfads auf 1 (oder eine andere Konstante), wählen Sie jedoch ansonsten die Gewichte so, dass keine anderen Pfade glatt sind. Schließlich duplizieren Sie alle Klauselscheitelpunkte und die angrenzenden Kanten. Auf diese Weise kann jede Klausel höchstens zweimal besucht werden, was für 3-SAT ausreicht.

Dmytro Taranovsky
quelle
Ich denke, der glatteste Pfad ist aufgrund der folgenden Transformation in P. Sei ein Scheitelpunkt vom Grad . Ersetzen Sie durch eine Clique der Größe , sodass jede Kante , die ursprünglich neben jetzt an einem anderen Scheitelpunkt der Clique endet . Wenn zwei solche ursprünglichen Kanten sind, weisen Sie das Gewichtan den Rand in der Clique. Führen Sie diese Transformation für jeden Scheitelpunkt durch und weisen Sie den ursprünglichen Diagrammkanten eine Gewichtung von 0 zu. Dann ein Mindestgewichtvdvdevvee,f|w(e)w(f)|(ve,vf)vs,tstDer Pfad im neuen Diagramm ergibt einen glattesten Pfad im Original, nachdem die Transformation rückgängig gemacht wurde.
Andras Farago
@AndrasFarago Das Problem mit Ihrem Argument ist, dass einige einfache Pfade im erweiterten Diagramm wiederholte Scheitelpunkte im ursprünglichen Diagramm haben. Mir gefällt, dass das Problem mit dem glattesten Pfad täuschend einfach aussieht.
Dmytro Taranovsky
@ Dmytro Taranovsky Es scheint, Sie haben Recht, es kann tatsächlich vorkommen, dass wir nach der Rückkehr zum ursprünglichen Diagramm wiederholte Scheitelpunkte auf dem Pfad erhalten (aber keine wiederholten Kanten). Wenn jedoch jeder Grad im Originaldiagramm höchstens 3 beträgt, kann keine Wiederholung auftreten. Dies bedeutet, dass das Problem des glattesten Pfades zumindest für Diagramme mit maximalem Grad in P liegt . 3
Andras Farago
Entschuldigung, im transformierten Diagramm müssen wir einen Pfad mit dem kleinsten Maximalgewicht (das auch in P ist) finden, anstatt dem kleinsten Gesamtgewicht. Das Gesamtgewicht würde zu einem Pfad mit minimaler Höhe führen (in Diagrammen mit maximalem Grad , so dass wiederholte Scheitelpunkte ausgeschlossen sind). 3
Andras Farago