¿Cuál es la intuición de por qué el problema del camino más largo no tiene una subestructura óptima?

Estaba aprendiendo sobre las rutas más largas y encontré el hecho de que las rutas más largas en los gráficos generales no se pueden resolver mediante programación dinámica porque el problema carecía de una subestructura óptima (que creo que la afirmación debe corregirse a las rutas simples más largas en los gráficos generales no se puede resolver mediante programación dinámica).

Si suponemos que tienen que ser simples (por alguna razón, esto es un requisito que aún no aprecio) y más largo, entonces es fácil crear un contraejemplo. Considere la gráfica cuadrada con 4 nodos A → B → C → D → A.

Una ruta más larga de A a D es claramente A → B → CD. Pero el camino más largo de B a C no es parte del camino más largo de A a D porque el camino más largo de B a C es B → A → D → C, que claramente no es lo mismo que el camino B → C (que ¡en este caso es, de hecho, el camino más corto!).

Esto parece funcionar solo porque requerimos que los caminos sean simples. ¿Es necesario suponer que los caminos deben ser simples para que podamos demostrar que la subestructura óptima no está presente?

Creo que el contraejemplo debería ser una buena prueba / prueba (que no niego), simplemente no me parece muy esclarecedor el contraejemplo. Ya veo por qué se demuestra el punto de que no permite subestructura óptima pero deja de proporcionar una comprensión real o la intuición por qué debería ser obvio que no debe haber ningún más largo subestructura camino óptimo. Por ejemplo, ¿por qué no funciona un argumento de cortar y pegar? Si el subtrayecto no es el más largo, ¡entonces quédese en un camino más largo! Suena muy tentador, quiero decir, si ponemos en práctica algo más largo, entonces, por supuesto, debería alargarse ... aunque, por alguna razón, esto es incorrecto . ¿De hecho, el ejemplo demuestra que DP nunca puedeResolver caminos más largos (¿simples?) eficientemente? No necesito una prueba general de que no está en P (ya que eso podría estar pidiendo una solución P vs NP). Estoy justo después de una prueba de que su no resolubles por DP (o al menos muy fuerte evidencia de que la DP no puede resolver este problema caminos más largo o que el problema no no tienen subestructura óptima).

Definitivamente he visto en Wikipedia que el problema debería ser NP-Hard, lo que significa que probablemente no haya un algoritmo rápido. No estoy seguro de si ese es el único tipo de evidencia / intuición que existe para proporcionar que la subestructura óptima debería faltar obviamente (o si no es así, que no se puede usar para acelerar el problema). Es que la única manera de demostrar que debería no ser resuelta mediante un programa dinámico rápido?

Es la razón por la que necesitamos simplessolo porque si no establecemos ese requisito, ¿el problema se vuelve trivial / poco interesante? En otras palabras, si hay algún ciclo, entonces uno ha resuelto el problema de la ruta más larga a todos los nodos accesibles desde ese ciclo (encontrando cualquier ruta a ese ciclo). Para los nodos que no tienen ningún ciclo alcanzable, tenemos un gráfico acíclico, que puede ser resuelto por DP (¿si los pesos son positivos?). Además, si hay ciclos, automáticamente hemos hecho que las cosas tengan una subestructura óptima (creo) porque cualquier ruta más larga solo está compuesta por la ruta más larga que cubre dos casos, 1 las rutas a través del ciclo o 2 las rutas a través del DAG, que ambos contienen una subestructura óptima. ¿Entonces el problema se ha vuelto trivial sin el requisito de senderos simples? ¿O me estoy perdiendo algo o hay mejores explicaciones de por qué se requieren rutas simples? No¿los caminos más largos generales son solucionables por DP?

Tampoco estoy 100% seguro de qué requisitos son necesarios para garantizar que DP no se pueda utilizar. ¿Es necesario tener pesos de borde negativos, positivos, no ponderados, dirigidos, no dirigidos ... cuáles son los requisitos?

El problema de la ruta más larga tiene una subestructura óptima, y ​​esto puede usarse para mejorar el algoritmo trivial algoritmo . Primero tenemos que generalizar el problema:$O(n!)$$\tilde{O}(2^n)$

Trayectoria más larga generalizada: dado un gráfico , dos vértices y un conjunto de vértices , encuentre la ruta más larga en desde a evitando los vértices en .$G=(V,E)$$s,t \in V$$A \subseteq V \setminus \{s,t\}$$G$$s$$t$$A$

Denotando la solución a este problema por (se entiende el gráfico), tenemos la recurrencia Si el máximo en el primer caso está sobre el conjunto vacío (es decir, si no hay una ruta desde hasta evitando ) , asignamos .$\ell(s,t,A)$

Puede resolver esta recurrencia utilizando programación dinámica en tiempo .$\tilde{O}(2^n)$

Si bien aquí hay una subestructura óptima, hay demasiados parámetros para realizar un seguimiento, y esto es lo que hace que el problema sea insoluble.

En primer lugar, el camino simple más largo es NP-duro y no hay duda al respecto (ya que el camino hamiltoniano se reduce a él).

En segundo lugar, si considera las rutas no simples, entonces el problema no tiene mucho sentido, ya que la ruta no simple recorre un borde / vértice más de una vez, por lo que tiene un bucle. Como resultado de tener un bucle en la ruta, la ruta no simple más larga es infinita .

He estado pensando lo mismo en la última hora y llegué a las siguientes conclusiones:

i) La ruta más larga en un gráfico sin ciclos tiene una subestructura óptima y también la ruta más corta.

ii) La ruta más larga sin ciclos positivos tiene una subestructura óptima y también la ruta más corta sin ciclos negativos.

iii) La ruta más larga con ciclos positivos y la ruta más corta con ciclos negativos no existen, ya que podemos recorrer el ciclo infinitamente. Entonces miramos caminos sencillos.

iv) La ruta simple más larga con ciclos positivos y la ruta simple más corta con ciclos negativos es NP Hard.

DP resuelve (i) en O (V + E). Bellman-Ford resuelve (ii) en O (VE) y Djisktra ayuda en ciertos casos de (ii).

La literatura es confusa sobre este tema cuando el camino más largo es el camino más corto con pesos negados y viceversa. No veo ninguna razón para dar declaraciones generales, ya que la ruta más larga no tiene una subestructura óptima, pero la ruta más corta sí, etc.