Un algoritmo voraz construye una solución paso a paso. En cada etapa mira los candidatos disponibles, escoge el que parece mejor según un criterio local y, si es factible, lo agrega al conjunto solución.

Por eso los voraces son rápidos y simples, pero matemáticamente delicados. No basta con que la estrategia parezca razonable: hay que demostrar que esa regla local siempre conduce a una solución óptima, o aceptar que es solo una heurística.

Un algoritmo voraz no se describe correctamente diciendo “escojo lo mejor”. Hay que especificar qué se escoge, con qué criterio, bajo qué restricciones y cuándo se considera terminada la solución.

El modelo voraz tiene tres movimientos repetidos: seleccionar un candidato, verificar si es prometedor y actualizar la solución parcial. La forma exacta cambia por problema, pero el esqueleto es el mismo.

En esta expresión, xt representa el candidato elegido en el paso t. El símbolo 'arg opt' indica que buscamos el elemento x, dentro del conjunto de candidatos Ct, que maximice o minimice el criterio local definido por el problema.

CSt es el conjunto solución acumulado. Si el candidato xt es factible (no rompe las reglas), se une al conjunto anterior usando el símbolo de unión (U). De lo contrario, la solución se mantiene igual.

Ct+1 define el nuevo conjunto de candidatos para la siguiente etapa. Dependiendo del problema, el candidato xt se descarta (resta de conjuntos) o permanece disponible para ser reutilizado.

algoritmoVoraz(Candidatos) BEGIN
  CS <- {};
  encontrado <- F;

  WHILE (NOT vacio(Candidatos) AND NOT encontrado) DO BEGIN
    x <- seleccionar(Candidatos);

    IF (factible(x, CS)) THEN BEGIN
      CS <- incluir(x, CS);
    END

    Candidatos <- remover(x, Candidatos);

    IF (esSolucion(CS)) THEN BEGIN
      encontrado <- T;
    END
  END

  RETURN CS;
END

El punto débil de los voraces es la correctitud. Implementar la selección local suele ser fácil; demostrar que esa selección local siempre lleva al óptimo global es lo difícil.

El problema pide dar cambio exacto para una cantidad objetivo usando el menor número posible de monedas. La regla voraz natural es tomar en cada paso la moneda más grande que no exceda el restante.

dt es el valor de la moneda elegida. Buscamos el valor máximo (max) en el conjunto de denominaciones D que no supere el dinero restante rt.

rt+1 es la nueva cantidad de dinero que falta por entregar. Se calcula restando el valor de la moneda entregada dt al monto previo.

El conjunto solución se actualiza añadiendo la moneda dt si esta cumple la condición de ser menor o igual al restante.

cambioVoraz(D[n], objetivo) BEGIN
  restante <- objetivo;
  CS <- {};

  WHILE (restante > 0) DO BEGIN
    moneda <- seleccionarMayorFactible(D, restante);

    IF (moneda = -1) THEN BEGIN
      RETURN -1;
    END

    CS <- incluir(moneda, CS);
    restante <- restante - moneda;
  END

  RETURN CS;
END

El problema consiste en recorrer un tablero de ajedrez con un caballo pasando una sola vez por cada casilla. En cada etapa, los candidatos son las casillas alcanzables por el movimiento del caballo.

La función siguiente(v) elige la próxima casilla u que minimiza el 'grado disponible', es decir, la que tiene menos opciones de salida hacia casillas no visitadas.

La ruta del caballo se extiende con la casilla elegida solo si existe al menos un movimiento factible desde la posición actual.

warnsdorff(tablero[n][n], inicio) BEGIN
  actual <- inicio;
  ruta <- {actual};
  marcarVisitada(actual);

  WHILE (longitud(ruta) < n * n) DO BEGIN
    candidatos <- movimientosFactibles(actual, tablero);

    IF (vacio(candidatos)) THEN BEGIN
      RETURN -1;
    END

    siguiente <- candidatoMenorGrado(candidatos, tablero);
    ruta <- incluir(siguiente, ruta);
    marcarVisitada(siguiente);
    actual <- siguiente;
  END

  RETURN ruta;
END

Dado un conjunto de actividades con hora de inicio y fin, se busca seleccionar el máximo número de actividades compatibles, es decir, actividades que no se solapen.

at representa la actividad elegida. Se busca aquella que tenga el tiempo de finalización (fin(a)) más temprano entre todas las que inician después de que termine la última actividad ya aceptada.

El conjunto de actividades seleccionadas CS crece solo si la nueva actividad at es compatible con el horario de la última actividad del conjunto.

seleccionarActividades(inicio[n], fin[n]) BEGIN
  ordenarPorFin(inicio, fin);
  CS <- {};
  ultimoFin <- 0;

  FOR i <- 1 TO n DO BEGIN
    IF (inicio[i] >= ultimoFin) THEN BEGIN
      CS <- incluir(i, CS);
      ultimoFin <- fin[i];
    END
  END

  RETURN CS;
END

Voraz y Programación Dinámica pueden aparecer en problemas de optimización, pero no razonan igual. El voraz se compromete con una decisión local. PD evalúa alternativas y guarda subproblemas.