¿Qué es un algoritmo codicioso?
Es posible que haya escuchado acerca de muchas técnicas de diseño algorítmico mientras examinaba algunos de los artículos aquí. Algunos de ellos son:
- Fuerza bruta
- Divide y conquistaras
- Programación codiciosa
- Programación dinámica, por nombrar algunos. En este artículo, aprenderá qué es un algoritmo codicioso y cómo puede usar esta técnica para resolver muchos problemas de programación que de otra manera no parecerían triviales.
Imagina que vas a hacer senderismo y tu objetivo es alcanzar la cima más alta posible. Ya tiene el mapa antes de comenzar, pero hay miles de posibles rutas que se muestran en el mapa. Eres demasiado vago y simplemente no tienes tiempo para evaluar cada uno de ellos. ¡Al diablo con el mapa! Comenzó a caminar con una estrategia simple: sea codicioso y miope. Simplemente tome los caminos que tienen una mayor pendiente. Esta parece una buena estrategia para hacer senderismo. ¿Pero es siempre el mejor?
Una vez finalizado el viaje y todo el cuerpo adolorido y cansado, mira el mapa de senderismo por primera vez. ¡Oh Dios mío! Hay un río fangoso que debería haber cruzado, en lugar de seguir caminando hacia arriba. Esto significa que un algoritmo codicioso elige la mejor opción inmediata y nunca reconsidera sus opciones. En términos de optimizar una solución, esto simplemente significa que la solución codiciosa intentará encontrar soluciones óptimas locales, que pueden ser muchas, y podría perderse una solución óptima global.
Definicion formal
Suponga que tiene una función objetivo que debe optimizarse (maximizada o minimizada) en un punto dado. Un algoritmo codicioso toma decisiones codiciosas en cada paso para garantizar que la función objetivo esté optimizada. El algoritmo Greedy tiene solo una oportunidad para calcular la solución óptima para que nunca retroceda y revierta la decisión.
Los algoritmos codiciosos tienen algunas ventajas y desventajas:
- Es bastante fácil idear un algoritmo codicioso (o incluso varios algoritmos codiciosos) para un problema. Analizar el tiempo de ejecución de los algoritmos codiciosos generalmente será mucho más fácil que para otras técnicas (como dividir y conquistar). Para la técnica Divide y vencerás, no está claro si la técnica es rápida o lenta. Esto se debe a que en cada nivel de recursividad el tamaño de se reduce y aumenta el número de subproblemas.
- La parte difícil es que para los algoritmos codiciosos tienes que trabajar mucho más para comprender los problemas de corrección. Incluso con el algoritmo correcto, es difícil probar por qué es correcto. Demostrar que un algoritmo codicioso es correcto es más un arte que una ciencia. Implica mucha creatividad. Por lo general, crear un algoritmo puede parecer trivial, pero demostrar que es realmente correcto es un problema completamente diferente.
Problema de programación de intervalos
Vamos a sumergirnos en un problema interesante que puede encontrar en casi cualquier industria o condición social. Algunas instancias del problema son las siguientes:
- Se le da un conjunto de N horarios de conferencias para un solo día en una universidad. El horario para una conferencia específica es de la forma (s hora, f hora) donde s hora representa la hora de inicio de esa conferencia y, de manera similar, la hora f representa la hora de finalización. Dada una lista de N horarios de conferencias, debemos seleccionar el conjunto máximo de conferencias que se llevarán a cabo durante el día de manera que ninguna de las conferencias se superponga entre sí, es decir, si las conferencias Li y Lj están incluidas en nuestra selección, entonces la hora de inicio de j > = tiempo de finalización de i o viceversa .
- Su amigo trabaja como consejero de campamento y está a cargo de organizar actividades para un grupo de campistas. Uno de sus planes es el siguiente ejercicio de mini-triatlón: cada participante debe nadar 20 vueltas en una piscina, luego andar en bicicleta 10 millas y luego correr 3 millas.
- El plan es enviar a los concursantes de manera escalonada, a través de la siguiente regla: los concursantes deben usar la piscina de uno en uno. En otras palabras, primero un participante nada las 20 vueltas, sale y comienza a andar en bicicleta.
- Tan pronto como esta primera persona sale de la piscina, un segundo competidor comienza a nadar las 20 vueltas; tan pronto como sale y comienza a andar en bicicleta, un tercer participante comienza a nadar, y así sucesivamente.
- Cada participante tiene un tiempo de natación proyectado, un tiempo de ciclismo proyectado y un tiempo de carrera proyectado. Tu amigo quiere decidir un horario para el triatlón: un orden en el que secuenciar las salidas de los concursantes.
- Digamos que la hora de finalización de un programa es la hora más temprana en la que todos los participantes terminarán con las tres etapas del triatlón, asumiendo que las proyecciones de tiempo son precisas. ¿Cuál es el mejor orden para enviar gente, si uno quiere que toda la competencia termine lo antes posible? Más precisamente, proporcione un algoritmo eficiente que produzca un cronograma cuyo tiempo de finalización sea lo más pequeño posible
El problema de la programación de conferencias
Veamos los distintos enfoques para resolver este problema.
Hora de inicio más temprana Primero, es decir, seleccione el intervalo que tiene la hora de inicio más temprana. Eche un vistazo al siguiente ejemplo que rompe esta solución. Esta solución falló porque podría haber un intervalo que comienza muy temprano pero que es muy largo. Esto significa que la siguiente estrategia que podríamos probar sería la de mirar primero a intervalos más pequeños.
Intervalo más pequeño Primero, es decir, termina seleccionando las conferencias en orden de su intervalo general, que no es más que su finish time - start time. Nuevamente, esta solución no es correcta. Mira el siguiente caso.
Puede ver claramente que la conferencia de intervalo más corto es la del medio, pero esa no es la solución óptima aquí. Veamos otra solución para este problema obteniendo conocimientos de esta solución.
Intervalo menos conflictivo Primero, es decir, debería observar los intervalos que causan el menor número de conflictos. Una vez más, tenemos un ejemplo en el que este enfoque no logra encontrar una solución óptima.
El diagrama nos muestra que el intervalo menos conflictivo es el que está en el medio con solo 2 conflictos. Después de eso, solo podemos elegir los dos intervalos en los extremos con conflictos 3 cada uno. Pero la solución óptima es elegir los 4 intervalos en el nivel superior.
Tiempo de finalización más temprano primero . Este es el enfoque que siempre nos da la solución más óptima a este problema. Obtuvimos muchos conocimientos de enfoques anteriores y finalmente encontramos este enfoque. Ordenamos los intervalos de acuerdo con el orden creciente de sus tiempos de finalización y luego comenzamos a seleccionar intervalos desde el principio. Mire el siguiente pseudocódigo para mayor claridad.
function interval_scheduling_problem(requests) schedule \gets \{\} while requests is not yet empty choose a request i_r \in requests that has the lowest finishing time schedule \gets schedule \cup \{i_r\} delete all requests in requests that are not compatible with i_r end return schedule end ¿Cuándo usamos algoritmos codiciosos?
Los algoritmos codiciosos pueden ayudarlo a encontrar soluciones a muchos problemas aparentemente difíciles. El único problema con ellos es que puede encontrar la solución correcta, pero es posible que no pueda verificar si es la correcta. Todos los problemas codiciosos comparten la propiedad común de que un óptimo local puede eventualmente conducir a un mínimo global sin reconsiderar el conjunto de opciones ya consideradas.
Los algoritmos codiciosos nos ayudan a resolver muchos tipos diferentes de problemas, como: