Algoritmo de búsqueda codicioso (Greedy Search) en C++- Explicación, ejemplo y código

El algoritmo Greedy Search es un enfoque de resolución de problemas que siempre elige la mejor opción disponible en cada paso sin considerar el impacto a largo plazo de la decisión. Si bien no garantiza encontrar la solución globalmente óptima, este método a menudo funciona rápidamente y es fácil de implementar.

Cómo funciona

1. Inicialización: Comience con una solución vacía o inicial.
2. Elección óptima local: en cada paso, elija la opción óptima localmente en función de la función objetivo o los criterios definidos.
3. Aplicar opción: aplica la opción óptima a la solución actual.
4. Repita: repita los pasos 2 a 4 hasta que no se pueda hacer una mejor elección local.

Ejemplo: Knapsack Problem

Considere el Knapsack Problem, donde tenemos una mochila con un peso máximo y una lista de artículos con pesos y valores. El objetivo es seleccionar artículos para maximizar el valor total en la mochila. Un enfoque de Greedy Search para este problema es seleccionar elementos en función de la mayor relación valor-peso.

Ejemplo de código en C++

#include <iostream>  
#include <vector>  
#include <algorithm>  
  
struct Item {  
    int weight;  
    int value;  
};  
  
bool compare(Item a, Item b) {  
    double ratioA =(double)a.value / a.weight;  
    double ratioB =(double)b.value / b.weight;  
    return ratioA > ratioB;  
}  
  
double greedyKnapsack(int maxWeight, std::vector<Item>& items) {  
    double totalValue = 0.0;  
  
    std::sort(items.begin(), items.end(), compare);  
  
    for(const Item& item: items) {  
        if(maxWeight >= item.weight) {  
            totalValue += item.value;  
            maxWeight -= item.weight;  
        } else {  
            totalValue +=(double)maxWeight / item.weight * item.value;  
            break;  
        }  
    }  
  
    return totalValue;  
}  
  
int main() {  
    int maxWeight = 10;  
    std::vector<Item> items = {{2, 6}, {5, 12}, {3, 8}, {7, 14}, {4, 10}};  
    double maxValue = greedyKnapsack(maxWeight, items);  
  
    std::cout << "Max value in knapsack: " << maxValue << std::endl;  
  
    return 0;  
}  

En este ejemplo, usamos el enfoque de búsqueda codiciosa para resolver el problema Knapsack Problem. Clasificamos los artículos en función de la relación valor-peso descendente y seleccionamos los artículos con la relación más alta que aún se ajustan al límite de peso de la mochila.