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

இந்த எடுத்துக்காட்டில், நாங்கள் பேராசை தேடல் அணுகுமுறையைப் பயன்படுத்துகிறோம் Knapsack Problem. இறங்கு மதிப்பு-எடை-எடை விகிதத்தின் அடிப்படையில் பொருட்களை வரிசைப்படுத்தி, நாப்கின் எடை வரம்பிற்குள் இன்னும் பொருந்தக்கூடிய அதிக விகிதத்துடன் பொருட்களைத் தேர்ந்தெடுக்கிறோம்.