Giải thuật tham lam (Greedy Algorithm)

30-09-2024
Toanngo92
0 Comments

Thuật toán tham lam (Greedy Algorithm) là một phương pháp giải quyết bài toán bằng cách chọn lựa phương án tốt nhất tại mỗi bước trong quá trình giải quyết vấn đề, mà không quan tâm đến những lựa chọn có thể dẫn đến kết quả tốt hơn trong tương lai. Điều này có nghĩa là thuật toán chỉ quan tâm đến lợi ích cục bộ tại mỗi bước với hi vọng rằng kết quả cuối cùng sẽ là tối ưu hoặc đủ tốt.

Mục lục

Đặc điểm của thuật toán tham lam:

Chọn lựa tại mỗi bước: Ở mỗi bước, thuật toán tham lam luôn chọn phương án tốt nhất có thể tại thời điểm đó, mà không cần quan tâm đến các bước tiếp theo.
Không quay lui: Một khi đã chọn một phương án tại một bước, thuật toán sẽ không thay đổi hoặc quay lại để thử các lựa chọn khác (không quay lui).
Tính cục bộ: Quyết định của thuật toán chỉ dựa trên thông tin tại bước hiện tại, không sử dụng thông tin về toàn bộ bài toán hay các bước sau.

Điều kiện để thuật toán tham lam hoạt động hiệu quả:

Tính tối ưu cục bộ dẫn đến tối ưu toàn cục: Khi bài toán có đặc điểm là các quyết định cục bộ tối ưu tại mỗi bước có thể dẫn đến kết quả tối ưu toàn cục, thuật toán tham lam sẽ cho ra kết quả đúng. Đây là điều kiện tiên quyết để thuật toán tham lam có thể đảm bảo giải quyết bài toán một cách chính xác.
Bài toán có tính chất tham lam: Để thuật toán tham lam hoạt động hiệu quả, bài toán phải có tính chất tham lam, nghĩa là luôn có một lựa chọn cục bộ tốt nhất tại mỗi bước dẫn đến giải pháp tối ưu toàn cục.

Các bước cơ bản của thuật toán tham lam:

Khởi tạo: Bắt đầu từ một trạng thái hoặc vị trí ban đầu của bài toán.
Chọn lựa tham lam: Tại mỗi bước, chọn lựa phương án tốt nhất mà không quan tâm đến các bước tiếp theo.
Lặp lại: Lặp lại quá trình này cho đến khi đạt được một kết quả cuối cùng.
Dừng: Thuật toán dừng khi đã đạt được lời giải hoàn chỉnh.

Ví dụ về thuật toán tham lam:

1. Bài toán đồng xu (Coin Change Problem):

Giả sử bạn cần trả một số tiền bằng cách sử dụng số lượng đồng xu ít nhất, với các mệnh giá đồng xu có sẵn là {1, 5, 10, 25}.

Chiến lược tham lam: Tại mỗi bước, bạn luôn chọn đồng xu có giá trị lớn nhất mà không vượt quá số tiền cần trả. Ví dụ: Để trả 37 đơn vị tiền:
Chọn đồng xu 25 → Còn lại 12.
Chọn đồng xu 10 → Còn lại 2.
Chọn đồng xu 1 hai lần → Hoàn thành.

2. Bài toán hoạt động (Activity Selection Problem):

Cho một tập hợp các hoạt động, mỗi hoạt động có thời gian bắt đầu và kết thúc. Mục tiêu là chọn số lượng hoạt động lớn nhất sao cho chúng không trùng lặp về thời gian.

Chiến lược tham lam: Tại mỗi bước, luôn chọn hoạt động có thời gian kết thúc sớm nhất và không xung đột với các hoạt động đã chọn trước đó.

Hạn chế của thuật toán tham lam:

Thuật toán tham lam không phải lúc nào cũng cho kết quả tối ưu. Trong một số bài toán, mặc dù lựa chọn cục bộ là tốt nhất, nhưng tổng thể giải pháp lại không tối ưu.
Không thể quay lui: Khi một quyết định đã được đưa ra, thuật toán tham lam không thể quay lại để thử phương án khác, điều này có thể dẫn đến việc không tìm được giải pháp tối ưu trong một số bài toán.

Ví dụ về bài toán mà thuật toán tham lam không hoạt động tốt:

Bài toán ba lô (Knapsack Problem):

Giả sử bạn có một ba lô với sức chứa tối đa và một số đồ vật với giá trị và trọng lượng khác nhau. Mục tiêu là chọn đồ vật sao cho tổng giá trị là lớn nhất mà không vượt quá sức chứa của ba lô.

Thuật toán tham lam: Luôn chọn đồ vật có giá trị cao nhất trước. Tuy nhiên, điều này không luôn dẫn đến lời giải tối ưu, vì có thể sau đó bạn sẽ không còn đủ sức chứa để chọn các đồ vật nhẹ nhưng có giá trị lớn.

Thuật toán tham lam là một kỹ thuật đơn giản và nhanh, thích hợp cho các bài toán có đặc tính tham lam, nhưng không phải lúc nào cũng đảm bảo giải pháp tối ưu. Nó được sử dụng phổ biến trong các bài toán về tối ưu hóa và là nền tảng cho nhiều giải thuật khác trong lập trình.

Dưới đây là một số ví dụ về việc áp dụng thuật toán tham lam trong lập trình, với các bài toán điển hình sử dụng chiến lược tham lam.

1. Bài toán hoạt động (Activity Selection Problem)

Bài toán này yêu cầu chọn ra số lượng hoạt động lớn nhất mà không trùng thời gian với nhau, từ một danh sách các hoạt động, mỗi hoạt động có thời gian bắt đầu và kết thúc.

Ví dụ cài đặt bằng Java:

import java.util.Arrays;
import java.util.Comparator;

class Activity {
    int start, end;

    public Activity(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

public class ActivitySelection {

    public static void main(String[] args) {
        Activity[] activities = {
            new Activity(1, 3),
            new Activity(2, 5),
            new Activity(4, 7),
            new Activity(1, 8),
            new Activity(5, 9),
            new Activity(8, 10)
        };

        // Sắp xếp theo thời gian kết thúc tăng dần
        Arrays.sort(activities, Comparator.comparingInt(a -> a.end));

        // Chọn hoạt động đầu tiên
        int count = 1;  // Đếm hoạt động đã chọn
        int lastEnd = activities[0].end;
        System.out.println("Selected activity: (" + activities[0].start + ", " + activities[0].end + ")");

        // Duyệt qua các hoạt động và chọn hoạt động không trùng thời gian
        for (int i = 1; i < activities.length; i++) {
            if (activities[i].start >= lastEnd) {
                System.out.println("Selected activity: (" + activities[i].start + ", " + activities[i].end + ")");
                lastEnd = activities[i].end;
                count++;
            }
        }

        System.out.println("Total number of selected activities: " + count);
    }
}

Giải thích:

Thuật toán tham lam ở đây là: tại mỗi bước, luôn chọn hoạt động có thời gian kết thúc sớm nhất và không trùng với các hoạt động đã chọn trước đó.
Hoạt động được sắp xếp theo thời gian kết thúc tăng dần, sau đó chúng ta chọn từng hoạt động dựa trên tiêu chí này.

2. Bài toán đồng xu (Coin Change Problem)

Bài toán yêu cầu tìm số lượng đồng xu ít nhất để tạo thành một số tiền từ danh sách các mệnh giá đồng xu có sẵn.

Ví dụ cài đặt bằng Java:

import java.util.Arrays;

public class CoinChange {

    public static void main(String[] args) {
        int[] coins = {1, 5, 10, 25};  // Các mệnh giá đồng xu
        int amount = 37;  // Số tiền cần đổi
        Arrays.sort(coins);  // Sắp xếp các đồng xu theo thứ tự tăng dần

        int count = 0;  // Biến đếm số lượng đồng xu
        int i = coins.length - 1;  // Bắt đầu từ đồng xu lớn nhất

        System.out.println("Amount: " + amount);
        System.out.print("Coins used: ");

        while (amount > 0) {
            if (coins[i] <= amount) {
                amount -= coins[i];  // Trừ giá trị đồng xu ra khỏi số tiền
                System.out.print(coins[i] + " ");
                count++;
            } else {
                i--;  // Chuyển sang đồng xu nhỏ hơn
            }
        }

        System.out.println("\nTotal coins used: " + count);
    }
}

Giải thích:

Thuật toán tham lam: Luôn chọn đồng xu có giá trị lớn nhất mà không vượt quá số tiền cần đổi.
Trong ví dụ này, số tiền cần đổi là 37, và thuật toán tham lam sẽ chọn đồng xu có mệnh giá 25, sau đó chọn tiếp đồng xu 10 và cuối cùng là 2 đồng xu 1.

3. Bài toán ba lô phân số (Fractional Knapsack Problem)

Bài toán yêu cầu chọn các vật phẩm sao cho giá trị tổng là lớn nhất, nhưng với điều kiện ba lô có một dung lượng giới hạn. Bài toán này cho phép chia vật phẩm thành phần nhỏ để đưa vào ba lô.

Ví dụ cài đặt bằng Java:

import java.util.Arrays;
import java.util.Comparator;

class Item {
    int weight;
    int value;

    public Item(int weight, int value) {
        this.weight = weight;
        this.value = value;
    }
}

public class FractionalKnapsack {

    public static void main(String[] args) {
        Item[] items = {
            new Item(10, 60),
            new Item(20, 100),
            new Item(30, 120)
        };
        int capacity = 50;  // Dung lượng của ba lô

        // Sắp xếp các vật phẩm theo tỷ lệ giá trị/trọng lượng giảm dần
        Arrays.sort(items, Comparator.comparingDouble(i -> -(double)i.value / i.weight));

        double totalValue = 0.0;  // Tổng giá trị tối đa

        for (Item item : items) {
            if (capacity - item.weight >= 0) {
                // Nếu còn đủ dung lượng, lấy toàn bộ vật phẩm
                capacity -= item.weight;
                totalValue += item.value;
                System.out.println("Took full item with weight: " + item.weight + ", value: " + item.value);
            } else {
                // Nếu không đủ dung lượng, chỉ lấy phần của vật phẩm
                double fraction = (double)capacity / item.weight;
                totalValue += item.value * fraction;
                System.out.println("Took " + (fraction * 100) + "% of item with weight: " + item.weight + ", value: " + item.value);
                break;
            }
        }

        System.out.println("Total value obtained: " + totalValue);
    }
}

Giải thích:

Thuật toán tham lam: Ở mỗi bước, chúng ta chọn vật phẩm có tỷ lệ giá trị trên trọng lượng lớn nhất để đưa vào ba lô. Nếu không đủ chỗ để lấy toàn bộ vật phẩm, chúng ta chỉ lấy một phần của nó.
Đây là bài toán cho phép phân chia vật phẩm, và chiến lược tham lam giúp đạt giá trị tối đa với dung lượng hạn chế của ba lô.