close

(Greedy Search) C++ の 貪欲な検索アルゴリズム- 説明、例、コード

Greedy Search アルゴリズムは、決定の長期的な影響を考慮せずに、各ステップで利用可能な最良のオプションを常に選択する問題解決アプローチです。 全体的に最適なソリューションを見つけることは保証されませんが、この方法は多くの場合迅速に機能し、実装も簡単です。

使い方

  1. 初期化: 空のソリューションまたは初期ソリューションから開始します。
  2. 局所的な最適な選択: 各ステップで、目的関数または定義された基準に基づいて局所的に最適な選択を選択します。
  3. 選択を適用: 現在のソリューションに最適な選択を適用します。
  4. 繰り返し: ローカルでより適切な選択ができなくなるまで、ステップ 2 ～ 4 を繰り返します。

例： Knapsack Problem

を考えてみましょう Knapsack Problem 。ここには、最大重量が記載されたナップザックと、重量と値が記載されたアイテムのリストがあります。 目標は、ナップザック内の合計価値を最大化するアイテムを選択することです。 この問題に対する貪欲な検索アプローチは、最高の価値対重量比に基づいてアイテムを選択することです。

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

この例では、Greedy Search アプローチを使用して を解決します Knapsack Problem。 値と重量の比率の降順に基づいてアイテムを並べ替え、ナップザックの重量制限内に収まる最も高い比率のアイテムを選択します。