Copyright HébergementWebs.com - License GPL

Clases NP Hard y NP-Complete

Diseño y análisis de algoritmos   2020-11-18 02:27:05

Clases NP Hard y NP-Complete Hay un problema en la class NPC si esta en NP y tambien es dificil que cualquier problema en NP. Un problema es NP-hard si todos los problemas en NP se pueden reducir a el en tiempo polinomial, incluso si no es NP en si. Si existe un algoritmo de tiempo polinomial para cualquiera de estos problemas, todos los problemas de NP podrian resolverse en tiempo polinomial. Estos problemas se denominan NP-completo . El fenomeno de NP-completitud es importante tanto por razones teoricas como practicas. Definicion de NP-Complete Un lenguaje B es NP-complete s " cumple dos condiciones B esta en NP Cada A en NP es un polinomio reducible en tiempo a B. Si un lenguaje satisface la segunda propiedad, pero no necesariamenteEl primero, el idioma B se conoce como NP-Hard . De manera informal, un problema de busqueda B es NP-Hard si hay un problema de NP-Complete A que Turing reduce a B . El problema en NP-Hard no se puede resolver en tiempo polinomial, hasta P = NP . Si un problema resulta ser un NPC, no hay necesidad de perder tiempo tratando de encontrar un algoritmo eficiente para ello. En cambio, podemos centrarnos en el algoritmo de aproximacion de diseno. Problemas NP-Complete Aqui hay algunos problemas NP-Complete, para los que no se conoce ningun algoritmo de tiempo polinomial. Determinar si una grafica tiene un ciclo hamiltoniano Determinar si una formula booleana es satisfactoria, etc. NP- Problemas dificiles Los siguientes problemas son NP-Dificiles El problema de satisfechoction du circuit Establecer portada Vertex Cover Problema del viajero comercial En este contexto, ahora discuters TSP es NP-Complete TSP es NP-Complete El problema del viajante consiste en un vendedor y un conjunto de ciudades. El vendedor debe visitar cada una de las ciudades partiendo de una determinada y regresando a la misma ciudad. El desafio del problema es que el vendedor ambulante quiere minimizar el tiempo total de viaje Prueba Para demostrar que TSP es NP-Complete , primero debemos demostrar que TSP es propiedad de NP . En TSP, buscamos un recorrido y comprobamos que el recorrido contiene cada vertice una vez. Luego se calcula el costo total de los bordes del recorrido. Finalmente, comprobamos si el costo es minimo. Esto se puede hacer en tiempo polinomial. Entonces TSP pertenece a NP . En segundo lugar, tenemos que demostrar que TSP es NP-hard . Para probar esto, una forma es mostrar que ciclo hamiltoniano ≤ p TSP (porque sabemos que el problema del ciclo hamiltoniano es NPcompleto). Suponga que G = (V, E) es una instancia del ciclo hamiltoniano. Por lo tanto, se crea una instancia de TSP. Creamos el grafico completo G = (V, E " ) , donde $$ E ^ { "} = lbrace (i, j) dos puntos i, j en V :: et: i neq j $$ Entonces, la funcion de costo esta definida de la siguiente manera: $$ t (i, j) = begin {cases} 0 & if: (i, j): in E 1 & else end {cases} $$ Ahora, suponga que existe un ciclo hamiltoniano h en G . Esta claro que el costo de cada borde en h es 0 en G porque cada borde pertenece a E . Por lo tanto, h tiene un costo de 0 enG" . Por lo tanto, si el grafico G tiene un ciclo hamiltoniano, entonces el grafico G tiene un costo de 0 visita. Por el contrario, asumimos que G" tiene un turno h " cuesta como maximo 0 . El costo de los bordes en E" es 0 y 1 por definicion . Por lo tanto, cada borde debe tener un costo de 0 porque el costo de h" es 0 . Entonces concluimos que h" solo contiene bordes en E . De esta manera hemos demostrado que G tiene un ciclo hamiltoniano, si y solo si G tiene un coste redondeado como maximo 0 . TSP es NP-completo.