Capítulo 17. Algoritmos Greedy (Parte II)

Presentaremos en este capítulo la forma general en formato pseudocódigo de los algoritmos Greedy.

GREEDY
Entrada: C -> conjunto de candidatos.
Salida:  S -> solución del problema.

     mientras C <> vacío y no esSolucion(S)
          x <- Seleccionar(C)
          C <- C\{x}          
          si esFactible(S U {x})
              S <- S U {x} 
          fin si
     fin mientras
     si esSolucion(S) 
         devolver S
     fin si
     sino 
         devolver No hay solución
     fin si
fin GREEDY

Al tratarse de operaciones entre conjuntos vale aclarar la notación:

• C\{x} quiere decir que al conjunto de candidatos C se le quita el elemento x (ya que 'x' había sido seleccionado en el paso anterior).
• S U {x} significa que al conjunto de solución se le agrega el elemento x.

En los siguientes capítulos nos dedicaremos a estudiar ejemplos de aplicación de esta técnica de diseño de algoritmos.