Was ist die Intuition dafür, warum das Problem mit dem längsten Pfad keine optimale Unterstruktur hat?

9

Ich habe etwas über die längsten Pfade gelernt und bin auf die Tatsache gestoßen, dass die längsten Pfade in allgemeinen Graphen durch dynamische Programmierung nicht lösbar sind, weil das Problem keine optimale Unterstruktur aufweist (was meiner Meinung nach die Aussage, dass die längsten einfachen Pfade in allgemeinen Graphen korrigiert werden müssen, nicht durch lösbar ist dynamische Programmierung).

Wenn wir davon ausgehen, dass sie einfach (aus irgendeinem Grund ist dies erforderlich, was ich noch nicht schätze) und am längsten sein müssen, ist es einfach, ein Gegenbeispiel zu erstellen. Betrachten Sie den quadratischen Graphen mit 4 Knoten A → B → C → D → A.

Ein längster Weg von A nach D ist eindeutig A → B → CD. Der längste Weg von B nach C ist jedoch nicht Teil des längsten Weges von A nach D, da der längste Weg von B nach C B → A → D → C ist, was eindeutig nicht mit dem Weg B → C (der) identisch ist in diesem Fall ist in der Tat ein kürzester Weg!).

Dies scheint nur zu funktionieren, weil die Pfade einfach sein müssen. Muss man davon ausgehen, dass die Wege einfach sein müssen , um zu beweisen, dass keine optimale Unterstruktur vorhanden ist?

Ich denke, dass das Gegenbeispiel ein guter Beweis sein sollte (was ich nicht leugne), ich finde das Gegenbeispiel überhaupt nicht sehr aufschlussreich. Ich verstehe, warum es den Punkt beweist, dass es keine optimale Unterstruktur zulässt, aber es gibt mir kein wirkliches Verständnis oder keine Intuition, warum es offensichtlich sein sollte, dass es keine optimale Unterstruktur mit dem längsten Pfad geben sollte . Warum funktioniert beispielsweise ein Argument zum Ausschneiden und Einfügen nicht? Wenn der Unterpfad nicht am längsten ist, bleiben Sie einfach auf einem längeren Pfad! Es klingt sehr verlockend, ich meine, wenn wir etwas länger einbauen, sollte es natürlich länger werden ... aber das ist aus irgendeinem Grund falsch . Beweist das Beispiel tatsächlich, dass DP niemals kannLängste (einfache?) Wege effizient lösen? Ich benötige keinen allgemeinen Beweis dafür, dass es nicht in P ist (da dies möglicherweise eine P vs NP-Lösung erfordert ). Ich bin gerade nach einem Beweis dafür , dass seine nicht auflösbar durch DP (oder zumindest sehr starke Hinweise darauf , dass DP kann nie dieses längsten Wege Problem lösen oder dass das Problem nicht nicht hat optimalen Unterbau).

Ich habe definitiv in Wikipedia gesehen, dass das Problem NP-Hard sein sollte, was bedeutet, dass es wahrscheinlich keinen schnellen Algorithmus gibt. Ich bin mir nicht sicher, ob dies die einzige Art von Beweis / Intuition ist, die vorhanden ist, um sicherzustellen, dass eine optimale Unterstruktur offensichtlich fehlt (oder wenn sie nicht fehlt, dass sie nicht verwendet werden kann, um das Problem schneller zu machen). Ist dies der einzige Weg zu zeigen, dass es mit einem schnellen dynamischen Programm nicht lösbar sein sollte ?

Ist der Grund, den wir brauchen, einfachNur weil das Problem trivial / uninteressant wird, wenn wir diese Anforderung nicht stellen. Mit anderen Worten, wenn es einen Zyklus gibt, hat man das Problem des längsten Pfades zu allen Knoten gelöst, die von diesem Zyklus aus erreichbar sind (indem man einen Pfad zu diesem Zyklus findet). Für die Knoten, für die kein Zyklus erreichbar ist, haben wir einen azyklischen Graphen, der durch DP lösbar ist (wenn die Gewichte positiv sind?). Wenn es Zyklen gibt, haben wir die Dinge automatisch auf eine optimale Unterstruktur gebracht (glaube ich), da jeder längste Pfad nur aus dem längsten Pfad besteht, der zwei Fälle abdeckt: 1 die Pfade durch den Zyklus oder 2 die Pfade durch die DAG beide enthalten eine optimale Unterkonstruktion. Das Problem ist also trivial geworden, ohne dass einfache Pfade erforderlich sind? Oder fehlt mir etwas oder gibt es bessere Erklärungen, warum einfache Pfade erforderlich sind? Tut nicht 'allgemeine längste Pfade sind von DP lösbar?

Ich bin mir auch nicht 100% sicher, welche Anforderungen erforderlich sind, um sicherzustellen, dass DP nicht verwendet werden kann. Ist es notwendig, negative Kantengewichte, positive, ungewichtete, gerichtete, ungerichtete ... was sind die Anforderungen?

algorithms graphs optimization dynamic-programming Charlie Parker
quelle

2

"ist durch dynamische Programmierung nicht lösbar, weil dem Problem eine optimale Unterstruktur fehlte (was meiner Meinung nach die Anweisung auf die längsten einfachen Pfade in allgemeinen Graphen korrigieren muss, ist durch dynamische Programmierung nicht lösbar)." - weder "optimale Unterstruktur" noch "dynamische Programmierung" "sind sinnvolle Begriffe im formalen Sinne; es gibt einfach keine allgemein vereinbarten formalen Definitionen für sie. Siehe auch hier und hier . Das heißt, der von Ihnen angeforderte Beweis existiert nicht.

Raphael

11

$O(n!)$ $\tilde{O}(2^n)$

$G=(V,E)$ $s,t \in V$ $A \subseteq V \setminus \{s,t\}$ $G$ $s$ $t$ $A$

$\ell(s,t,A)$

\begin{aligned} ℓ (s, t, EIN) = 1 + max_{\begin{matrix} x \notin EIN \cup {s}} :: \\ (s, x) \in E. \end{matrix}} ℓ (x, t, EIN \cup {s}}) (s \neq t), \\ ℓ (t, t, EIN) = 0. \end{aligned}

$\begin{align*} &\ell(s,t,A) = 1 + \max_{\substack{x \notin A \cup \{s\}: \\ (s,x) \in E}} \ell(x,t,A \cup \{s\}) \qquad (s \neq t), \\ &\ell(t,t,A) = 0. \end{align*}$

s

$s$

t

$t$

A

$A$

ℓ (s, t, A) = - \infty

$\ell(s,t,A) = -\infty$

$\tilde{O}(2^n)$

Obwohl es hier eine optimale Unterstruktur gibt, gibt es zu viele Parameter, um sie im Auge zu behalten, und dies macht das Problem unlösbar.

Yuval Filmus
quelle

Was bedeutet die Tilde auf dem O? Ich vermute, es bedeutet, dass Sie Polynombegriffe in der großen O-Notation verstecken.

Charlie Parker

@CharlieParker Das stimmt.

Yuval Filmus

Wie erzwingen Sie einfache Pfade in dieser Formulierung?

Joost

@Joost Die Wiederholung erzwingt dies bereits.

Yuval Filmus

x

$x$

s

$s$

A

$A$

3

Erstens ist der längste einfache Pfad NP-hart und daran besteht kein Zweifel (da sich der Hamilton-Pfad darauf reduziert).

Zweitens, wenn Sie die nicht einfachen Pfade betrachten, ist das Problem nicht sehr sinnvoll, da der nicht einfache Pfad mehr als einmal über eine Kante / einen Scheitelpunkt verläuft und somit eine Schleife aufweist. Aufgrund einer Schleife im Pfad ist der längste nicht einfache Pfad unendlich .

Orezvani
quelle

1

Ich habe in der letzten Stunde darüber nachgedacht und bin zu folgenden Schlussfolgerungen gekommen:

i) Der längste Pfad in einem Graphen ohne Zyklen hat eine optimale Unterstruktur, ebenso wie der kürzeste Pfad.

ii) Der längste Weg ohne positive Zyklen hat eine optimale Unterstruktur, ebenso wie der kürzeste Weg ohne negative Zyklen.

iii) Der längste Weg mit positiven Zyklen und der kürzeste Weg mit negativen Zyklen existieren nicht, da wir den Zyklus unendlich durchlaufen können. Wir betrachten also einfache Wege.

iv) Der längste einfache Weg mit positiven Zyklen und der kürzeste einfache Weg mit negativen Zyklen ist NP Hard.

DP löst (i) in O (V + E). Bellman-Ford löst (ii) in O (VE) und Djisktra hilft in bestimmten Unterfällen von (ii).

Die Literatur ist zu diesem Thema verwirrend, wenn der längste Weg nur der kürzeste Weg mit negierten Gewichten ist und umgekehrt. Ich sehe keinen Grund, pauschale Aussagen zu machen, wie der längste Pfad keine optimale Unterstruktur hat, aber der kürzeste Pfad usw.

Nitesh Bharadwaj Gundavarapu
quelle

Was ist die Intuition dafür, warum das Problem mit dem längsten Pfad keine optimale Unterstruktur hat?

Antworten: