Publicado · en mejora
Algorithm
Los algoritmos voraces eligen en cada paso la mejor opción local sin retroceder: planificación de intervalos, códigos de Huffman, mochila fraccionaria.
Un algoritmo voraz (greedy) construye su solución mediante una serie de decisiones: en cada paso toma el candidato que parece mejor según una regla fija y nunca revisa esa decisión. La mayoría ordena los candidatos o los coloca en una cola de prioridad y los acepta uno a uno, por lo que el código es breve y el tiempo de ejecución suele ser O(n log n), dominado por la ordenación o las operaciones del montículo.
Cuando funciona, el enfoque voraz es la solución más rápida y sencilla, pero no siempre funciona. Para garantizar el óptimo deben cumplirse la propiedad de elección voraz y la subestructura óptima, algo que suele demostrarse con un argumento de intercambio. Basta un contraejemplo, como formar 6 con monedas de 1, 3 y 4, para saber que hace falta programación dinámica. El principio voraz también está en el núcleo de algoritmos muy usados, como la codificación de Huffman, los caminos mínimos de Dijkstra y los árboles de expansión mínima.
Empieza por la planificación de intervalos (selección de actividades) y explica con un argumento de intercambio por qué elegir la reunión que termina antes es correcto. Después implementa la codificación de Huffman, la mochila fraccionaria y la asignación de salas con un montículo, y acostúmbrate a comparar tus resultados voraces con una búsqueda exhaustiva en entradas pequeñas: es la forma más rápida de detectar una regla equivocada en una entrevista de programación.
Debe existir una solución óptima que contenga la primera elección voraz; es la condición clave para que el algoritmo sea correcto.
Se demuestra que cualquier solución óptima puede transformarse, elemento a elemento, en la solución voraz sin empeorar.
Los candidatos se ordenan por hora de fin, valor por peso o frecuencia, o se extraen de un montículo, así que casi siempre cuesta O(n log n).
Con sistemas de monedas arbitrarios o la mochila 0/1 la regla voraz se equivoca y hay que pasar a la programación dinámica.
El programa elige el mayor conjunto de reuniones que no se solapan. Ordena las reuniones por hora de fin y acepta una solo si empieza después de que termine la última elegida. Ordenar cuesta O(n log n) y el recorrido O(n); en el ejemplo se eligen 4 de las 11 reuniones.
greedy.py
def select_intervals(intervals):
"""Return a maximum set of non-overlapping half-open intervals [start, end)."""
chosen = []
last_end = float("-inf")
for start, end in sorted(intervals, key=lambda iv: iv[1]): # earliest end first
if start >= last_end:
chosen.append((start, end))
last_end = end
return chosen
meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
print(select_intervals(meetings)) # [(1, 4), (5, 7), (8, 11), (12, 16)]
python greedy.pySeis capítulos que te llevan desde la instalación hasta las ideas clave de Algoritmos voraces.
Haz preguntas, comparte tu experiencia e intercambia opiniones sobre Algoritmos voraces.
Todavía no hay debates. Empieza el primero.
0 comentarios
Iniciar sesión · Inicia sesión para dejar un comentario.
Sé el primero en comentar.