Page 79 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

método codicioso (greedy)

INtroduccIóN

Un juego como el ajedrez solo se gana pensando en las posibles jugadas futuras; por ende, un ju-
gador que solo se focalice en la jugada presente es fácil de vencer. Pero en otros juegos, tales como
Scrabble, es posible hacer un buen juego simplemente realizando una jugada que parezca apropia-
da en el momento, sin preocuparse demasiado en las consecuencias.

Este tipo de comportamiento miope es fácil y conveniente, lo cual genera una estrategia atractiva
para algún tipo de problema. Los algoritmos avaros construyen una solución pieza por pieza, siem-
pre escogiendo la siguiente pieza que ofrece el obvio e inmediato beneficio (Dasgupta, Papadimitriou
y Vazirani, 2008).
La mayoría de estos problemas tienen n entradas y requieren un subconjunto que satisfaga ciertas
restricciones. Cualquier subconjunto que satisfaga estas restricciones se conoce como solución
factible. El problema demanda una solución factible que maximice o minimice una función objetivo
dada. Existe una forma obvia de encontrar un punto factible, pero no necesariamente óptimo.

El método greedy sugiere que uno puede hacer un algoritmo que trabaje por pasos, considerando
una entrada a la vez. En cada paso se realiza una decisión para seguir la ruta que en ese momento
puede maximizar la ganancia o minimizar el costo (nótese que no garantiza el óptimo global, ya que
sus decisiones son locales). El algoritmo 3.1 refleja en pseudocódigo la estrategia greedy:

Algoritmo 3.1. Estrategia general del algoritmo greedy (Horowitz y Sahni, 1978)

73