EJEMPLOS DE PROBLEMAS NP COMPLETOS

EJEMPLOS DE PROBLEMAS NP COMPLETOS
1) PROBLEMA DE SATISFACIBILIDAD BOOLEANA (TAMBIÉN LLAMADO SAT)
La satisfacibilidad es el problema de determinar si a las variables de una fórmula booleana se le pueden asignar determinados valores que hagan que el resultado de la fórmula sea verdad.
n problema es satisfacible si existe al menos una asignación de valores a las variables del problema que lohagan verdadero ().
Un problema es insatisfacible si todas las posibles asignaciones de valores hacen el problema siempre falso ().

Ejemplo:
Se va a partir de la siguiente proposición en forma normal disyuntiva:

Se realiza la siguiente asignación:
y
Se sustituye en la expresión:


Se evalúa la expresión: .
Como no se ha encontrado una solución válida se hace una nuevaasignación:
y
Se evalúa la expresión: .

Como se ha encontrado una asignación de valores (modelo) que hacen a la expresión verdadera, se ha demostrado que este problema en concreto es satisfacible.
Estas son sólo dos de las ocho (2n = 3) posibles asignaciones. Se puede apreciar que el número de soluciones crece rápidamente al añadir nuevas variables, de ahí que su complejidad computacional seaelevada
2) PROBLEMA DE LA MOCHILA
También conocido por su abreviación KP (del inglés Knapsack problem).
Es un problema de optimización combinatoria, es decir, que busca la mejor solución entre un conjunto de posibles soluciones a un problema. Modela una situación análoga al llenar una mochila, incapaz de soportar más de un peso determinado, con todo o parte de un conjunto de objetos, cada uno conun peso y valor específicos. Los objetos colocados en la mochila deben maximizar el valor total sin exceder el peso máximo.
Problema de la mochila simple
Observar que en un problema de la mochila 0-1, si para cada tipo de ítem el beneficio y los pesos son idénticos (vi=wi), entonces el problema quedaría formulado de la siguiente forma

Por tanto si existe un vector xi tal que , entonces esaserá una solución al problema. Si existe una solución xi de este tipo, resolver el problema de la mochila realmente es resolver el problema de la suma de subconjuntos. Además si el conjunto de los pesos de los elementos es una secuencia supercreciente, es decir, se verifica que:

Entonces se dice que se trata de un problema de la mochila simple o también problema de la mochila tramposa. Este tipode problemas tiene importantes aplicaciones en el mundo de la criptografía.


Problema de la mochila de múltiple elección
Si en un problema de la mochila 0-1 los ítems están subdivididos en k clases, denotadas por Ni, y exactamente un ítem tienen que ser tomado de cada clase, entonces hablamos del problema de la mochila de múltiple elección.

Problema de la mochila múltiple
Si en unproblema de la mochila 0-1 tenemos n items y m mochilas con capacidades Wi entonces tenemos el problema de la mochila múltiple
Un caso especial del problema de la mochila múltiple es cuando los beneficios son iguales a los pesos y todas las mochilas tienen la misma capacidad. Entonces se le llama problema de la múltiple suma de subconjuntos.
3) PROBLEMA DEL CICLO HAMILTONIANO
Un camino hamiltoniano,en el campo matemático de la teoría de grafos, es un camino de un grafo, una sucesión de aristas adyacentes, que visita todos los vértices del grafo una sola vez. Si además el último vértice visitado es adyacente al primero, el camino es un ciclo hamiltoniano.

























4) PROBLEMA DEL VIAJANTE (TSP)
Consiste en encontrar la ruta que lleva a cabo unvendedor, que comenzando por un origen visita un determinado y pre establecido conjunto de ciudades y vuelve a ese origen, de manera que la distancia recorrida total es mínima y cada ciudad sólo se visita una vez.
Si se desea expresar el problema de forma matemática utilizando la teoría de grafos, el TSP consistiría en encontrar en una red G el ciclo Hamiltoniano tal que la suma de los costes de...