fdelu
commented
3 months ago Hola! Les dejo los comentarios de la reentrega. Les cierro el TP con un 7, cualquier consulta avisenme. Saludos!
Reducción
Ahora si, efectivamente, la reducción es correcta. De todas formas, está incompleta: falta la prueba de las implicancias. En un parcial esto bajaría puntos. Les dejo el ejemplo el resuelto de Martín para que entiendan a lo que me refiero: lo que a ustedes les faltaría sería lo de las secciones 2.2.2 y 2.2.3. En este caso lo que habría que probar es que para cualquier 2-Partition con solución, reducirlo al del TP va a tener solución (2-Partition->TP) y que para cualquier caso reducido del TP con solución, 2-partition tiene solución (TP->2-Partition).
6.1/6.2 Algoritmo y Complejidad del maestro pakku
Hubiera preferido código real antes que pseudocódigo, pero ok
10.0.2. Es NP-Completo
Se puede reducir tanto Partition Problem a Subset Sum, como al rev´es. Empezamos reduciendo Partition Problem a Subset Sum.
A efectos de este trabajo práctico, no sirve de nada la reducción de Partition Problem a Subset Sum. Ya sabemos que Subset Sum es NP-Completo.
Ahora para reducir Subset Sum a Partition Problem
Esta prueba esta incluso mucho mejor que la del Partition Problem al problema del TP, usando las ecuaciones matemáticas. La prueba en sí esta probando solamente que si hay Partition Problem entonces hay Subset Sum, y de nuevo le faltaría sentido de la implicancia (si hay Subset Sum hay Partition Problem).
Hola! Les dejo las correcciones
3. El Problema de la Tribu del Agua, es NP-Completo?
No necesariamente. Se podría asumir que $K \leq N$ ya que sino quedarían grupos vacíos que no tiene mucho sentido. Con que se cumpla esa condición ya es $O(N)$
Para este punto es preferible que directamente implementen un (pseudo)código que haga la verificación y listo. De todas formas su explicación fue bastante detallada así que se las acepto. Para los examenes tengan esto en cuenta.
3.2. Demostración de que el Problema de la Tribu del Agua es NP-Completo
Es verdad que para cualquier instancia del problema de la bolsa que tiene solución el problema de la tribu del agua también tiene solución:
$\sum_{x_j \in S_i} x_j \leq W$ $\forall i$
$\Rightarrow \left( \sum_{x_j \in S_i} x_j \right)^2 \leq W^2$ $\forall i$
$\Rightarrow \sum{i=1}^k \left( \sum{x_j \in S_i} x_j \right)^2 \leq k W^2 = B$
Sin embargo, en el sentido contrario, no funciona, va contraejemplo:
Tengo el problema de las bolsas con elementos $[40, 32, 22]$, $k=2$ y capacidad de la bolsa $W=48$. Fijense que como $k=2$ tengo que poner 2 elementos en una misma bolsa, pero si sumo los 2 más chicos, ya $32+22=54 > 48$ por lo que no hay solución.
Sin embargo, con el problema de los maestros, $B = k \cdot W^2 = 2 \cdot 48^2 = 4608$ tengo la solución $[40]$, $[32, 22]$, que da una suma de $40^2 + (32+22)^2 = 1600 + 2916 = 4516 < 4608$. Es decir, con este ejemplo, el problema de los maestros tiene solución pero el de las bolsas no, así que la reducción sería inválida.
4. Propuesta de Solución Backtracking
Podas:
fuera del index: No es tanto una poda sino más bien una condición de corte.grupos vacíos: No esta mal ya que es verdad que este camino probablemente no vaya a ser la solución óptima pero quizás venía bien recorrerlo para llegar a una mejor cota. De todas formas estas ramas seguro que iban a cortarse también por las otras podas.cota superior: Está genial, quizás me faltó un poco de formalidad en la explicación (demostrar un poco más matemáticamente por qué esto ayuda a la función objetivo)En general bastante bien, muy completo el algoritmo.
4.3. Complejidad
No se pedía, pero la dada no es correcta. Sería más bien $O(k^n)$ ($k$ posibilidades para cada maestro). $O(n!)$ es simplemente la cantidad de permutaciones de un conjunto de $n$ elementos y $O(2^n)$ sería si hubiera solo 2 posibilidades para cada maestro (binario).
5. Propuesta de Solución Programación Lineal
Como dijeron ustedes arriba, hay $n \cdot k$ variables binarias por lo que la complejidad sería $O(2^{nk})$.
5.1. Mediciones de PLE y comparación con Backtracking
Es preferible que usen un error relativo (es decir el porcentaje de error) más que el absoluto para cuantificarlo en estos casos.
Al gráfico de tiempos le falta la unidad del eje del tiempo. ¿Los limitaron a 10 minutos que cortaron varios en 600?
6.1. Algoritmo
¿Por qué para encontrar el grupo más débil ordenan todo el arreglo? Eso es $O(k \log k)$ cuando recorriendo el arreglo lo hacen en $O(k)$, y si usaran un heap en $O(\log k)$...
6.2. Complejidad
No, no es esa la complejidad, porque estan ordenando el arreglo en todas las iteraciones. Eso hubiera sido si lo encontraban con una búsqueda lineal.
6.3. Análisis
No me quedó del todo claro el análisis que hicieron con PL, el por qué de cada una de las restricciones que utilizaron.
8. Mediciones temporales
Faltaron mediciones con sets de datos generados por ustedes
Les pido que me hagan una reentrega, corrigiendo más que nada el tema de la reducción (punto 1). Con eso ya los puedo aprobar, pero si quieren corregir más cosas, también lo voy a tener en cuenta. Especialmente el tema de mediciones con sets de datos propios del algoritmo de backtracking y la implementación y complejidad del algoritmo de Pakku.
Para la reducción: asegurense de hacer la demostración en ambos sentidos. Si usan un problema que no se dio en clase ponganme por lo menos en un anexo alguna justificación de por qué ese es NP-Completo también. Les recomiendo que busquen sobre el partition problem.
No cambien el informe. Hagan las correcciones en un anexo.
Cualquier consulta avisenme!