Problema Subset-Sum (Suma de Subconjuntos).
Enviado por Sebastian Bonato • 28 de Junio de 2023 • Apuntes • 1.732 Palabras (7 Páginas) • 304 Visitas
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
- Elegir un problema NP-Completo dentro de la lista que vimos en clase.
- 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.
- 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.
- Realizar un gráfico teniendo como eje X las cantidades y eje Y los tiempos.
- Investigar algoritmos heurísticos para el problema elegido. Estudiar alguno de ellos y describir sus ventajas y desventajas.
- 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).
- 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.
- 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.
- 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.
Cantidad de Elementos | Demora de Ejecución | Resultados |
10 | 0.02594 segundos = 0.0004 Minutos | Sin Coincidencias |
11 | 0.04487 segundos = 0.00074 Minutos | Hubo 6 coincidencias |
12 | 0.08581 segundos = 0.0014 Minutos | Sin coincidencias |
13 | 0.17548 segundos = 0.0029 Minutos | Hubo 5 Coincidencias |
14 | 0.48771 segundos = 0.0081 Minutos | Hubo 2 Coincidencias |
15 | 2.48826 segundos = 0.0414 Minutos | No hubo Coincidencias |
16 | 5.59397 segundos = 0.0932 Minutos | Hubo 3 coincidencias |
17 | 13.14582 segundos = 0.2190 Minutos | Hubo 4 Coincidencias |
18 | 27.61192 segundos = 0.4601 Minutos | Hubo 3 Coincidencias |
19 | 59.43613 segundos = 0.9906 Minutos | Hubo 3 Coincidencias |
20 | 125.57688 segundos = 2.0929 Minutos | Hubo 20 Coincidencias |
21 | 259.23152 segundos = 4.3205 Minutos | Hubo 1 coincidencia |
22 | 783.11122 segundos = 13.0518 Minutos | Hubo 1 Coincidencia |
23 | 1662.06214 segundos = 27.7010 Minutos | Hubo 4 Coincidencia |
24 | 3245.04313 Segundos = 54.08405 Minutos = 0.9014 Horas | No hubo coincidencias |
25 | 4753.47122 segundos = 79.2245 Minutos = 1.32 Horas | Hubo 12 Coincidencias |
26 | 9127.41523 segundos = 152.1235 Minutos = 2.53 Horas | Hubo 1 Coincidencia |
...