"Verwandte" des kürzesten Wegproblems

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,t$$s-t$

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.$s-t$

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.$s-t$

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.$s-t$

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.$s-t$

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.)$s$$t$$s-t$

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.$s-t$

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.

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.$\tilde{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.$\tilde{O}(|E|)$$|E|^2$$k$$k-1$

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 in$S$$Θ(n/\log n)$$\mathrm{P}^S$auch 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 mit$\tilde{O}(|E|)$$n$$s=v_0,v_1,...,t=v_n$$x_i$$i<n$$v_i$$v_{i+1}$$x_i$$¬x_i$. 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.