Nombre maximum de points que deux chemins peuvent atteindre

Supposons que l'on nous donne une liste de points, dont les coordonnées et sont toutes non négatives. Supposons également qu'il n'y ait pas de points en double. On ne peut aller du point au point si et . La question est: étant donné ces points, quel est le nombre maximum de points que nous pouvons atteindre si nous sommes autorisés à tracer deux chemins qui relient des points en utilisant la règle ci-dessus? Les chemins doivent partir de l'origine et peuvent contenir des points répétés. n'est bien sûr pas inclus dans les points atteints.$n$$x$$y$$(x_i, y_i)$$(x_j, y_j)$$x_i \le x_j$$y_i \le y_j$$n$$(0, 0)$

Un exemple: donné $(2, 0), (2, 1), (1, 2), (0, 3), (1, 3), (2, 3), (3, 3), (2, 4), (1, 5), (1, 6)$ , la réponse est $8$ puisque nous pouvons prendre $(0, 0) \rightarrow (2, 0) \rightarrow (2, 1) \rightarrow (2, 3) \rightarrow (2, 4)$ et $(0, 0) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (1, 5) \rightarrow (1, 6)$ .

Si nous sommes autorisés à dessiner un seul chemin, je peux facilement résoudre la question par une programmation dynamique qui s'exécute en $O(n^2)$ . Je trie d'abord les points en diminuant $x_i+y_i$ . Soit $D[i]$ le nombre maximum de pièces que l'on peut ramasser des pièces $1$ à $i$ dans la liste triée. Alors $D[1] = 1$ et $D[i] = \max\limits_{1\le j < i, x_j \le x_i, y_j \le y_i} D[j] + 1$ . La réponse est alors simplement $\max\limits_{1\le i \le n} D[i] + 1$ .

Mais je ne peux pas trouver une relation de récurrence pour deux chemins. Si quelqu'un a une idée d'une telle relation de récurrence, je serais heureux d'entendre ce qu'ils sont.

Le problème, reformulé et généralisé: étant donné un ensemble fini équipé d'un ordre partiel , trouver les chaînes maximisant . La question concerne le cas où et .$S$ $\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$

Naïvement, on pourrait essayer de trouver la meilleure chaîne unique dans , où la meilleure est mesurée par le nombre de valeurs distinctes des composants de la chaîne. Malheureusement, un composant peut retracer les étapes de l'autre, par exemple, donc cette notion de meilleur n'a pas de sous-structure optimale.$S^2$

Au lieu de cela, nous recherchons des chaînes dans l'ensemble . En exigeant que les composants soient égaux ou incomparables, nous empêchons le retracement mais devons maintenant affirmer que la meilleure chaîne est conforme à la nouvelle exigence.$T := \{(x, y) \mid (x, y) \in S^2 \wedge x \nless y \wedge y \nless x\}$

Lemme 1 (pas de retracement). Soit une chaîne et définissez et . Pour tout , nous avons si et seulement si .$C \subseteq T$$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$

Preuve. La direction if est triviale. Dans la direction seulement si, pour tout , il existe de telle sorte que . Puisque est une chaîne, . Supposons symétriquement que , ce qui implique que . On sait par la définition de que , de sorte , et .$z \in C_1 \cap C_2$$x, y \in S$$(x, z), (z, y) \in C$$C$$(x, z) \le (z, y) \vee (z, y) \le (x, z)$$(x, z) \le (z, y)$$x \le z \le y$$T$$x \nless z \wedge z \nless y$$x = z = y$$(z, z) \in C$

Lemme 2 (existence de la meilleure chaîne restreinte). Pour toutes les chaînes , il existe une chaîne telle que and .$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$

Preuve (révisée). Nous donnons un algorithme pour construire . Pour plus de commodité, définir factionnaires tel que pour tous . Soit et .$C$$\bot, \top$$\bot < x < \top$$x \in S$$C_1' := C_1 \cup \{\top\}$$C_2' := C_2 \cup \{\top\}$

1. Initialisez et et . Un invariant est que .$C := \varnothing$$x := \bot$$y := \bot$$x \nless y \wedge y \nless x$

2. Soit le prochain élément de , c'est-à-dire . Soit l'élément suivant de , c'est-à-dire .$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. Si , définissez et passez à l'étape 9.$x' \nless y' \wedge y' \nless x'$$(x, y) := (x', y')$

4. Si , définissez et passez à l'étape 9.$y < x' < y'$$(x, y) := (x', x')$

5. Si , définissez et passez à l'étape 9. Notez que implique que .$y \nless x' < y'$$x := x'$$x < x' \wedge x \nless y$$x' \nless y$

6. Si , définissez et passez à l'étape 9.$x < y' < x'$$(x, y) := (y', y')$

7. Si , définissez et passez à l'étape 9. Notez que implique que .$x \nless y' < x'$$y := y'$$y < y' \wedge y \nless x$$y' \nless x$

8. Cette étape n'est jamais atteinte, car les conditions des étapes 3 à 7 sont exhaustives.

9. Si (de manière équivalente, ), définissez et passez à l'étape 2.$x \ne \top$$y \ne \top$$C := C \cup \{(x, y)\}$

Programme dynamique. Pour tout , calculez où si est vrai et si est faux. Par le lemme 1, il s'ensuit que les expressions entre crochets comptent correctement le nombre de nouveaux éléments. Par le lemme 2, la solution optimale au problème d'origine est trouvée.$(x, y) \in T$

Soit pour une liste triée de points.$P = p_1\dots p_n$

Après votre récurrence pour un chemin, la première chose à noter est que vous devez garder une trace des points qui ont été visités par les chemins; sinon vous ne pourrez pas compter correctement. La deuxième chose est que vous avez maintenant quatre possibilités pour chaque point: aucun chemin ne peut l'utiliser, l'un d'eux ou les deux. Nous devons donc trouver des combinaisons maximales pour les trois cas.

Formellement, soit avec la paire de (ensembles de) nœuds visités des deux chemins qui maximisent le nombre de points visités de la configuration d'entrée au ème, avec le premier composant la paire de chemins maximisante pour laquelle le premier utilise , le deuxième composant similaire pour le deuxième chemin et le troisième composant avec les deux chemins utilisant . est donné par la récurrence$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}$

avec

$\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$ similaire à l' extension et similaire à l' extension à la fois et .$R$$(\mathcal{L}' \times \mathcal{R}')_i$$L$$R$

Inutile de dire que ce n'est pas très agréable. En effet, le problème ne se prête pas très bien à la programmation dynamique: vous ne pouvez pas combiner de nombreuses solutions partielles car il n'y a pas de bon classement total sur les points, et vous ne pouvez pas ignorer les résultats intermédiaires pour la même raison.

Une meilleure vue du problème consiste à modéliser l'ensemble des points sous forme de graphique acyclique dirigé pondéré avec$G = (V, E, w)$

• $V = \{(0,0), p_1, \dots, p_n, (X,Y)\}$ avec , , et$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\}$ et
• $w(v_1,v_2) = \begin{cases} 0 &, v_2 = (X,Y) \\ 1 &, \text{ else}\end{cases}$ .

Notez que vous pouvez garder le graphique plus petit si vous supprimez des bords redondants, c'est-à-dire supprimer s'il y a un chemin , car prendre de tels "raccourcis" n'est jamais plus avantageux.$(v_1,v_2)$$(v_1,\dots,v_2)$

Pour un chemin, la solution est clairement la longueur du plus long chemin de à . Maintenant, si nous modifions sorte que toutes les arêtes menant aux points sur aient également le poids et calculent le chemin le plus long dans ce graphique modifié, nous obtenons un chemin sorte que et couvrent ensemble comme autant de points que deux chemins peuvent. Cela nous laisse avec un runtime dans (voir ici ).$P^*$$(0,0)$$(X,Y)$$w$$P^*$$0$$P^+$$P^*$$P^+$$O(|V| + |E|) \subseteq O(n^2)$