Greedy Search (Greedy Search) Algorithm in C++- ახსნა, მაგალითი და კოდი

Greedy Search ალგორითმი არის პრობლემის გადაჭრის მიდგომა, რომელიც ყოველთვის ირჩევს საუკეთესო ხელმისაწვდომ ვარიანტს ყოველ ნაბიჯზე გადაწყვეტილების გრძელვადიანი გავლენის გათვალისწინების გარეშე. მიუხედავად იმისა, რომ ეს არ იძლევა გარანტიას გლობალურად ოპტიმალური გადაწყვეტის პოვნის შესახებ, ეს მეთოდი ხშირად მუშაობს სწრაფად და არის მარტივი განხორციელება.

Როგორ მუშაობს

1. ინიციალიზაცია: დაიწყეთ ცარიელი ან საწყისი ხსნარით.
2. ლოკალური ოპტიმალური არჩევანი: თითოეულ საფეხურზე აირჩიეთ ლოკალურად ოპტიმალური არჩევანი ობიექტური ფუნქციის ან განსაზღვრული კრიტერიუმების საფუძველზე.
3. არჩევანის გამოყენება: გამოიყენეთ ოპტიმალური არჩევანი მიმდინარე გადაწყვეტაზე.
4. გაიმეორეთ: გაიმეორეთ ნაბიჯები 2-დან 4-მდე, სანამ უკეთესი ადგილობრივი არჩევანის გაკეთება შეუძლებელია.

მაგალითი: Knapsack Problem

განვიხილოთ Knapsack Problem, სადაც გვაქვს ჩანთა მაქსიმალური წონით და ნივთების სია წონებითა და მნიშვნელობებით. მიზანია შეარჩიოთ ნივთები, რათა მაქსიმალურად გაზარდოთ მთლიანი ღირებულება ჩანთაში. ამ პრობლემისადმი Greedy Search მიდგომა არის ნივთების არჩევა ღირებულებისა და წონის ყველაზე მაღალი თანაფარდობის საფუძველზე.

კოდის მაგალითი 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. ჩვენ ვახარისხებთ ნივთებს კლებადობითი მნიშვნელობის-წონის თანაფარდობის მიხედვით და ვირჩევთ ყველაზე მაღალი თანაფარდობის მქონე ნივთებს, რომლებიც ჯერ კიდევ ჯდება ჩანთის წონის ლიმიტის ფარგლებში.