vothuaphucnguyen
White---
-
31/08/2016
-
8
-
6 bài viết
Giới thiệu về thuật toán tham lam - Greedy Algorithm(Phần 1)
Tham ăn hiểu một cách dân gian là: trong một mâm có nhiều món ăn, món nào ngon nhất ta sẽ ăn trước và ăn cho hết món đó thì chuyển sang món ngon thứ hai, lại ăn hết món ngon thứ hai này và chuyển sang món ngon thứ ba…
Phương pháp tham ăn (greedy method) là một chến lược thiết kế thuật toán thường được sử dụng để giải quyết các bài toán tối ưu.
Có rất nhiều vấn đề cần giải quyết, có thể quy về vấn đề chính sau đây: Cho trước một tập A các đối tượng nào đó, đòi hỏi phải chọn ra một tập con S các đối tượng thỏa mãn một số điều kiện nào đó. Bất kỳ một tập con S nào của A thỏa mãn các yêu cầu đặt ra được gọi là nghiệm chấp nhận được của bài toán. Một hàm mục tiêu gắn mỗi nghiệm chấp nhận được với một giá trị nào đó. Một nghiệm chấp nhận được mà tại đó hàm mục tiêu có giá trị lớn nhất (hoặc nhỏ nhất) được gọi là nghiệm tối ưu.
Ý tưởng:
Ta xây dựng tập S dần dần từng bước, bắt đầu từ tập rỗng. Tại mỗi bước, ta sẽ chọn một phần tử “tốt nhất” trong các phần tử còn lại của A để đưa vào S. Việc lựa chọn một phần tử như thế ở mỗi bước được hướng dẫn bởi hàm chọn. Phần tử được chọn sẽ bị loại khỏi tập A. Nếu khi thêm phần tử được chọn vào tập S mà S vẫn còn thỏa mãn các điều kiện của bài toán thì ta mở rộng S bằng cách thêm vào phần tử được chọn.
Đặc điểm:
Mục đích xây dựng bài toán giải nhiều lớp bài toán khác nhau, đưa ra quyết định dựa ngay vào thuật toán đang có, và trong tương lai sẽ không xem xét lại quyết định trong quá khứ. Vì vậy thuật toán dễ đề xuất, thời gian tính nhanh nhưng thường không cho kết quả đúng.
Lời giải cần tìm có thể mô tả như là bộ gồm hữu hạn các thành phần thoả mãn điều kiện nhất định, ta phải giải quyết bài toán một cách tối ưu.
Để xây dựng lời giải ta có một tập các ứng cử viên
Xuất phát từ lời giải rỗng, thực hiện việc xây dựng lời giải từng bước, mỗi bước sẽ lựa chọn trong tập ứng cử viên để bổ sung vào lời giải hiện có.
Xây dựng một hàm nhận biết tính chấp nhận được của lời giải hiện có -> Hàm Solution(S) -> Kiểm tra thoả mãn điều kiện chưa.
Một hàm quan trọng nữa: Select(A) cho phép tại mỗi bước của thuật toán lựa chọn ứng cử viên có triển vọng nhất để bổ xung vào lời giải hiện có -> dựa trên căn cứ vào ảnh hưởng của nó vào hàm mục tiêu, thực tế là ứng cử viên đó phải giúp chúng ta phát triển tiếp tục bài toán.
Lược đồ tổng quát:
Trong lược đồ tổng quát trên. Select là hàm chọn, nó cho phép ta chọn ra từ tập A một phần tử được xem là tốt nhất, nhiều hứa hẹn nhất là thành viên của nghiệm.
Ta có thể dễ dàng thấy tại sao các thuật toán như thế được gọi là “ tham ăn”. Tại mỗi bước, nó chọn “miếng ngon nhất” (được xác định bởi hàm chọn), nếu thấy có thể nuốt được (có thể đưa vào nghiệm) nó sẽ xơi ngay, nếu không nó sẽ bỏ đi, sau này không bao giờ xem xét lại.
Cần nhấn mạnh rằng, thuật toán tham ăn trong một số bài toán, nếu xây dựng được hàm chọn thích hợp có thể cho nghiệm tối ưu. Trong nhiều bài toán, thuật toán tham ăn chỉ tìm được nghiệm gần đúng với nghiệm tối ưu.
Note : Trong phần sau mình đưa ví dụ cụ thể và nói kĩ hơn về thuật toán này.
Phương pháp tham ăn (greedy method) là một chến lược thiết kế thuật toán thường được sử dụng để giải quyết các bài toán tối ưu.
Có rất nhiều vấn đề cần giải quyết, có thể quy về vấn đề chính sau đây: Cho trước một tập A các đối tượng nào đó, đòi hỏi phải chọn ra một tập con S các đối tượng thỏa mãn một số điều kiện nào đó. Bất kỳ một tập con S nào của A thỏa mãn các yêu cầu đặt ra được gọi là nghiệm chấp nhận được của bài toán. Một hàm mục tiêu gắn mỗi nghiệm chấp nhận được với một giá trị nào đó. Một nghiệm chấp nhận được mà tại đó hàm mục tiêu có giá trị lớn nhất (hoặc nhỏ nhất) được gọi là nghiệm tối ưu.
Ý tưởng:
Ta xây dựng tập S dần dần từng bước, bắt đầu từ tập rỗng. Tại mỗi bước, ta sẽ chọn một phần tử “tốt nhất” trong các phần tử còn lại của A để đưa vào S. Việc lựa chọn một phần tử như thế ở mỗi bước được hướng dẫn bởi hàm chọn. Phần tử được chọn sẽ bị loại khỏi tập A. Nếu khi thêm phần tử được chọn vào tập S mà S vẫn còn thỏa mãn các điều kiện của bài toán thì ta mở rộng S bằng cách thêm vào phần tử được chọn.
Đặc điểm:
Mục đích xây dựng bài toán giải nhiều lớp bài toán khác nhau, đưa ra quyết định dựa ngay vào thuật toán đang có, và trong tương lai sẽ không xem xét lại quyết định trong quá khứ. Vì vậy thuật toán dễ đề xuất, thời gian tính nhanh nhưng thường không cho kết quả đúng.
Lời giải cần tìm có thể mô tả như là bộ gồm hữu hạn các thành phần thoả mãn điều kiện nhất định, ta phải giải quyết bài toán một cách tối ưu.
Để xây dựng lời giải ta có một tập các ứng cử viên
Xuất phát từ lời giải rỗng, thực hiện việc xây dựng lời giải từng bước, mỗi bước sẽ lựa chọn trong tập ứng cử viên để bổ sung vào lời giải hiện có.
Xây dựng một hàm nhận biết tính chấp nhận được của lời giải hiện có -> Hàm Solution(S) -> Kiểm tra thoả mãn điều kiện chưa.
Một hàm quan trọng nữa: Select(A) cho phép tại mỗi bước của thuật toán lựa chọn ứng cử viên có triển vọng nhất để bổ xung vào lời giải hiện có -> dựa trên căn cứ vào ảnh hưởng của nó vào hàm mục tiêu, thực tế là ứng cử viên đó phải giúp chúng ta phát triển tiếp tục bài toán.
Lược đồ tổng quát:
Trong lược đồ tổng quát trên. Select là hàm chọn, nó cho phép ta chọn ra từ tập A một phần tử được xem là tốt nhất, nhiều hứa hẹn nhất là thành viên của nghiệm.
Ta có thể dễ dàng thấy tại sao các thuật toán như thế được gọi là “ tham ăn”. Tại mỗi bước, nó chọn “miếng ngon nhất” (được xác định bởi hàm chọn), nếu thấy có thể nuốt được (có thể đưa vào nghiệm) nó sẽ xơi ngay, nếu không nó sẽ bỏ đi, sau này không bao giờ xem xét lại.
Cần nhấn mạnh rằng, thuật toán tham ăn trong một số bài toán, nếu xây dựng được hàm chọn thích hợp có thể cho nghiệm tối ưu. Trong nhiều bài toán, thuật toán tham ăn chỉ tìm được nghiệm gần đúng với nghiệm tối ưu.
Note : Trong phần sau mình đưa ví dụ cụ thể và nói kĩ hơn về thuật toán này.
Chỉnh sửa lần cuối bởi người điều hành:
