La ruta más larga optimizada es NP Complete

Problema de la ruta más larga optimizada : El problema de la ruta más larga optimizada establece que dado un gráfico G , de un conjunto de vértices V y aristas E , la tarea es demostrar que existe una ruta de longitud al menos K entre un conjunto de Nodes V _s y V _e .

Declaración del problema : Dado un gráfico G(V, E, K) y un conjunto de Nodes V _s y V _e con la secuencia de Nodes, de longitud ≥ K .

Explicación :
una instancia del problema es una entrada especificada para el problema. Una instancia del problema de la ruta más larga optimizada es G(V, E, V _s , V _e , K) . Dado que un problema NP-completo es un problema que está tanto en NP como en NP-Difícil , la prueba de la afirmación de que un problema es NP-Completo consta de dos partes:

1. El problema en sí está en la clase NP.
2. Todos los demás problemas en la clase NP pueden ser reducibles en tiempo polinomial a eso.
   (B es reducible en tiempo polinomial a C se denota como B≤P ^C )

Si solo se cumple la segunda condición, el problema se llama NP-Hard .

Pero no es posible reducir cada problema NP a otro problema NP para mostrar su NP-Completitud todo el tiempo. Es por eso que si queremos mostrar que un problema es NP-Completo, simplemente mostramos que el problema está en NP y cualquier problema NP-Completo es reducible a eso, entonces hemos terminado B ≤ P ^C Por lo tanto, podemos verificar que el camino más largo optimizado El problema es NP-Completo usando las siguientes dos proposiciones:

• El problema de ruta más larga optimizada está en NP :
  si algún problema está en NP, se le otorga un ‘certificado’, que es una solución al problema y una instancia del problema, entonces se puede verificar (verifique si la solución dada es correcta o no ) que el certificado en tiempo polinomial. Esto se puede hacer mediante un camino P , que consta de un conjunto de vértices < V ₁ , V ₂ , V ₃ , ….V _n >. Verifique si la ruta conecta V ₁ y V _n completamente y la longitud de la ruta es como máximo K .

• El problema de la ruta más larga optimizada es NP-difícil:
  para demostrar que la ruta más larga es NP-difícil, deduzca una reducción de un NP-difícil conocido al problema. Realice una reducción en la que un problema del camino hamiltoniano no dirigido pueda reducirse al problema del camino más largo. El camino hamiltoniano no dirigido usa como entrada un gráfico G(V ₁ , V _n ) donde el gráfico G tiene Nodes V ₁ y V _n . La ruta hamiltoniana no dirigida es una ruta no dirigida a lo largo del gráfico que comienza en un vértice y termina en otro que atraviesa todos los Nodes.

  Ahora, sea K el número de Nodes en G. Cada instancia de la ruta hamiltoniana no dirigida se puede convertir a la ruta más larga de la siguiente manera:
  para la entrada G (V ₁ , V _n ), salida G (V ₁ , V _n , k). Esta reducción toma un tiempo polinomial simplemente contando el número de vértices en G. La reducción se puede demostrar mediante las siguientes dos proposiciones:

  1. Suponga que el grafo original G(V, E) tiene Nodes V ₁ y V _n tiene un camino hamiltoniano no dirigido, que atraviesa todos los vértices, por lo tanto, G(V, E, K) es verdadero porque dos Nodes cualesquiera en G serán conectados por un camino de longitud igual a sus Nodes, es decir, K , por lo tanto, el problema del camino más largo se cumple.
  2. Supongamos que el gráfico G'(V, E, V _s , V _e , K) tiene un Lcamino de longitud K de V _s a V _e , lo que implica que G’ contiene un camino simple de longitud K de V _s a V _e .
     Pero, G contiene K vértices, por lo tanto atraviesa todos los vértices comenzando en V _s y terminando en V _e formando un camino hamiltoniano, G'(V _s , V _e ) .

     

     Sean V ₁ ≡ B y V _n ≡ D
     Ahora, G tiene un camino hamiltoniano no dirigido ≡ BCAD de K = 4 .
     Por lo tanto, G contiene un camino optimizado de longitud = 4 entre B y D.