4.1 Định nghĩa thuật toán tham lam.
Thuật toán tham lam (Greedy Algorithms) là một loại thuật toán mà xây dựng giải pháp bằng cách chọn lựa chọn tối ưu cục bộ ở mỗi bước. Những lựa chọn này được thực hiện dựa trên trạng thái hiện tại và không bị xem xét lại sau này.
Thuật toán tham lam thường được sử dụng để giải quyết các bài toán tối ưu hóa, nơi mà mục tiêu là tối đa hóa hay tối thiểu hóa một đại lượng nhất định.
Nguyên tắc chính của thuật toán tham lam
- Lựa chọn tham lam: Ở mỗi bước, thuật toán chọn lựa chọn cục bộ tốt nhất mà nó nghĩ rằng sẽ dẫn đến giải pháp tối ưu toàn cục.
- Cấu trúc tối ưu: Vấn đề phải có tính chất mà các giải pháp tối ưu cục bộ có thể được kết hợp để có được giải pháp tối ưu toàn cục.
- Tính đơn điệu: Sau khi chọn bước tối ưu cục bộ, giải pháp không nên bị xấu đi bởi các lựa chọn tiếp theo.
Ưu điểm và nhược điểm của thuật toán tham lam
Ưu điểm:
- Dễ dàng thực hiện: Thuật toán tham lam thường dễ hiểu và dễ thực hiện.
- Hiệu quả: Thông thường, chúng hoạt động nhanh hơn so với các thuật toán phức tạp hơn như lập trình động.
Nhược điểm:
- Thiếu tối ưu toàn cầu: Thuật toán tham lam không phải lúc nào cũng dẫn đến giải pháp tối ưu toàn cục.
- Không phải mọi vấn đề đều phù hợp: Chỉ có một số vấn đề cụ thể có thể được giải quyết bằng thuật toán tham lam.
Có một loạt các vấn đề mà giải pháp tốt nhất được đạt được bằng thuật toán tham lam. Sẽ rất hữu ích cho bạn khi biết về những vấn đề như vậy.
4.2 Bài toán đổi tiền.
Bài toán:
Chúng ta có các đồng xu với mệnh giá khác nhau. Cần tìm số lượng đồng xu tối thiểu để trả lại một số tiền nhất định.
Giải pháp:
Luôn luôn chọn đồng xu có mệnh giá lớn nhất nhưng không vượt quá số tiền còn lại.
Độ phức tạp thời gian: O(n), trong đó n là số loại đồng xu.
Mã ví dụ trên Python:
def min_coins(coins, amount):
coins.sort(reverse=True)
count = 0
for coin in coins:
while amount >= coin:
amount -= coin
count += 1
return count
4.3 Bài toán ba lô
Bài toán:
Chúng ta có các vật phẩm với giá trị và trọng lượng đã biết. Chúng ta muốn đặt trong một chiếc ba lô có kích thước cố định các vật phẩm với tổng giá trị lớn nhất có thể.
Trong trường hợp này các vật phẩm có thể được chia thành phần. Ví dụ, chúng ta có thể mua các loại hạt với bất kỳ số gram nào, dù là 1000 gram hay 512 gram.
Giải pháp:
Sắp xếp các vật phẩm theo giá trị đơn vị (giá trị/trọng lượng) và chọn các giá trị đơn vị lớn nhất cho đến khi đầy ba lô.
Độ phức tạp thời gian: O(n log n), trong đó n là số lượng vật phẩm.
Mã ví dụ trên Python:
class Item:
def __init__(self, value, weight):
self.value = value
self.weight = weight
self.ratio = value / weight
def fractional_knapsack(items, capacity):
items.sort(key=lambda x: x.ratio, reverse=True)
total_value = 0.0
for item in items:
if capacity >= item.weight:
total_value += item.value
capacity -= item.weight
else:
total_value += item.ratio * capacity
break
return total_value
4.4 Bài toán phủ đoạn
Bài toán:
Có các đoạn thẳng trên một đường thẳng, được xác định bởi điểm đầu và điểm cuối (x1, x2), và một đoạn mục tiêu. Cần tìm số lượng đoạn nhỏ nhất, để phủ tất cả các điểm của đoạn mục tiêu.
Giải pháp:
Sắp xếp các đoạn theo điểm cuối và chọn đoạn ngắn nhất bao phủ điểm hiện tại.
Độ phức tạp thời gian: O(n log n), trong đó n là số lượng đoạn.
Mã ví dụ trên Python:
def min_segments(segments):
segments.sort(key=lambda x: x[1])
count = 0
end = -float('inf')
for seg in segments:
if seg[0] > end:
end = seg[1]
count += 1
return count
GO TO FULL VERSION