Algoritmos Voraces

Los algoritmos voraces son algoritmos genéricos que se usan normalmente para intentar resolver problemas de optimización. Esto es, problemas en los que hay que maximizar o minimizar una función objetivo.

Se parte de un número de elementos de entrada y se van seleccionando o descartando formando el conjunto final de seleccionados que cumplen las restricciones del problema inicial.

No se tiene la posibilidad de dar marcha atrás y rehacer la selección. La solución no tiene porque ser óptima siempre.

Podemos utilizar el siguiente esquema para resolver problemas mediante algoritmos voraces:

alg
   inicializa()
   mientras (No fin() )
      seleccionaYElimina()
      si prometedor():
         anotaEnSolucion()
      fsi
   fmientras
fin

Con la función inicializa() pretendemos establecer las variables necesarias para resolver el problema y asociarles un valor. La función fin() establece el final de las iteraciones sobre el conjunto de elementos de entrada. seleccionaYElimina() es la encargada de elegir el elemento de entrada que se va a procesar y lo elimina del conjunto. prometedor() se encarga de determinar si el elemento elegido añadido al conjunto de salida hace que este mantenga las restricciones del problema. En ese caso se anotaEnSolucion().

Partiendo de este esquema podemos intentar solucionar algunos problemas mediante algoritmos voraces que suelen tener unos ordenes de complejidad bajos.

:wq