Los algoritmos voraces, también conocidos como algoritmos codiciosos (greedy algorithms), constituyen una estrategia de diseño algorítmico utilizada para resolver problemas de optimización. La característica fundamental de un algoritmo voraz es que, en cada etapa del proceso de construcción de una solución, toma la decisión que parece mejor en ese momento, sin considerar las implicaciones futuras de esa elección. En otras palabras, busca un óptimo local con la esperanza de que este conduzca a un óptimo global.

Aunque la naturaleza "miópica" de los algoritmos voraces no siempre garantiza la solución óptima, en muchos casos prácticos produce soluciones suficientemente buenas o aproximadas, y lo hace con una eficiencia computacional significativamente mayor que métodos más complejos que buscan una solución exacta. Esto es particularmente útil para problemas que se clasifican como NP-completos, donde encontrar la solución óptima es computacionalmente inviable para entradas grandes. Ejemplos clásicos de algoritmos voraces que sí encuentran la solución óptima incluyen el algoritmo de Dijkstra para el camino más corto, el algoritmo de Prim y Kruskal para el árbol de expansión mínima.

Codificación de Huffman

La codificación de Huffman es un método de compresión de datos sin pérdidas que utiliza un algoritmo voraz para construir un árbol binario. El objetivo es asignar códigos binarios de longitud varible a los caracteres de un alfabeto, de modo que los caracteres más frecuentes tengan códigos más cortos, lo que resulta en una longitud total de bits minimizada para el mensaje codificado. Una propiedad clave de la codificación de Huffman es que es una "codificación de prefijo", lo que significa que ningún código de carácter es prefijo de otro, garantizando una decodificación única.

Construcción del Árbol de Huffman

El algoritmo voraz para construir el árbol de Huffman sigue estos pasos:

1. Calcular la frecuencia de aparición de cada carácter en el texto de entrada.
2. Crear un nodo hoja para cada carácter, asignándole su frecuencia.
3. Insertar todos estos nodos en una cola de prioridad (min-heap), ordenados por frecuencia ascendente.
4. Mientras queden más de un nodo en la cola:
   • Extraer los dos nodos con las frecuencias más bajas.
   • Crear un nuevo nodo interno, cuya frecuencia sea la suma de las frecuencias de los dos nodos extraídos.
   • Asignar los dos nodos extraídos como hijos (izquierdo y derecho) de este nuevo nodo.
   • Insertar el nuevo nodo interno en la cola de prioridad.
5. El último nodo restante en la cola es la raíz del árbol de Huffmen.

Generación de Códigos a partir del Árbol

Una vez construido el árbol, se recorre para asignar los códigos binarios. Convencionalmente, un paso a la izquierda se representa con '0' y un paso a la derecha con '1'. Los códigos se forman concatenando estos bits desde la raíz hasta cada nodo hoja.

Pseudocódigo para la Construcción del Árbol

mientras (colaPrioridad.tamano() > 1) {
    nodoIzquierdo  = colaPrioridad.extraerMinimo();
    nodoDerecho = colaPrioridad.extraerMinimo();
    
    nuevoNodoPadre = crearNodoInterno(); // Un nodo interno sin caracter, solo con frecuencia
    nuevoNodoPadre->frecuencia = nodoIzquierdo->frecuencia + nodoDerecho->frecuencia;
    nuevoNodoPadre->izquierdo = nodoIzquierdo;
    nuevoNodoPadre->derecho = nodoDerecho;
    
    colaPrioridad.insertar(nuevoNodoPadre);
}

arbolHuffman = colaPrioridad.extraerMinimo(); // La raíz del árbol

Pseudocódigo para Generar los Códigos

funcion generarCodigos(nodo* actual, mapa<caracter, string>& tablaCodigos, string& rutaActual) {
    si (actual->esHoja) {
        tablaCodigos[actual->caracter] = rutaActual;
    }
    sino {
        string rutaIzquierda = rutaActual + "0";
        generarCodigos(actual->izquierdo, tablaCodigos, rutaIzquierda);
        
        string rutaDerecha = rutaActual + "1";
        generarCodigos(actual->derecho, tablaCodigos, rutaDerecha);
    }
}

Implementación Completa del Algoritmo de Huffman en C++

#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <unordered_map>
#include <utility>

using namespace std;

// Estructura para representar un nodo en el árbol de Huffman
struct Nodo {
    char caracter;
    int frecuencia;
    Nodo *izquierdo;
    Nodo *derecho;
    bool esHoja; // Indica si el nodo es una hoja (contiene un carácter)

    Nodo(char c = '\0', int freq = 0, Nodo* izq = nullptr, Nodo* der = nullptr, bool hoja = true)
        : caracter(c), frecuencia(freq), izquierdo(izq), derecho(der), esHoja(hoja) {}
};

// Comparador para la cola de prioridad (min-heap)
// Prioriza nodos con menor frecuencia
struct ComparadorNodos {
    bool operator()(const Nodo* a, const Nodo* b) {
        return a->frecuencia > b->frecuencia;
    }
};

// Función recursiva para generar los códigos de Huffman
void generarCodigosDesdeArbol(Nodo* raiz, unordered_map<char, string>& tablaCodigos, string rutaActual) {
    if (raiz == nullptr) {
        return;
    }

    if (raiz->esHoja) { // Si es un nodo hoja, hemos encontrado un carácter y su código
        tablaCodigos[raiz->caracter] = rutaActual;
    } else { // Si es un nodo interno, continuar el recorrido
        generarCodigosDesdeArbol(raiz->izquierdo, tablaCodigos, rutaActual + "0");
        generarCodigosDesdeArbol(raiz->derecho, tablaCodigos, rutaActual + "1");
    }
}

// Función principal para la codificación de Huffman
void codificarHuffman(const string& textoEntrada) {
    // 1. Contar frecuencias de caracteres
    unordered_map<char, int> frecuencias;
    for (char c : textoEntrada) {
        frecuencias[c]++;
    }

    // 2. Crear cola de prioridad con nodos hoja
    priority_queue<Nodo*, vector<Nodo*>, ComparadorNodos> colaPrioridad;
    for (auto const& [caracter, freq] : frecuencias) {
        colaPrioridad.push(new Nodo(caracter, freq));
    }

    // 3. Construir el árbol de Huffman
    while (colaPrioridad.size() > 1) {
        Nodo* izquierdo = colaPrioridad.top();
        colaPrioridad.pop();

        Nodo* derecho = colaPrioridad.top();
        colaPrioridad.pop();

        // Crear un nuevo nodo padre
        Nodo* padre = new Nodo('\0', izquierdo->frecuencia + derecho->frecuencia, izquierdo, derecho, false);
        colaPrioridad.push(padre);
    }

    // El último nodo en la cola es la raíz del árbol de Huffman
    Nodo* raizArbolHuffman = colaPrioridad.top();

    // 4. Generar los códigos de Huffman a partir del árbol
    unordered_map<char, string> tablaCodigos;
    string rutaInicial = "";
    generarCodigosDesdeArbol(raizArbolHuffman, tablaCodigos, rutaInicial);

    // Imprimir los códigos generados
    cout << "Tabla de Codigos de Huffman:" << endl;
    for (auto const& [caracter, codigo] : tablaCodigos) {
        cout << "'" << caracter << "': " << codigo << endl;
    }

    // Liberar memoria del árbol (importante en una aplicación real)
    // Esto requeriría una función de limpieza que recorra el árbol
}


int main() {
    string texto = "abbcccdddd";
    codificarHuffman(texto); // Salida: a:100, b:101, c:11, d:0
    return 0;
}

Consideraciones de Implementación:

• La codificación de Huffman es un algoritmo de dos pasadas: la primera para calcular frecuencias y la segunda para construir el árbol y codificar.
• Para la decodificación, se debe almacenar o transmitir la tabla de códigos junto con los datos comprimidos, lo cual representa una sobrecarga.
• La memoria utilizada por el árbol debe ser gestionada correctamente (liberar nodos).

Problema del Empaquetamiento (Bin Packing)

El problema del empaquetamiento consiste en colocar un conjunto de elementos de diferentes tamaños en un número mínimo de contenedores (o "bins") de capacidad fija. Este problema es NP-duro, por lo que a menudo se utilizan algoritmos voraces para encontrar soluciones aproximadas.

Se distinguen dos variantes principales:

• Algoritmos en Línea (Online): Cada elemento se procesa y se coloca en un contenedor antes de que se conozca el siguiente elemento.
• Algoritmos fuera de Línea (Offline): Todos los elementos se conocen de antemano y pueden ser ordenados o preprocesados antes de comenzar el empaquetamiento.

Algoritmos en Línea

1. Siguiente Ajuste (Next Fit)

Para cada nuevo elemento, se intenta colocarlo en el último contenedor que se utilizó. Si no cabe, se abre un nuevo contenedor y se coloca el elemento allí. Este algoritmo es simple pero no muy eficiente.

#include <iostream>
#include <vector>
#include <numeric> // Para std::iota
#include <algorithm> // Para std::sort

using namespace std;

struct Contenedor {
    int capacidadMaxima;
    int espacioDisponible;
    vector<int> elementosContenidos;

    Contenedor(int capacidad) : capacidadMaxima(capacidad), espacioDisponible(capacidad) {}
};

void siguienteAjuste(vector<Contenedor>& contenedores, int elementoActual, int capacidadBin) {
    if (elementoActual > capacidadBin) {
        cout << "Error: Elemento excede la capacidad maxima del contenedor." << endl;
        return;
    }

    // Si no hay contenedores o el elemento no cabe en el ultimo, crear uno nuevo
    if (contenedores.empty() || contenedores.back().espacioDisponible < elementoActual) {
        contenedores.push_back(Contenedor(capacidadBin));
    }
    
    // El elemento siempre cabe en el ultimo contenedor (ya sea uno nuevo o el existente que tenia espacio)
    contenedores.back().espacioDisponible -= elementoActual;
    contenedores.back().elementosContenidos.push_back(elementoActual);
}

2. Primer Ajuste (First Fit)

Para cada nuevo elemento, se escanea la lista de contenedores existentes y se coloca el elemento en el primer contenedor donde quepa. Si no cabe en ningún contenedor existente, se abre uno nuevo.

void primerAjuste(vector<Contenedor>& contenedores, int elementoActual, int capacidadBin) {
    if (elementoActual > capacidadBin) {
        cout << "Error: Elemento excede la capacidad maxima del contenedor." << endl;
        return;
    }

    for (auto& contenedor : contenedores) {
        if (contenedor.espacioDisponible >= elementoActual) {
            contenedor.espacioDisponible -= elementoActual;
            contenedor.elementosContenidos.push_back(elementoActual);
            return; // Elemento colocado
        }
    }

    // Si no se encontró un contenedor, crear uno nuevo
    contenedores.push_back(Contenedor(capacidadBin));
    contenedores.back().espacioDisponible -= elementoActual;
    contenedores.back().elementosContenidos.push_back(elementoActual);
}

3. Mejor Ajuste (Best Fit)

Para cada nuevo elemento, se busca entre todos los contenedores existentes aquel donde el elemento quepa, y que, al colocarlo, deje el menor espacio restante posible (es decir, el contenedor que quede "más lleno"). Si no cabe en ninguno, se crea un nuevo contenedor.

void mejorAjuste(vector<Contenedor>& contenedores, int elementoActual, int capacidadBin) {
    if (elementoActual > capacidadBin) {
        cout << "Error: Elemento excede la capacidad maxima del contenedor." << endl;
        return;
    }

    int indiceMejorAjuste = -1;
    int espacioRestanteMinimo = capacidadBin + 1; // Mayor que cualquier posible espacio restante

    for (size_t i = 0; i < contenedores.size(); ++i) {
        int espacioDespuesDeAjuste = contenedores[i].espacioDisponible - elementoActual;
        if (espacioDespuesDeAjuste >= 0 && espacioDespuesDeAjuste < espacioRestanteMinimo) {
            espacioRestanteMinimo = espacioDespuesDeAjuste;
            indiceMejorAjuste = i;
        }
    }

    if (indiceMejorAjuste != -1) {
        contenedores[indiceMejorAjuste].espacioDisponible -= elementoActual;
        contenedores[indiceMejorAjuste].elementosContenidos.push_back(elementoActual);
    } else {
        // No se encontró un contenedor existente, crear uno nuevo
        contenedores.push_back(Contenedor(capacidadBin));
        contenedores.back().espacioDisponible -= elementoActual;
        contenedores.back().elementosContenidos.push_back(elementoActual);
    }
}

Algoritmos fuera de Línea

Una mejora común para los algoritmos en línea cuando se dispone de todos los datos es ordenar los elementos antes de aplicar la estrategia de empaquetamiento. El Primer Ajuste Decreciente (First Fit Decreasing) es una variante popular que primero ordena los elementos de mayor a menor tamaño y luego aplica el algoritmo Primer Ajuste.

void primerAjusteDecreciente(vector<Contenedor>& contenedores, vector<int>& elementos, int capacidadBin) {
    // Ordenar elementos en orden descendente
    sort(elementos.begin(), elementos.end(), greater<int>());

    // Aplicar Primer Ajuste a los elementos ya ordenados
    for (int elemento : elementos) {
        primerAjuste(contenedores, elemento, capacidadBin); // Reutiliza la función primerAjuste
    }
}

/*
int main() {
    int capacidadContenedor = 100;
    vector<int> items = {60, 40, 70, 20, 30, 80, 10};
    vector<Contenedor> bins;

    // Inicializar el primer contenedor (para los algoritmos que requieren uno inicial)
    // o simplemente dejar que se creen a medida que sea necesario.
    // Para FFD, el primerAjuste se encargará de crear si bins está vacío.
    
    primerAjusteDecreciente(bins, items, capacidadContenedor);

    cout << "Resultado FFD:" << endl;
    for (size_t i = 0; i < bins.size(); ++i) {
        cout << "Contenedor " << i + 1 << " (Disp: " << bins[i].espacioDisponible << "): ";
        for (int item : bins[i].elementosContenidos) {
            cout << item << " ";
        }
        cout << endl;
    }
    return 0;
}
*/

Problema del Cambio de Monedas

El problema del cambio de monedas consiste en dar una cantidad de dinero utilizando el menor número de monedas posible. En muchos sistemas monetarios (como el euro o el dólar estadounidense), un algoritmo voraz proporciona la solución óptima. Sin embargo, para sistemas de monedas arbitrarios, un enfoque voraz no siempre funciona.

El algoritmo voraz para el cambio de monedas funciona así: para una cantidad dada, se seleccionan tantas monedas del mayor valor posible como quepan sin exceder la cantidad restante. Este proceso se repite con la siguiente moneda de mayor valor hasta que la cantidad a cambiar sea cero.

Ejemplo de Implementación en C++

#include <iostream>
#include <vector>
#include <map>
#include <functional> // Para std::greater

using namespace std;

// Estructura para almacenar la estrategia de cambio
struct EstrategiaCambio {
    // Mapa que almacena el valor de la moneda y la cantidad de esa moneda usada
    // std::greater<int> ordena las claves (valores de moneda) de forma descendente
    map<int, int, greater<int>> monedasContadas;

    // Constructor que inicializa las monedas disponibles (cantidades en 0)
    EstrategiaCambio(initializer_list<int> valoresMonedas) {
        for (int valor : valoresMonedas) {
            monedasContadas[valor] = 0;
        }
    }
};

// Función para calcular el cambio usando un enfoque voraz
void calcularCambio(int cantidadTotal, EstrategiaCambio& estrategia) {
    for (auto& parMoneda : estrategia.monedasContadas) {
        int valorMoneda = parMoneda.first;
        int &cuentaMoneda = parMoneda.second; // Referencia para modificar directamente

        if (cantidadTotal >= valorMoneda) {
            cuentaMoneda = cantidadTotal / valorMoneda; // Cuantas monedas de este valor caben
            cantidadTotal -= cuentaMoneda * valorMoneda; // Reducir la cantidad total restante
        }
        // Si la cantidad total es menor que el valor de la moneda, cuentaMoneda sigue siendo 0
    }
}

// Función para imprimir la estrategia de cambio
void imprimirEstrategia(const EstrategiaCambio& estrategia) {
    cout << "Detalle del cambio:" << endl;
    for (auto const& [valor, cantidad] : estrategia.monedasContadas) {
        if (cantidad > 0) {
            cout << valor << " (unidades): " << cantidad << endl;
        }
    }
    cout << "--------------------" << endl;
}

int main() {
    // Sistema de monedas típico (dólar: 25, 10, 5, 1 centavos)
    EstrategiaCambio s1({25, 10, 5, 1});
    calcularCambio(41, s1); // 41 centavos
    imprimirEstrategia(s1); // Debería dar: 1x25, 1x10, 1x5, 1x1

    // Sistema de monedas donde el voraz NO es óptimo (ejemplo: 1, 3, 4 y queremos 6)
    // El voraz daría: 4, 1, 1 (3 monedas)
    // El óptimo sería: 3, 3 (2 monedas)
    EstrategiaCambio s2({4, 3, 1}); // Asegúrate de que los valores estén en orden descendente si no usas std::greater
    calcularCambio(6, s2);
    imprimirEstrategia(s2);

    return 0;
}

Problema de Programación de Máquinas (Machine Scheduling)

En el problema de programación de máquinas, se busca asignar un conjunto de tareas a un número de máquinas disponibles de manera que se optimice algún criterio, como minimizar el tiempo total de finalización (makespan) o el número de máquinas utilizadas. Un enfoque voraz común es ordenar las tareas por su tiempo de inicio y asignarlas a la máquina que esté disponible más temprano.

Implementación en C++

#include <iostream>
#include <vector>
#include <algorithm> // Para std::sort
#include <queue>     // Para std::priority_queue

using namespace std;

// Estructura para representar una tarea
struct Tarea {
    char identificador;
    int inicio;
    int fin;

    Tarea(char id, int s, int f) : identificador(id), inicio(s), fin(f) {}
};

// Estructura para representar una máquina
struct Maquina {
    size_t identificador;
    int disponibleDesde; // Tiempo en el que la máquina estará disponible
    vector<char> tareasAsignadas; // Lista de tareas asignadas a esta máquina

    Maquina(size_t id = 0, int disp = 0) : identificador(id), disponibleDesde(disp) {}
};

// Comparador para la cola de prioridad de máquinas
// Prioriza máquinas que estarán disponibles antes (menor 'disponibleDesde')
struct ComparadorMaquinas {
    bool operator()(const Maquina& a, const Maquina& b) {
        return a.disponibleDesde > b.disponibleDesde;
    }
};

// Función para planificar tareas en máquinas
vector<Maquina> planificarTareas(vector<Tarea>& tareas) {
    // 1. Ordenar tareas por tiempo de inicio ascendente
    sort(tareas.begin(), tareas.end(), 
        [](const Tarea& lhs, const Tarea& rhs) {
        return lhs.inicio < rhs.inicio;
    });

    // Cola de prioridad para mantener las máquinas ordenadas por su tiempo de disponibilidad
    // La máquina en la parte superior (top) será la que esté disponible más temprano
    priority_queue<Maquina, vector<Maquina>, ComparadorMaquinas> maquinasDisponibles;

    size_t contadorMaquinas = 0; // Para asignar IDs a nuevas máquinas

    // 2. Asignar tareas a máquinas
    for (const Tarea& tareaActual : tareas) {
        Maquina maquinaSeleccionada;

        if (!maquinasDisponibles.empty() && tareaActual.inicio >= maquinasDisponibles.top().disponibleDesde) {
            // Si hay máquinas disponibles y alguna puede empezar la tarea a tiempo
            maquinaSeleccionada = maquinasDisponibles.top();
            maquinasDisponibles.pop();
        } else {
            // No hay máquinas disponibles que puedan empezar a tiempo, crear una nueva máquina
            contadorMaquinas++;
            maquinaSeleccionada.identificador = contadorMaquinas;
            maquinaSeleccionada.disponibleDesde = 0; // Se inicializa para que pueda tomar la primera tarea
        }

        // Asignar la tarea a la máquina seleccionada
        maquinaSeleccionada.tareasAsignadas.push_back(tareaActual.identificador);
        maquinaSeleccionada.disponibleDesde = tareaActual.fin; // Actualizar el tiempo de disponibilidad de la máquina

        maquinasDisponibles.push(maquinaSeleccionada); // Volver a insertar la máquina en la cola
    }

    // Convertir la cola de prioridad a un vector para devolver el resultado
    vector<Maquina> resultadoPlanificacion;
    while (!maquinasDisponibles.empty()) {
        resultadoPlanificacion.push_back(maquinasDisponibles.top());
        maquinasDisponibles.pop();
    }
    // Opcional: ordenar el resultado por ID de máquina si se desea una salida ordenada
    sort(resultadoPlanificacion.begin(), resultadoPlanificacion.end(), [](const Maquina& a, const Maquina& b){
        return a.identificador < b.identificador;
    });

    return resultadoPlanificacion;
}

int main() {
    vector<Tarea> listaTareas = {
        { 'A', 0, 2},
        { 'B', 3, 7 },
        { 'C', 4, 7 },
        { 'D', 9, 11 },
        { 'E', 7, 10 },
        { 'F', 1, 5 },
        { 'G', 6, 8 }
    };

    vector<Maquina> plan = planificarTareas(listaTareas);
    
    cout << "Planificacion de Tareas:" << endl;
    for (const auto& maquina : plan) {
        cout << "Maquina " << maquina.identificador << " (Disponible desde: " << maquina.disponibleDesde << "): ";
        for (char tareaId : maquina.tareasAsignadas) {
            cout << tareaId << " ";
        }
        cout << endl;
    }

    return 0;
}

Problema de la Mochila 0/1

El problema de la mochila 0/1 es un problema clásico de optimización combinatoria. Dada una mochila con una capacidad máxima y un conjunto de ítems, cada uno con un peso y un valor, el objetivo es seleccionar un subconjunto de ítems para maximizar el valor total sin exceder la capacidad de la mochila. El "0/1" indica que cada ítem solo puede ser tomado completamente o no ser tomado en absoluto (no se pueden tomar fracciones de ítems).

A diferencia del problema de la mochila fraccionla (donde se pueden tomar partes de ítems), un enfoque voraz (por ejemplo, tomar ítems por mayor valor/peso o mayor valor individual) no garantiza la solución óptima para el problema de la mochila 0/1. Esto se debe a que la elección localmente óptima de un ítem podría ocupar demasiado espacio, impidiendo la inclusión de otros ítems que, en conjunto, tendrían un valor total mayor. El problema de la mochila 0/1 es un problema NP-completo, y se resuelve típicamente con programación dinámica o algoritmos de ramificación y poda.