Problema Subset-Sum (Suma de Subconjuntos).

Facultad de Ciencia y Tecnología

Sede Concepción del Uruguay

[pic 1]

Trabajo Práctico Final – NP Completos

• Tema: Problema Subset-Sum (Suma de Subconjuntos).

• Docente: Mg. Pascal Andrés.

• Alumno: Figueroa Gustavo Daniel.

• Cátedra: Teoría de la Computabilidad.

• Carrera: Licenciatura en Sistemas de Información.

Año: 2019

Consigna Planteada

1. Elegir un problema NP-Completo dentro de la lista que vimos en clase.
2. Programar el algoritmo trivial que lo resuelve (aunque dicha solución es muy costosa en tiempo de ejecución). El algoritmo debe tener como parámetro, como mínimo, la cantidad de elementos sobre la que se trabaja. Por ejemplo, en el Problema del Viajante de Comercio, la cantidad de clientes a visitar. Además puede tener también otros parámetros (en ese caso, la matriz de distancias entre clientes), o si no, estos valores se pueden generar aleatoriamente.
3. Realizar experimentos incrementando la cantidad de elementos y registrando el tiempo que tarda el algoritmo en obtener la solución. Pueden partir desde 10 elementos y aumentar la cantidad hasta que el tiempo de ejecución supere una hora.
4. Realizar un gráfico teniendo como eje X las cantidades y eje Y los tiempos.
5. Investigar algoritmos heurísticos para el problema elegido. Estudiar alguno de ellos y describir sus ventajas y desventajas.
6. Investigar aplicaciones del problema a casos reales (por ejemplo, el viajante de comercio se aplica a la distribución de mercadería de empresas mayoristas, a la distribución de cartas del Correo, etc).

1. Elegir un problema NP-Completo dentro de la lista que vimos en clase.

El problema elegido es el Subset-Sum (el problema de la suma de subconjuntos), el cual, para comenzar el presente trabajo, se presenta a continuación una introducción al problema:

Introducción al problema SubSet-Sum

En teoría de complejidad computacional, NP es el acrónimo en inglés de nodeterministic polynominal time (“Tiempo polinominal no determinista). Por lo tanto, NP se entiende como el conjunto de problemas que pueden ser resueltos en tiempo polinómico por una máquina de Turing no determinista. La importancia de la clase NP es que contiene muchos problemas de búsqueda y de optimización para los que se desea saber si existe una cierta solución o si existe una mejor solución que las conocidas. Entre los problemas de clase NP, existe una subclase muy importante de problemas que se conocen como NP-Completos. Tales problemas no son eficientemente resolubles o tratables desde la perspectiva de la ciencia computacional actual, pues los algoritmos que se han desarrollado hasta el momento para resolver problemas NP-Completos no operan en tiempo polinómico o “razonablemente alcanzable” para los propósitos humanos, esto conlleva obligadamente a grandes limitaciones en el diseño de sistemas computacionales con los que se pretende efectuar una inspección tan sencilla como lo es verificar subconjuntos que sumen un valor k determinado, pero a la vez tan compleja a la hora de abordar el interrogante crucial: ¿existe o no uno/varios subconjunto/s cuyos elementos sumen un valor k, teniendo en cuenta que habría que realizar demasiadas combinaciones para afirmar o refutar la proposición planteada?

El problema mejor conocido de este tipo es la suma de subconjuntos, probablemente el más simple de explicar de los problemas NP-Completos.

El problema de la suma de subconjuntos se puede definir como:

“Dado un conjunto de números enteros y un entero S, ¿existe un subconjunto no vacío de ellos, donde la suma de sus elementos es exactamente igual a S?”

El gran reto, por así decirlo, para la ciencia de la complejidad es tratar de encontrar un algoritmo, si es que existe alguno, que resuelve un problema NP-Completo en tiempo polinómico, lo cual bastaría para demostrar que existe una intersección entre las clases de complejidad NP-Completo y P, y más interesante aún se comprobaría que todo problema NP es definido en la clase P. Si se descubriera un algoritmo en tiempo polinómico para la suma de subconjunto, inmediatamente se dispondría de uno para cualquier otro problema NP-Completo. Es por esta razón que el estudio de las clases de complejidad NP y P es considerado como uno de los problemas más difíciles e importantes del siglo XXI y de la matemática en general. [1]

A continuación, en el siguiente trabajo se proporciona una introducción al problema de la suma de subconjuntos.

En la primera parte se analizará cómo obtener una solución óptima para el problema a través de programación trivial o fuerza bruta. Luego, se estudiará como incrementa el tiempo en que demora el algoritmo en obtener una solución, a medida que se incrementa la cantidad de elementos, lo cual se representará a través de un gráfico. A continuación, se detallara una posible solución al problema a través de una heurística. Para finalizar, se describirán aplicaciones del problema a casos reales.

1. Programar el algoritmo trivial que lo resuelve (aunque dicha solución es muy costosa en tiempo de ejecución). El algoritmo debe tener como parámetro, como mínimo, la cantidad de elementos sobre la que se trabaja. Por ejemplo, en el Problema del Viajante de Comercio, la cantidad de clientes a visitar. Además, puede tener también otros parámetros (en ese caso, la matriz de distancias entre clientes), o si no, estos valores se pueden generar aleatoriamente.

Código del algoritmo Adjunto.

1. Realizar experimentos incrementando la cantidad de elementos y registrando el tiempo que tarda el algoritmo en obtener la solución. Pueden partir desde 10 elementos y aumentar la cantidad hasta que el tiempo de ejecución supere una hora.