Giải thuật Tìm kiếm Tham lam (Greedy Search) trong C++ - Giải thích, Ví dụ và Mã nguồn

Thuật toán Tìm kiếm Tham lam là một phương pháp giải quyết vấn đề bằng cách luôn chọn lựa lựa chọn tốt nhất tại mỗi bước, mà không xem xét tác động dài hạn của quyết định. Mặc dù không đảm bảo tìm ra giải pháp tối ưu toàn cục, tuy nhiên phương pháp này thường hoạt động nhanh chóng và dễ cài đặt.

Cách hoạt động

1. Khởi tạo: Bắt đầu với một giải pháp trống hoặc khởi tạo ban đầu.
2. Chọn tối ưu cục bộ: Tại mỗi bước, chọn lựa lựa chọn tối ưu nhất dựa trên hàm mục tiêu hoặc tiêu chí xác định.
3. Áp dụng lựa chọn: Thực hiện lựa chọn tối ưu vào giải pháp hiện tại.
4. Lặp lại: Lặp lại quá trình từ bước 2 đến khi không thể thực hiện lựa chọn tốt hơn nữa.

Ví dụ: Bài toán Túi lựa chọn (Knapsack Problem)

Xét bài toán Túi lựa chọn, trong đó chúng ta có một túi có trọng lượng tối đa và một danh sách các vật phẩm với trọng lượng và giá trị. Mục tiêu là chọn các vật phẩm để đạt được giá trị tối đa trong túi. Một phương pháp Tìm kiếm Tham lam là chọn các vật phẩm theo tỷ lệ giá trị/trọng lượng cao nhất.

Mã nguồn ví dụ trong 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;
}

Trong ví dụ này, chúng ta sử dụng phương pháp Tìm kiếm Tham lam để giải quyết bài toán Túi lựa chọn. Chúng ta sắp xếp các vật phẩm theo tỷ lệ giá trị/trọng lượng giảm dần và chọn các vật phẩm có tỷ lệ này cao nhất mà vẫn vừa túi.