# Algoritmos 3 practica 1 ej 3 ### Ejercicio 3 MaxiSubconjunto #### Preguntar por complejidad y podas 3. Dada una matriz simétrica $M$ de $n \times n$ números naturales y un número $k$, queremos encontrar un subconjunto $I$ de $\{1, \ldots, n\}$ con $|I| = k$ que maximice $\sum_{i,j \in I} M_{ij}$. Por ejemplo, si $k = 3$ y: $$ M = \begin{pmatrix} 0 & 10 & 10 & 1 \\ -1 & 0 & 5 & 2 \\ -1 & -1 & 0 & 1 \\ -1 & -1 & -1 & 0 \end{pmatrix}, $$ entonces $I = \{1, 2, 3\}$ es una solución óptima. a) Diseñar un algoritmo de *backtracking* para resolver el problema, indicando claramente cómo se codifica una solución candidata, cuáles soluciones son válidas y qué valor tienen, qué es una solución parcial y cómo se extiende cada solución parcial. b) Calcular la complejidad temporal y espacial del mismo. c) Proponer una poda por optimalidad y mostrar que es correcta. #### Resolución (a consultar) ##### a) -inicializar i vacio y tambien un conjunto candidato en vacio - el backtracking toma $I$, el conjunto de indices candidatos, la suma actual, y el indice de inicoi para evitar repeticiones. - una solución candidata es un conjunto $I$, $|I|< k$ que se expande para maximizar la suma $M_{ij}$. - Cada vez que queremos añadir un elem a $I$ calculamos la suma de los elementos asociados a la matriz con $I$ $\cup$ {i} - una solucion es válida si |I| = k y si el valor da $\sum_{i,j \in I} M_{ij}$ - Una solución parcial sería un conjunto I con menos de k o sea $|I| < k$ se extiende añadiendo elementeos i al conjunto $I$ y chequeando la suma $M_{ij}$ #### Código (o algo así) ``` funcion backtracking(I,k,suma_actual_mejor_suma,M): if |I| == k: mejor_suma = suma_actual mejor_conjunto = I return mejor_suma, mejor_conjunto ## caso base ^^ for each elem i 1...n: if i is not in I: I_nuevo = I + {i} suma_nueva = suma_actual + SumaDeElementos(M, I_nuevo) ## Esto es una aux que calcula la suma de valores maximos posibles ## que se pueden añadir if suma_nueva + SumaPosibleRestante(M, I_nuevo,k) <= mejos_suma: Continue ... # poda por optimalidad Backtracking(I_nuevo, k, suma_nueva, mejor_suma,M) ``` pasé por **gpt-4** la consigna y mi código y me entregó lo siguiente: ``` funcion backtracking(I, k, suma_actual, mejor_suma, M): # Si el tamaño de I es igual a k, entonces hemos encontrado una solución. if |I| == k: # Actualizar la mejor suma si la suma actual es mayor que la mejor suma conocida. if suma_actual > mejor_suma: mejor_suma = suma_actual mejor_conjunto = I # Debemos retornar tanto la mejor suma como el mejor conjunto encontrado. return mejor_suma, mejor_conjunto mejor_conjunto_local = I # Recorrer cada elemento para expandir el conjunto I. for each elem i from 1 to n: # Considerar solo si i no está ya en I. if i not in I: I_nuevo = I + {i} suma_nueva = suma_actual + SumaDeElementos(M, I_nuevo) # Suma posible restante considera el máximo potencial para los elementos restantes. if suma_nueva + SumaPosibleRestante(M, I_nuevo, k) <= mejor_suma: continue # Poda por optimalidad. # Recursivamente intentar agregar más elementos a I_nuevo. suma_recursiva, conjunto_recursivo = backtracking(I_nuevo, k, suma_nueva, mejor_suma, M) # Actualizar la mejor suma y el mejor conjunto si se encuentra una mejor en la recursión. if suma_recursiva > mejor_suma: mejor_suma = suma_recursiva mejor_conjunto_local = conjunto_recursivo # Retornar el mejor resultado encontrado en esta llamada recursiva. return mejor_suma, mejor_conjunto_local ``` intenté codear esto pero no estoy seguro si funciona bien ```python def backtracking(I, k, suma_actual, mejor_suma, mejor_conjunto, M): """ Algoritmo de backtracking para encontrar el subconjunto de índices de tamaño k que maximiza la suma de los elementos correspondientes en la matriz M. """ # Comprueba si la combinación actual de índices tiene la longitud deseada k. if len(I) == k: # Si la suma actual es mayor que la mejor suma encontrada hasta ahora, actualiza la mejor suma y el subconjunto. if suma_actual > mejor_suma: mejor_suma = suma_actual mejor_conjunto = I return mejor_suma, mejor_conjunto n = len(M) # Explora todas las posibles extensiones al subconjunto actual I. for i in range(n): if i not in I: I_nuevo = I + [i] suma_nueva = suma_de_elementos(M, I_nuevo) # Aplica la poda si la suma máxima posible es menor o igual a la mejor suma actual. if suma_nueva + suma_posible_restante(M, I_nuevo, k) <= mejor_suma: continue # Poda por optimalidad. # Llamada recursiva al backtracking con el nuevo subconjunto y la nueva suma. mejor_suma, mejor_conjunto = backtracking( I_nuevo, k, suma_nueva, mejor_suma, mejor_conjunto, M ) return mejor_suma, mejor_conjunto ``` - Lo que mi codigo no está haciendo es actualizar la mejor suma y el mejor conjunto si se encuentra una mejor en la recursión. Habría que **preguntar si es necesario** pero yo creería que es fundamental actualizar la suma. ##### b) - Hay $n^k$ posibles subconjuntos, n es el tamaño de la matriz y k el tamaño del subconjunto que queremos encontrar. $\therefore$ $O(n^k)$ - Preguntar si es $O(n^k \times k^2)$ **Porque es algo que me dijo el bot** - Espacial: ¿lineal? No sé, revisar. #### c) Podas - La poda de optimalidad está planteada en el algoritmo y en el inciso a)