El problema de la mochila

Estamos de celebración en cuanto a divulgación de Matemáticas y es que Clara Grima, gran divulgadora de este campo ha comenzado un programa en TVE llamado «Una matemática viene a verte«. En el primer programa, emitido el 12/04/23, habla del Problema del viajero, un famoso problema NP y cita algunos problemas NP más, entre ellos el PROBLEMA DE LA MOCHILA, del que hablaremos en esta entrada del blog.

¿Qué es un problema NP?

Ya hablamos de ello en el artículo sobre los problemas del milenio. Ya que uno de los grandes problemas no resueltos de las Matemáticas (premiados con la medalla Fields y un millón de dolares) es el problema de P frente a NP.

El problema lo formuló el matemático estadounidense Stephen Cook en 1971. «P frente a NP» aspira a demostrar o refutar la creencia de que hay problemas para los que, por su complejidad, es más difícil encontrarles una solución que comprobar si esa solución es correcta. Para entenderlo, imaginemos un puzzle, resolverlo es difícil pero ver que está bien resuelto es una tarea fácil. 

Los problemas P (polinómicos) son los que se pueden resolver en un tiempo razonable, digamos fáciles de resolver con procedimientos conocidos.

Los problemas NP (no deterministas en tiempo polinómico) son aquellos que, aunque sea difícil encontrarles solución, una vez hallada se puede comprobar en un tiempo razonable que es correcta. Es decir, una vez resueltos se pueden comprobar fácilmente

Si se puede encontrar fácilmente una solución, esta se podrá verificar de manera sencilla, así que todo problema P es también NP. Lo que se desconoce es si hay algún problema NP que no sea P. Esta demostración tendrá grandes aplicaciones computacionales pero de momento nadie ha sido capaz de demostrarlo.

Problema NP completo

Los problemas NP completos son aquellos que si se resolvieran serían fáciles de comprobar y además se podrían transformar en otro problema de la misma clase (NP) en un tiempo razonable.

Esto significa que si se encontrara una forma de resolver un problema NP completo en un tiempo razonable, se podría resolver cualquier otro problema de la misma clase en un tiempo razonable también. Pero nadie ha podido demostrar si eso es posible o no.

Para entenderlo podemos pensar en un laberinto. Un problema NP sería encontrar la salida de un laberinto dado. Se puede verificar fácilmente si una ruta es la correcta o no, pero no se sabe si hay una forma rápida de encontrarla. Un problema NP completo sería encontrar la salida de cualquier laberinto posible. Si se pudiera hacer eso en un tiempo razonable, se podría resolver cualquier otro problema NP, como encontrar la ruta más corta entre dos puntos, o el conjunto de ciudades más cercanas que se pueden visitar en un viaje de la misma forma.

El PROBLEMA DE LA MOCHILA

Este problema es muy importante en la teoría de la computación, ya que pertenece a la clase de problemas NP completos, que hemos explicado. Es decir, es un problema cuya resolución es difícil pero cuya comprobación es fácil. No se conoce la forma (el algoritmo) para resolverlo en un tiempo polinomial (un tiempo razonable).

Además, si se encontrara un algoritmo polinomial para el problema de la mochila, se podría usar para resolver cualquier otro problema de la clase NP completo, lo que implicaría que NP = P, una de las mayores incógnitas de la ciencia.

El problema de la mochila es un problema de optimización combinatoria que consiste en elegir un subconjunto de objetos de un conjunto dado, de manera que se maximice el valor total de los objetos elegidos sin superar una capacidad máxima.

Existen varios métodos aproximados para resolver el problema de la mochila, como algoritmos voraces, programación dinámica o metaheurísticas. Estos métodos no garantizan encontrar la solución óptima, pero pueden obtener soluciones aceptables en un tiempo razonable. Sin embargo, el problema de la mochila sigue siendo un reto para la investigación y el desarrollo de nuevas técnicas y algoritmos.

Veamos un ejemplo para entenderlo.

EJEMPLO SENCILLO PROBLEMA DE LA MOCHILA

Por ejemplo, si tenemos una mochila con una capacidad de 15 kg y varios objetos con diferentes pesos y valores, ¿qué objetos debemos meter en la mochila para obtener el mayor beneficio posible?

Imaginemos que tenemos los siguientes objetos

La solución óptima al problema de la mochila es elegir los objetos B, C y D, que tienen un peso total de 7 kg y un valor total de 14 €.

Este ejemplo es fácil porque son pocos objetos y nos basta con usar un algoritmos de fuerza bruta (probar todas las combinaciones posibles). Que en este caso son 16. Lo que haría un ordenador o nosotros mismos para hacerlo bien y no dejarnos ninguna posibilidad es calcular todas las posibilidades y descartar los valores que no cumplan el máximo de peso (15 kg), como se ve en la siguiente tabla.

Parece fácil ¿verdad?

Este algoritmo (llamado de fuerza bruta) es muy simple, pero también muy ineficiente, ya que el número de combinaciones crece exponencialmente con el número de objetos. Por ejemplo, si tenemos 4 objetos como en el caso que nos ocupa, hay 2^4 = 16 posibles combinaciones. Si tenemos 10 objetos, hay 2^10 = 1024 posibles combinaciones. Si tenemos 20 objetos, hay 2^20 = 1048576 posibles combinaciones.

Imaginad cuantos cálculos habría que realizar para optimizar 40 objetos. Para 40 objetos, el algoritmo de fuerza bruta tendría que probar 2^40 posibles soluciones, lo que equivale a más de un billón. Si el ordenador pudiera probar una solución por nanosegundo, tardaría más de 34 años en resolver el problema.

El encontrar un algoritmo para resolver problemas NP y demostrar que estos son de la clase P implicaría grandes avances en muchos campos. Informática e inteligencia artificial, optimización de procesos, medicina y biología…

¿A que ahora entendéis porque el problema de P frente a NP es uno de los problemas del milenio?

Saludos desde el infinito

Bibliografia

• Clases de complejidad P y NP – Wikipedia, la enciclopedia libre
• P versus NP. ¿Nunca lo entendiste? (xatakaciencia.com)
• ¿Qué es eso del problema P versus NP? – YouTube
• Problema de la mochila – Wikipedia, la enciclopedia libre
• que es un problema p y np – Bing video
• ¿Qué es eso del problema P versus NP? – Bing video
• NP-completo – Wikipedia, la enciclopedia libre
• Desde la máquina de Turing a la computación cuántica (virtualpro.co)
• NP (clase de complejidad) – Wikipedia, la enciclopedia libre