Algoritmo de pesquisa gananciosa (Greedy Search) em C++- explicação, exemplo e código

O algoritmo Greedy Search é uma abordagem de resolução de problemas que sempre escolhe a melhor opção disponível em cada etapa sem considerar o impacto de longo prazo da decisão. Embora não garanta encontrar a solução ideal globalmente, esse método geralmente funciona rapidamente e é simples de implementar.

Como funciona

1. Inicialização: Comece com uma solução vazia ou inicial.
2. Escolha ótima local: Em cada etapa, escolha a escolha ótima local com base na função objetivo ou critérios definidos.
3. Aplicar escolha: aplica a escolha ideal à solução atual.
4. Repita: itere pelas etapas 2 a 4 até que nenhuma escolha local melhor possa ser feita.

Exemplo: Knapsack Problem

Considere o Knapsack Problem, onde temos uma mochila com peso máximo e uma lista de itens com pesos e valores. O objetivo é selecionar itens para maximizar o valor total da mochila. Uma abordagem de pesquisa gananciosa para esse problema é selecionar itens com base na maior relação valor/peso.

Exemplo de código em 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;  
}  

Neste exemplo, usamos a abordagem Greedy Search para resolver o problema Knapsack Problem. Classificamos os itens com base na relação valor/peso decrescente e selecionamos os itens com a proporção mais alta que ainda cabem no limite de peso da mochila.