Maximale Anzahl von Punkten, die zwei Pfade erreichen können

Angenommen, wir erhalten eine Liste von Punkten, deren und y- Koordinaten alle nicht negativ sind. Angenommen, es gibt keine doppelten Punkte. Wir können nur von Punkt (x_i, y_i) zu Punkt (x_j, y_j) gehen, wenn x_i \ le x_j und y_i \ le y_j . Die Frage ist: Angesichts dieser n Punkte, wie viele Punkte können wir maximal erreichen, wenn wir nach der obigen Regel zwei Pfade zeichnen dürfen, die Punkte verbinden? Pfade müssen vom Ursprung ausgehen und können wiederholte Punkte enthalten. (0, 0) ist natürlich nicht in den erreichten Punkten enthalten.$n$$x$$y$$(x_i, y_i)$$(x_j, y_j)$$x_i \le x_j$$y_i \le y_j$$n$$(0, 0)$

Ein Beispiel: gegeben $(2, 0), (2, 1), (1, 2), (0, 3), (1, 3), (2, 3), (3, 3), (2, 4), (1, 5), (1, 6)$ lautet die Antwort $8$ da wir $(0, 0) \rightarrow (2, 0) \rightarrow (2, 1) \rightarrow (2, 3) \rightarrow (2, 4)$ und $(0, 0) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (1, 5) \rightarrow (1, 6)$ .

Wenn wir nur einen Pfad zeichnen dürfen, kann ich die Frage leicht durch dynamische Programmierung lösen, die in $O(n^2)$ . Ich sortiere zuerst die Punkte, indem ich x_i + y_i verkleinere $x_i+y_i$. Sei $D[i]$ die maximale Anzahl von Münzen, die man von den Münzen $1$ bis $i$ in der sortierten Liste aufnehmen kann. Dann ist $D[1] = 1$ und $D[i] = \max\limits_{1\le j < i, x_j \le x_i, y_j \le y_i} D[j] + 1$ . Die Antwort lautet dann nur $\max\limits_{1\le i \le n} D[i] + 1$ .

Aber ich kann keine Wiederholungsrelation für zwei Pfade finden. Wenn jemand eine Vorstellung von einer solchen Wiederholungsbeziehung hat, würde ich mich freuen zu hören, was sie sind.

Das Problem, angepasst und verallgemeinerte: Bei einem gegebenen endlicher Satz , ausgestattet mit einer Teilordnung , Ketten finden Maximizing . Die Frage bezieht sich auf den Fall, in dem und .$S$ C 1 , C 2 ⊆ S | C 1 ∪ C 2 | S ⊆ R 2 + ( x , y ) ≤ ( z , w ) ⟺ x ≤ z ∧ y ≤ $\le$$C_1, C_2 \subseteq S$$\lvert C_1 \cup C_2 \rvert$$S \subseteq \mathbb R_+^2$$(x, y) \le (z, w) \Longleftrightarrow x \le z \wedge y \le w$

Naiv könnte man versuchen, die beste Kette in , wobei die beste daran gemessen wird, wie viele unterschiedliche Werte die Komponenten der Kette haben. Leider kann eine Komponente die Schritte der anderen zurückverfolgen, z. B. daher hat dieser Begriff des Besten keine optimale Unterstruktur.( ( 0 , 0 ) , ( 0 , 0 ) ) < ( ( 1 , 0 ) , ( 0 , 0 ) ) < ( ( 2 , 0 ) , ( 0 , 0 ) ) < ( ( 2 , 0 )) , ( 1 , 0 ) )$S^2$

Stattdessen suchen wir nach Ketten in der Menge . Indem wir verlangen, dass die Komponenten gleich oder unvergleichlich sind, verhindern wir das Zurückverfolgen, müssen aber jetzt argumentieren, dass eine der besten Ketten der neuen Anforderung entspricht.$T := \{(x, y) \mid (x, y) \in S^2 \wedge x \nless y \wedge y \nless x\}$

Lemma 1 (keine Rückverfolgung). Sei eine Kette und definiere und . Für alle , haben wir , wenn und nur wenn .C 1 : = { x ∣ ( x , $C \subseteq T$C 2 : = { y ∣ ( x , y ) ∈ C } z ∈ S z ∈ C 1 ∩ C 2 ( z , z ) ∈ $C_1 := \{x \mid (x, y) \in C\}$$C_2 := \{y \mid (x, y) \in C\}$$z \in S$$z \in C_1 \cap C_2$$(z, z) \in C$

Beweis. Die if-Richtung ist trivial. In der einzigen Richtung , wenn, für alle existieren derart , daß . Da eine Kette ist, ist . Nehmen Sie symmetrisch an, dass , was impliziert, dass . Wir wissen von der Definition von , die , also , und . x , y ≤ S ( x , z ) , ( $z \in C_1 \cap C_2$$x, y \in S$C ( x , z ) ≤ ( z , y ) ∨ ( z , y ) ≤ ( x , z ) ( x , z ) ≤ ( z , y ) $(x, z), (z, y) \in C$$C$$(x, z) \le (z, y) \vee (z, y) \le (x, z)$$(x, z) \le (z, y)$T x ≮ z ∧ z ≮ y x = z = y ( z , z ) ∈ $x \le z \le y$$T$$x \nless z \wedge z \nless y$$x = z = y$$(z, z) \in C$

Lemma 2 (Existenz einer eingeschränkten besten Kette). Für alle Ketten existiert eine Kette so dass und .C ⊆ T C 1 ⊆ { x ∣ ( x , y ) ∈ C } ⊆ C 1 ∪ C 2 C 2 ⊆ { y ∣ ( x , y ) ∈ C } ⊆ C 1 ∪ C $C_1, C_2 \subseteq S$$C \subseteq T$$C_1 \subseteq \{x \mid (x, y) \in C\} \subseteq C_1 \cup C_2$$C_2 \subseteq \{y \mid (x, y) \in C\} \subseteq C_1 \cup C_2$

Beweis (überarbeitet). Wir geben einen Algorithmus zu konstruieren . Definieren Sie der Einfachheit Sentinels so, dass für alle . Sei und .⊥ , ⊤ x < x < ⊤ x ∈ S C ′ 1 : = C 1 ∪ { ⊤ } C ′ 2 : = C 2 ∪ { ⊤ $C$$\bot, \top$$\bot < x < \top$$x \in S$$C_1' := C_1 \cup \{\top\}$$C_2' := C_2 \cup \{\top\}$

1. Initialisieren Sie und und . Eine Invariante ist, dass .x : = ⊥ y : = ⊥ x ≮ y ∧ y ≮ $C := \varnothing$$x := \bot$$y := \bot$$x \nless y \wedge y \nless x$

2. Sei das nächste Element von , . Sei das nächste Element von , .C 1 x ' : = inf { z ≤ z ≤ C ' 1 ≤ x < z } y ' C 2 y ' : = inf { w ≤ w ≤ C ' 2 ≤ y < w $x'$$C_1$$x' := \inf \{z \mid z \in C_1' \wedge x < z\}$$y'$$C_2$$y' := \inf \{w \mid w \in C_2' \wedge y < w\}$

3. Wenn , setze und gehe zu Schritt 9.$x' \nless y' \wedge y' \nless x'$$(x, y) := (x', y')$

4. Wenn , setzen Sie und fahren Sie mit Schritt 9 fort.$y < x' < y'$$(x, y) := (x', x')$

5. Wenn , setzen Sie und fahren Sie mit Schritt 9 fort. Beachten Sie, dass impliziert, dass .$y \nless x' < y'$$x := x'$$x < x' \wedge x \nless y$$x' \nless y$

6. Wenn , setzen Sie und fahren Sie mit Schritt 9 fort.$x < y' < x'$$(x, y) := (y', y')$

7. Wenn , setzen Sie und fahren Sie mit Schritt 9 fort. Beachten Sie, dass impliziert, dass .$x \nless y' < x'$$y := y'$$y < y' \wedge y \nless x$$y' \nless x$

8. Dieser Schritt wird nie erreicht, da die Bedingungen für die Schritte 3 bis 7 vollständig sind.

9. Wenn (äquivalent ), setzen Sie und fahren Sie mit Schritt 2 fort.$x \ne \top$$y \ne \top$$C := C \cup \{(x, y)\}$

Dynamisches Programm. Berechnen Sie für alle wobei wenn wahr ist, und wenn falsch ist. Aus Lemma 1 folgt, dass die Klammerausdrücke die Anzahl der neuen Elemente korrekt zählen. Mit Lemma 2 wird die optimale Lösung für das ursprüngliche Problem gefunden.$(x, y) \in T$

Lassen Sie zur sortierten Liste von Punkten.$P = p_1\dots p_n$

Nach Ihrer Wiederholung für einen Pfad müssen Sie zunächst feststellen, welche Punkte von den Pfaden besucht wurden. Andernfalls können Sie nicht richtig zählen. Die zweite Sache ist, dass Sie jetzt vier Möglichkeiten für jeden Punkt haben: Keiner der Pfade darf ihn verwenden, einer von ihnen oder beide. Wir müssen also für alle drei Fälle maximale Kombinationen finden.

Formal sei mit dem Paar von (Sätzen von) besuchten Knoten der beiden Pfade, die die Anzahl der besuchten Punkte von der Eingabe bis zur ten maximieren, wobei die erste Komponente das maximierende , für das die erste , die zweite Komponente für den zweiten Pfad ähnlich ist und die dritte Komponente mit beiden Pfade mit . ist durch die Wiederholung gegeben$d : [0\dots n] \to (2^{[n]} \times 2^{[n]})^3$$d(i)$$i$$p_i$$p_i$$d$

$\quad \displaystyle \begin{align} d(0) &= ((\emptyset, \emptyset),(\emptyset, \emptyset),(\emptyset, \emptyset)) \\ d(i) &= (\ \arg\max_{(L,R) \in (\mathcal{L}' \times \mathcal{R})_i} |L \cup R|, \\ &\phantom{= (\ } \arg\max_{(L,R) \in (\mathcal{L} \times \mathcal{R}')_i} |L \cup R|, \\ &\phantom{= (\ } \arg\max_{(L,R) \in (\mathcal{L}' \times \mathcal{R}')_i} |L \cup R| \ ) \\ \end{align}$

mit

$\quad \displaystyle (\mathcal{L}' \times \mathcal{R})_i = \left\{ (L \cup \{i\}, R) \mid (L,R) \in \bigcup_{j=0}^{i-1} d(j), x_i \geq \max_{j \in L} x_j, y_i \geq \max_{j \in L} y_j \right\}$ ,

$(\mathcal{L}' \times \mathcal{R})_i$ ähnlich mit erstrecken und ähnlich mit beiden erstreckenden und .$R$$(\mathcal{L}' \times \mathcal{R}')_i$$L$$R$

Das ist natürlich nicht sehr schön. Dies liegt daran, dass sich das Problem nicht sehr gut für die dynamische Programmierung eignet: Sie können nicht viele Teillösungen kombinieren, da es keine schöne Gesamtreihenfolge für die Punkte gibt und Sie Zwischenergebnisse aus demselben Grund nicht verwerfen können.

Eine schönere Sicht auf das Problem besteht darin, die Menge der Punkte als gewichteten gerichteten azyklischen Graphen mit zu modellieren$G = (V, E, w)$

• $V = \{(0,0), p_1, \dots, p_n, (X,Y)\}$ mit , und$X = \max x_i$$Y = \max y_i$
• $E = \{ ((x_1, y_1),(x_2,y_2)) \in V^2 \mid x_i \leq x_j, y_i \leq y_j\}$ und
• $w(v_1,v_2) = \begin{cases} 0 &, v_2 = (X,Y) \\ 1 &, \text{ else}\end{cases}$ .

Beachten Sie, dass Sie das Diagramm kleiner halten können, wenn Sie redundante Kanten entfernen entfernen wenn ein Pfad vorhanden ist , da die Verwendung solcher "Verknüpfungen" niemals besser vorteilhaft ist.$(v_1,v_2)$$(v_1,\dots,v_2)$

Für einen Pfad ist die Lösung eindeutig die Länge des längsten Pfades von bis . Wenn wir nun so ändern , dass alle Kanten, die zu Punkten auf auch das Gewicht und den längsten Pfad in diesem modifizierten Graphen berechnen, erhalten wir einen Pfad so dass und zusammen as abdecken viele Punkte wie zwei Pfade können. Dies lässt uns eine Laufzeit in (siehe hier ).$P^*$$(0,0)$$(X,Y)$$w$$P^*$$0$$P^+$$P^*$$P^+$$O(|V| + |E|) \subseteq O(n^2)$