อั ลก (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. เราจัดเรียงสิ่งของตามอัตราส่วนมูลค่าต่อน้ำหนักจากมากไปหาน้อย และเลือกสิ่งของที่มีอัตราส่วนสูงสุดซึ่งยังคงพอดีกับน้ำหนักที่จำกัดของกระเป๋าเป้