Page 79 - Revista ingeniantes 2 No1 Vol 1 Interactiva
P. 79
Revista Ingeniantes Año 2 No. 1 Vol. 1
INTRODUCCIÓN Dado un conjunto finito de entradas C, un algoritmo
Los algoritmos de planificación son de vital importancia voraz devuelve un conjunto S (seleccionados) tal que
en muchas áreas prácticas del conocimiento, ya que nos S ⊆ C y que además cumple con las restricciones del
permiten prever la administración de un conjunto de re- problema inicial. A cada conjunto S que satisfaga las
cursos que por lo general son limitados o en su defecto restricciones se le suele denominar prometedor, y si
su uso se encuentra restringido a algún tipo de norma este además logra que la función objetivo se minimi-
que no se puede romper. ce o maximice (según corresponda). Diremos que S
En las ciencias computacionales el estudio de este tipo es una solución óptima.
de problemas ha dado lugar a diferentes interpretacio- Elementos de los que consta la técnica:
nes algorítmicas para su solución tratando de optimizar El conjunto C de candidatos, entradas del problema.
los recursos computacionales primarios como son el • Función solución. Comprueba, en cada paso, si el
tiempo de respuesta y la utilización de la memoria prin-
cipal. subconjunto actual de candidatos elegidos forma
A continuación se realiza una breve descripción de las una solución (no importa si es ´ óptima o no lo es).
técnicas estudiadas haciendo hincapié en que no son las • Función de selección. Informa de todas las solu-
únicas formas de abordad este tipo de problemas. ciones cuál es el elemento más prometedor para
1.1 Algoritmos Voraces completar la solución. Este no puede haber sido
En el área de la Informática este tipo de Algoritmos se escogido con anterioridad. Cada elemento es
consideran una técnica de diseño general a pesar del considerado una sola vez. Luego, puede ser re-
hecho de que es aplicable únicamente a problemas de chazado o aceptado y pertenecerá a C \ S.
optimización. El enfoque voraz sugiere la construcción • Función de factibilidad. Informa si a partir de un
de una solución a través de una secuencia de pasos, conjunto se puede llegar a una solución. Lo apli-
donde en cada ampliación se obtiene una solución par- caremos al conjunto de seleccionados unido con
cialmente construida obtenida hasta el momento, esto el elemento más prometedor.
continua hasta que se alcanza una solución completa al • Función objetivo. Es aquella que queremos maxi-
problema. mizar o minimizar, el núcleo del problema. [3].
En cada paso, y este es el punto central de esta técnica, 1.2. Programación Dinámica
la opción elegida debe ser: La programación dinámica es una técnica de diseño
• Factible, es decir, tiene que satisfacer las limitacio- de algoritmos con una historia bastante interesante.
Fue inventada por el matemático Richard Bellman,
nes del problema en la década de 1950 como un método general para
• Localmente óptima, es decir, tiene que ser la mejor la optimización de los procesos de toma de varias
etapas. Por lo tanto, la palabra “programación” en el
opción local entre todas las opciones viables dispo- nombre de esta técnica es sinónimo de “planificación”
nibles en ese paso y no se refiere a la programación de computadoras.
• Irrevocable, es decir, una vez hecho, se no se puede La programación dinámica es una técnica para resol-
cambiar en etapas posteriores del algoritmo ver problemas utilizando subproblemas, la programa-
Estos requisitos explican el nombre de la técnica: en ción dinámica sugiere la solución de cada uno de los
cada paso, sugiere un robo “codiciosos” de la mejor al- subproblemas más pequeños sólo una vez y regis-
ternativa disponible en la esperanza de que una secuen- trando los resultados en una tabla de la que a con-
cia de opciones localmente óptimas producirá una solu- tinuación se puede obtener la solución al problema
ción óptima para todo el problema. original.
Como regla general, los algoritmos voraces son intuitiva- Si uno usa la versión bottom-up clásica de la progra-
mente atractivos y simples. Dado un problema de optimi- mación dinámica o su variación up-bottom, el paso
zación, por lo general es fácil de encontrar la manera de crucial en el diseño de un algoritmo sigue siendo el
proceder de una manera voraz, posiblemente después mismo: derivar una recurrencia relacionada al proble-
de considerar algunas pequeñas instancias del proble- ma de las soluciones a sus subproblemas más pe-
ma. Lo que es generalmente es más difícil, es demos- queños.
trar que un algoritmo voraz produce una solución óptima A pesar de su aplicabilidad cuando se aplica a un
(cuando lo hace). Una de las formas más comunes de problema en particular necesita ser comprobada, por
hacer esto es el uso de la inducción matemática, que supuesto, por lo general dicha comprobación no es la
muestra que una solución parcialmente construida ob- dificultad principal en el desarrollo de una programa-
tenida por el algoritmo voraz en cada iteración se puede ción basada en Algoritmos dinámicos. [2].
extender a una solución óptima al problema. [1]
73
