Cài đặt thuật toán Activity Selection Problem trong lập trình

Thuật toán Activity Selection Problem là một ví dụ kinh điển của bài toán tối ưu hóa trong lập trình và thường được dùng để giải quyết vấn đề lập lịch. Bài toán đưa ra nhiều hoạt động với thời gian bắt đầu và thời gian kết thúc khác nhau, và mục tiêu là chọn một tập hợp các hoạt động để không có hoạt động nào chồng chéo nhau và số lượng hoạt động được chọn là nhiều nhất.

Khái niệm và công thức

Giả sử rằng chúng ta có n hoạt động được đánh số từ 1 đến n. Mỗi hoạt động i có thời gian bắt đầu s[i] và thời gian kết thúc f[i].

Yêu cầu: Tìm tập hợp hoạt động lớn nhất sao cho không có hai hoạt động nào chồng lấn nhau theo thời gian.

Phương pháp giải quyết vấn đề

Một tiếp cận hiệu quả cho bài toán này là sử dụng thuật toán tham lam (greedy algorithm). Ý tưởng cơ bản là chọn hoạt động kết thúc sớm nhất mà không dẫn tới xung đột về thời gian với các hoạt động đã chọn trước đó. Quá trình này lặp lại cho đến khi không còn hoạt động nào có thể được thêm vào.

Các bước thực hiện:

1. Sắp xếp các hoạt động: Đầu tiên, các hoạt động cần được sắp xếp theo thời gian kết thúc của chúng. Sắp xếp này có thể được thực hiện bằng cách sử dụng bất kỳ thuật toán sắp xếp nào có độ phức tạp O(n log n).
2. Chọn hoạt động: Bắt đầu từ hoạt động có thời gian kết thúc sớm nhất và liên tục chọn các hoạt động tiếp theo sao cho thời gian bắt đầu của hoạt động mới lớn hơn hoặc bằng thời gian kết thúc của hoạt động trước đó.

Cài đặt thuật toán bằng ngôn ngữ lập trình Python

Dưới đây là mã nguồn của thuật toán Activity Selection Problem được cài đặt bằng ngôn ngữ lập trình Python:

# Hoạt động được biểu diễn dưới dạng một lớp (class)
class Activity:
    def __init__(self, start, end):
        self.start = start
        self.end = end

def activity_selection(activities):
    # Bước 1: Sắp xếp danh sách hoạt động theo thời gian kết thúc
    sorted_activities = sorted(activities, key=lambda x: x.end)
    
    # Khởi tạo danh sách hoạt động được chọn
    selected_activities = []
    
    # Bước 2: Chọn hoạt động đầu tiên (có thời gian kết thúc sớm nhất)
    selected_activities.append(sorted_activities[0])
    last_selected_activity = sorted_activities[0]
    
    # Bước 3: Duyệt qua các hoạt động còn lại và chọn những hoạt động không chồng chéo
    for i in range(1, len(sorted_activities)):
        if sorted_activities[i].start >= last_selected_activity.end:
            selected_activities.append(sorted_activities[i])
            last_selected_activity = sorted_activities[i]
    
    return selected_activities

# Ví dụ sử dụng
activities = [
    Activity(1, 2),
    Activity(3, 4),
    Activity(0, 6),
    Activity(5, 7),
    Activity(8, 9),
    Activity(5, 9)
]

selected_activities = activity_selection(activities)
print("Các hoạt động được chọn:")
for activity in selected_activities:
    print(f'Hoạt động bắt đầu: {activity.start}, kết thúc: {activity.end}')

Giải thích mã nguồn:

1. Lớp Activity: Định nghĩa một lớp Activity với hai thuộc tính là thời gian bắt đầu (start) và thời gian kết thúc (end).
2. Hàm activity_selection: Chứa logic của thuật toán tham lam:
   • Sắp xếp danh sách hoạt động dựa trên thời gian kết thúc.
   • Khởi tạo danh sách selected_activities với hoạt động đầu tiên trong danh sách đã sắp xếp.
   • Lặp qua danh sách hoạt động và thêm vào selected_activities những hoạt động có thời gian bắt đầu lớn hơn hoặc bằng thời gian kết thúc của hoạt động cuối cùng trong selected_activities.

Kết luận

Thuật toán Activity Selection Problem là một ví dụ hoàn hảo về cách áp dụng thuật toán tham lam để giải quyết các bài toán tối ưu hóa. Việc nắm rõ cách thức cài đặt và tối ưu hóa thuật toán này là vô cùng hữu ích, không chỉ trong các cuộc thi lập trình mà còn trong thực tế khi chúng ta cần giải quyết các bài toán liên quan đến quản lý thời gian và lập lịch.