Алгоритм жадного поиска (Greedy Search) в C++ — объяснение, пример и код

Алгоритм жадного поиска — это подход к решению проблем, который всегда выбирает наилучший доступный вариант на каждом этапе без учета долгосрочных последствий решения. Хотя он не гарантирует нахождения оптимального решения в глобальном масштабе, этот метод часто работает быстро и его легко реализовать.

Как это работает

1. Инициализация: Начните с пустого или начального решения.
2. Локальный оптимальный выбор: на каждом шаге выбирайте локально оптимальный выбор на основе целевой функции или определенных критериев.
3. Применить выбор: применить оптимальный выбор к текущему решению.
4. Повторите: повторите шаги со 2 по 4, пока не будет сделан лучший локальный выбор.

Пример: Knapsack Problem

Рассмотрим Knapsack Problem, где у нас есть рюкзак с максимальным весом и список предметов с весами и ценностями. Цель состоит в том, чтобы выбрать предметы, чтобы максимизировать общую стоимость рюкзака. Подход жадного поиска к этой проблеме заключается в выборе элементов на основе наибольшего отношения ценности к весу.

Пример кода на С++

#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;  
}  

В этом примере мы используем подход жадного поиска для решения задачи Knapsack Problem. Мы сортируем предметы по убыванию отношения стоимости к весу и выбираем предметы с самым высоким соотношением, которые все еще укладываются в пределы веса рюкзака.