Quelle est l'intuition pour laquelle le problème du chemin le plus long n'a pas de sous-structure optimale?

J'apprenais les chemins les plus longs et je suis tombé sur le fait que les chemins les plus longs dans les graphiques généraux ne sont pas résolubles par programmation dynamique parce que le problème manquait de sous-structure optimale (dont je pense que l'énoncé doit être corrigé pour les chemins simples les plus longs sur les graphiques généraux n'est pas résolu par programmation dynamique).

Si nous supposons qu'ils doivent être simples (pour une raison quelconque, cela est nécessaire que je n'apprécie pas encore) et les plus longs, alors il est facile de créer un contre-exemple. Considérons le graphique carré à 4 nœuds A → B → C → D → A.

Le chemin le plus long de A à D est clairement A → B → CD. Mais le plus long chemin de B à C ne fait pas partie du plus long chemin de A à D parce que le plus long chemin de B à C est B → A → D → C qui n'est clairement pas le même que le chemin B → C (qui dans ce cas c'est en fait un chemin le plus court!).

Cela semble fonctionner uniquement parce que nous avions besoin que les chemins soient simples. Faut-il supposer que les chemins doivent être simples pour que l'on prouve qu'il n'y a pas de sous-structure optimale ?

Je pense que le contre-exemple devrait être une bonne preuve / preuve (ce que je ne nie pas), je ne trouve tout simplement pas le contre-exemple très éclairant du tout. Je vois pourquoi cela prouve le fait qu'il ne permet pas une sous-structure optimale mais cela ne me fournit pas une réelle compréhension ou intuition pourquoi il devrait être évident qu'il ne devrait pas y avoir de sous-structure optimale sur le plus long chemin. Comme par exemple, pourquoi un argument couper-coller ne fonctionne-t-il pas? Si le sous-chemin n'est pas le plus long, alors restez sur un chemin plus long! Cela semble très tentant, je veux dire, si nous mettons en place quelque chose de plus long, bien sûr, cela devrait s'allonger ... cependant, c'est pour une raison erronée . L'exemple prouve-t-il réellement que DP ne peut jamaisrésoudre efficacement les chemins les plus longs (simples?)? Je n'ai pas besoin d'une preuve générale que ce n'est pas en P (car cela pourrait demander une solution P vs NP). Je suis juste après une preuve que ce n'est pas résoluble par DP (ou au moins une preuve très forte que DP ne peut jamais résoudre ce problème de chemins les plus longs ou que le problème n'a pas de sous-structure optimale).

J'ai définitivement vu dans wikipedia que le problème devrait être NP-Hard, ce qui signifie qu'il n'y a probablement pas d'algorithme rapide. Je ne sais pas si c'est le seul type de preuve / intuition qui existe pour fournir que la sous-structure optimale devrait évidemment faire défaut (ou si elle ne fait pas défaut, qu'elle ne peut pas être utilisée pour accélérer le problème). Est-ce le seul moyen de montrer qu'il ne devrait pas être résoluble par un programme dynamique rapide?

Est-ce la raison pour laquelle nous demandons simplejuste parce que si nous ne plaçons pas cette exigence, le problème devient trivial / sans intérêt? En d'autres termes, s'il y a un cycle, alors on a résolu le problème de chemin le plus long à tous les nœuds accessibles à partir de ce cycle (en trouvant n'importe quel chemin vers ce cycle). Pour les nœuds qui n'ont pas de cycle accessible, nous avons un graphe acyclique, qui peut être résolu par DP (si les poids sont positifs?). De plus, s'il y a des cycles, nous avons automatiquement fait que les choses aient une sous-structure optimale (je pense) parce que tout chemin le plus long est simplement composé du chemin le plus long qui couvre deux cas, 1 les chemins à travers le cycle ou 2 les chemins à travers le DAG, qui les deux contiennent une sous-structure optimale. Le problème est donc devenu trivial sans l'exigence de chemins simples? Ou manque-t-il quelque chose ou existe-t-il de meilleures explications pour lesquelles des chemins simples sont nécessaires? N'est pasles chemins les plus longs sont-ils résolubles par DP?

Je ne suis pas sûr à 100% des exigences nécessaires pour garantir que le DP ne peut pas être utilisé. Faut-il des poids de bord négatifs, positifs, non pondérés, dirigés, non dirigés ... quelles sont les exigences?

Le problème de chemin le plus long a une sous-structure optimale, et cela peut être utilisé pour améliorer le trivial $O(n!)$ algorithme à un $\tilde{O}(2^n)$algorithme. Nous devons d'abord généraliser le problème:

Chemin le plus long généralisé: étant donné un graphique $G=(V,E)$, deux sommets $s,t \in V$et un ensemble de sommets $A \subseteq V \setminus \{s,t\}$, trouvez le chemin le plus long $G$ de $s$ à $t$ en évitant les sommets $A$.

Indiquant la solution à ce problème par $\ell(s,t,A)$ (le graphique est compris), on a la récurrence

Vous pouvez résoudre cette récurrence en utilisant la programmation dynamique dans le temps .$\tilde{O}(2^n)$

Bien qu'il y ait une sous-structure optimale ici, il y a trop de paramètres à suivre, et c'est ce qui rend le problème insoluble.

Tout d'abord, le chemin simple le plus long est NP-difficile et cela ne fait aucun doute (car le chemin hamiltonien se réduit à lui).

Deuxièmement, si vous considérez les chemins non simples, le problème n'a pas beaucoup de sens, car le chemin non simple passe plusieurs fois sur un bord / sommet, il a donc une boucle. Du fait de la présence d'une boucle dans le chemin, le plus long chemin non simple est infini .

J'ai pensé à la même chose au cours de la dernière heure et je suis arrivé aux conclusions suivantes:

i) Le chemin le plus long dans un graphe sans cycles a une sous-structure optimale, tout comme le chemin le plus court.

ii) Le chemin le plus long sans cycles positifs a une sous-structure optimale, tout comme le chemin le plus court sans cycles négatifs.

iii) Le chemin le plus long avec des cycles positifs et le chemin le plus court avec des cycles négatifs n'existent pas car nous pouvons parcourir le cycle à l'infini. Nous examinons donc des chemins simples.

iv) Le chemin simple le plus long avec des cycles positifs et le chemin simple le plus court avec les cycles négatifs est NP Hard.

DP résout (i) dans O (V + E). Bellman-Ford résout (ii) dans O (VE) et Djisktra aide dans certains sous-cas de (ii).

La littérature prête à confusion sur ce sujet lorsque le chemin le plus long est simplement le chemin le plus court avec des poids annulés et vice-versa. Je ne vois aucune raison de donner des instructions générales comme le chemin le plus long n'a pas de sous-structure optimale mais le chemin le plus court a etc.