# TDA | Teoría: Algoritmos greedy - Los algoritmos voraces son una técnica para resolver problemas computacionales en la que se toma la mejor decisión local en cada paso con la esperanza de encontrar la solución global óptima al problema. Estos algoritmos son efectivos para un conjunto de problemas bien definidos y a menudo **son más simples y rápidos** que otras técnicas como la programación dinámica. ## Características - **Óptimo local:** En cada paso, el algoritmo elige la opción que parece ser la mejor en ese momento. - **Sin arrepentimientos:** Una vez tomada una decisión, el algoritmo no la reconsidera. - **Eficiencia:** Generalmente, los algoritmos voraces son más simples y rápidos. - **No siempre óptimos:** No garantizan una solución óptima para todos los problemas. ## Principio Greedy El principio greedy se puede resumir en dos pasos: 1. **Selección:** Escoger el elemento que parece ser el más óptimo entre los disponibles. 2. **Viabilidad:** Verificar que esta elección es válida dentro del contexto del problema. 3. **Solución óptima:** La elección debe contribuir a la solución óptima global del problema. ## Ejemplos ### Problema de la Mochila Fraccionaria Dado un conjunto de ítems con pesos y valores, y una mochila con capacidad limitada, el objetivo es maximizar el valor total sin sobrepasar la capacidad de la mochila. A diferencia del problema de la mochila 0/1, se pueden tomar fracciones de ítems. - **Solución greedy:** Seleccionar ítems basándose en el valor por unidad de peso, comenzando por el de mayor valor. $$\text{Ratio de valor} = \frac{\text{Valor}}{\text{Peso}}$$ ### Problema del Cambio de Monedas Dado un conjunto de denominaciones de monedas y un valor de cambio, el objetivo es encontrar el número mínimo de monedas que suman ese valor. - **Solución greedy:** Seleccionar siempre la moneda de mayor valor que no exceda el cambio restante. ```python def dar_cambio(cambio): suma = 0 M = set() while suma < cambio: proxima = mas_grande(cambio, suma) M.add(proxima) suma += proxima return M ``` ### Problema de Programación de Intervalos Dado un conjunto de actividades con tiempos de inicio y fin, el objetivo es seleccionar el número máximo de actividades que no se solapen. - **Solución greedy:** Seleccionar siempre la actividad que termina primero, considerando solo las actividades que comienzan después de que la actividad seleccionada previamente haya terminado. ## Conclusión Los algoritmos voraces son una herramienta poderosa para resolver ciertos problemas computacionales de manera eficiente. Su simplicidad y eficiencia los hacen atractivos, aunque es crucial entender las condiciones bajo las cuales garantizan una solución óptima. ## Resumen de la clase - **Heurísticas** - Una heurística es un procedimiento computacional que busca soluciones de buena calidad para un problema, intentando ser lo más preciso posible. - Para problemas de optimización, una heurística busca soluciones cuyo valor sea cercano al óptimo. - Un algoritmo es $\varepsilon$-aproximado ($\varepsilon \geq 0$) si $\left|\frac{x_A - x_{OPT}}{x_{OPT}}\right| \leq \varepsilon$. - APX y PTAS son clases de la Teoría de Complejidad Computacional relacionadas con la aproximación. - **Algoritmos Golosos (Greedy)** - Construyen una solución seleccionando en cada paso la mejor alternativa posible, sin considerar fuertemente las implicancias de esta selección. - Suelen ofrecer heurísticas simples para problemas de optimización y permiten construir soluciones razonables en tiempos eficientes. - **El Problema de la Mochila** - Datos de entrada incluyen la capacidad $C$ de la mochila, cantidad $n$ de objetos, pesos $p_i$ y beneficios $b_i$ de cada objeto. - Algoritmos golosos pueden basarse en seleccionar objetos por mayor beneficio, menor peso, o mejor ratio $b_i/p_i$. - En la versión fraccionaria del problema, seleccionar objetos basados en el mejor ratio $b_i/p_i$ garantiza una solución óptima. - **El Problema del Cambio** - Se busca dar el vuelto usando el mínimo número de monedas posibles con denominaciones dadas. - El algoritmo goloso selecciona la moneda de mayor valor que no exceda la cantidad restante por devolver. - Bajo ciertas condiciones (relaciones entre las denominaciones de las monedas), este algoritmo proporciona una solución óptima. - **Tiempo de Espera Total en un Sistema** - Se desea atender $n$ clientes, cada uno requiere un tiempo $t_i$ para ser atendido, y se busca minimizar el tiempo total de espera. - El algoritmo goloso atiende primero al cliente con menor tiempo de atención requerido. - Este enfoque garantiza una solución óptima para minimizar el tiempo total de espera. ## Notas del cormen ### Problema de Programación de Intervalos Dado un conjunto de actividades con tiempos de inicio $s[i]$ y tiempos de finalización $f[i]$ para cada actividad $i$, el objetivo es seleccionar el número máximo de actividades que no se solapen. #### Estrategia Greedy La estrategia greedy para el problema de selección de actividades consiste en seleccionar siempre la actividad que termina primero, es decir, la que tiene el menor tiempo de finalización, considerando solo las actividades que comienzan después de que la actividad seleccionada previamente haya terminado. Este enfoque garantiza que se maximice el número de actividades seleccionadas sin solapamientos. #### Algoritmo Greedy de Selección de Actividades El siguiente algoritmo implementa la estrategia greedy para el problema de selección de actividades en Python: Greedy-Iterative-Activity-Selector(A, s, f): Sort A by finish times stored in f S = {A[1]} k = 1 n = A.length for i = 2 to n: if s[i] ≥ f[k]: S = S U {A[i]} k = i return S ## La subestructura óptima del problema de selección de actividades - Podemos verificar fácilmente que el problema de selección de actividades exhibe una subestructura óptima. - Denotemos por $S_{ij}$ el conjunto de actividades que inician después de que la actividad $a_i$ termina y que finalizan antes de que la actividad $a_j$ inicie. - Supongamos que deseamos encontrar un conjunto máximo de actividades mutuamente compatibles en $S_{ij}$, y supongamos además que tal conjunto máximo es $A_{ij}$, que incluye alguna actividad $a_k$. - Al incluir $a_k$ en una solución óptima, nos enfrentamos a dos subproblemas: encontrar actividades mutuamente compatibles en el conjunto $S_{ik}$ (actividades que inician después de que la actividad $a_i$ termina y que finalizan antes de que $a_k$ inicie). - Y encontrar actividades mutuamente compatibles en el conjunto $S_{kj}$ (actividades que inician después de que la actividad $a_k$ termina y que finalizan antes de que $a_j$ inicie). - Sea $A_{ik} = A_{ij} \cap S_{ik}$ y $A_{kj} = A_{ij} \cap S_{kj}$, de modo que $A_{ik}$ contiene las actividades en $A_{ij}$ que finalizan antes de que $a_k$ inicie y $A_{kj}$ contiene las actividades en $A_{ij}$ que inician después de que $a_k$ termine. - Así, tenemos $A_{ij} = A_{ik} \cup \{a_k\} \cup A_{kj}$, y por lo tanto el conjunto de tamaño máximo $A_{ij}$ de actividades mutuamente compatibles en $S_{ij}$ consiste en $|A_{ij}| = |A_{ik}| + |A_{kj}| + 1$ actividades. - El argumento habitual de cortar y pegar muestra que la solución óptima $A_{ij}$ debe también incluir soluciones óptimas a los dos subproblemas para $S_{ik}$ y $S_{kj}$. - Si pudiésemos encontrar un conjunto $A'_{kj}$ de actividades mutuamente compatibles en $S_{kj}$ donde $|A'_{kj}| > |A_{kj}|$, entonces podríamos usar $A'_{kj}$, en vez de $A_{kj}$, en una solución al subproblema para $S_{ij}$. - Habríamos construido un conjunto de $|A_{ik}| + |A'_{kj}| + 1 > |A_{ik}| + |A_{kj}| + 1 = |A_{ij}|$ actividades mutuamente compatibles, lo cual contradice la suposición de que $A_{ij}$ es una solución óptima. - Un argumento simétrico se aplica a las actividades en $S_{ik}$. Esta forma de caracterizar la subestructura óptima sugiere que podríamos resolver el problema de selección de actividades mediante programación dinámica. - Si denotamos el tamaño de una solución óptima para el conjunto $S_{ij}$ por $c[i, j]$, entonces tendríamos la recurrencia $c[i, j] = c[i, k] + c[k, j] + 1$. Por supuesto, si no supiéramos que una solución óptima para el conjunto $S_{ij}$ incluye la actividad $a_k$, tendríamos que examinar todas las actividades en $S_{ij}$ para encontrar cuál elegir, de modo que: $$ c[i, j] = \begin{cases} 0 & \text{si } S_{ij} = \emptyset; \\ \max\limits_{a_k \in S_{ij}} \{c[i, k] + c[k, j] + 1\} & \text{si } S_{ij} \neq \emptyset; \end{cases} $$ - Haciendo la elección greedy. ¿Y si pudiéramos elegir una actividad para añadir a nuestra solución óptima sin tener que resolver primero todos los subproblemas? - Eso podría ahorrarnos tener que considerar todas las elecciones inherentes en la recurrencia $(16.2)$. - De hecho, para el problema de selección de actividades, solo necesitamos considerar una elección: **la elección greedy**. - ¿A qué nos referimos con la elección greedy para el problema de selección de actividades? - La intuición sugiere que deberíamos elegir una actividad que deje el recurso disponible para tantas otras actividades como sea posible. - Ahora, de las actividades que terminamos eligiendo, una de ellas debe ser la primera en terminar. - Nuestra intuición nos dice, por lo tanto, elegir la actividad en $S$ con el tiempo de finalización más temprano, ya que eso dejaría el recurso disponible para tantas de las actividades que le siguen como sea posible. - (Si más de una actividad en $S$ tiene el tiempo de finalización más temprano, entonces podemos elegir cualquier actividad de ese tipo). - En otras palabras, dado que las actividades están ordenadas en orden monótonamente creciente por tiempo de finalización, la elección greedy es la actividad $a_1$. - Elegir la primera actividad en terminar no es la única forma de pensar en hacer una elección greedy para este problema; el Ejercicio $16.1$-$3$ te pide que explores otras posibilidades. - Si hacemos la elección greedy, solo nos queda un subproblema por resolver: encontrar actividades que comiencen después de que $a_1$ termine. - ¿Por qué no tenemos que considerar actividades que terminan antes de que $a_1$ comience? - Tenemos que $s_1 < f_1$, y $f_1$ es el tiempo de finalización más temprano de cualquier actividad, y por lo tanto, ninguna actividad puede tener un tiempo de finalización menor o igual a $s_1$. - Así, todas las actividades que son compatibles con la actividad $a_1$ deben comenzar después de que $a_1$ termine. - Además, ya hemos establecido que el problema de selección de actividades exhibe una subestructura óptima. - Sea $S_k = \{a_i \in S | s_i > f_k\}$ el conjunto de actividades que comienzan después de que la actividad $a_k$ termine. - Si hacemos la elección greedy de la actividad $a_1$, entonces $S_1$ queda como el único subproblema por resolver. - La subestructura óptima nos dice que si $a_1$ está en la solución óptima, entonces una solución óptima al problema original consiste en la actividad $a_1$ y todas las actividades en una solución óptima al subproblema $S_1$. - Una gran pregunta permanece: ¿es correcta nuestra intuición? ¿Es la elección greedy, en la que elegimos la primera actividad en terminar, siempre parte de alguna solución óptima? - El siguiente teorema muestra que así es. ## Teorema: - Considere cualquier subproblema no vacío $S_k$, y sea $a_m$ una actividad en $S_k$ con el tiempo de finalización más temprano. - Entonces $a_m$ se incluye en algún subconjunto de tamaño máximo de actividades mutuamente compatibles de $S_k$. ## Prueba - Sea $A_k$ un subconjunto de tamaño máximo de actividades mutuamente compatibles en $S_k$, y sea $a_j$ la actividad en $A_k$ con el tiempo de finalización más temprano. - Si $a_j = a_m$, hemos terminado, ya que hemos mostrado que $a_m$ está en algún subconjunto de tamaño máximo de actividades mutuamente compatibles de $S_k$. - Si $a_j \neq a_m$, sea el conjunto $A'_k = A_k - \{a_j\} \cup \{a_m\}$ sea $A_k$ pero sustituyendo $a_m$ por $a_j$. - Las actividades en $A'_k$ son disjuntas, lo cual se sigue porque las actividades en $A_k$ son disjuntas, $a_j$ es la primera actividad en $A_k$ en terminar, y $f_m \leq f_j$. - Dado que $|A'_k| = |A_k|$, concluimos que $A'_k$ es un subconjunto de tamaño máximo de actividades mutuamente compatibles de $S_k$, e incluye a $a_m$. - Así, vemos que aunque podríamos ser capaces de resolver el problema de selección de actividades con programación dinámica, no necesitamos hacerlo. - (Además, todavía no hemos examinado si el problema de selección de actividades incluso tiene subproblemas superpuestos). - En cambio, podemos elegir repetidamente la actividad que termina primero, mantener solo las actividades compatibles con esta actividad, y repetir hasta que no queden actividades. - Además, como siempre elegimos la actividad con el tiempo de finalización más temprano, los tiempos de finalización de las actividades que elegimos deben aumentar estrictamente. - Podemos considerar cada actividad solo una vez en total, en orden monótonamente creciente de tiempos de finalización. - Un algoritmo para resolver el problema de selección de actividades no necesita trabajar de abajo hacia arriba, como un algoritmo de programación dinámica basado en tablas. - En cambio, puede trabajar de arriba hacia abajo, eligiendo una actividad para poner en la solución óptima y luego resolviendo el subproblema de elegir actividades de aquellas que son compatibles con las ya elegidas. - Los algoritmos greedy típicamente tienen este diseño de arriba hacia abajo: hacer una elección y luego resolver un subproblema, en lugar de la técnica de abajo hacia arriba de resolver subproblemas antes de hacer una elección.