Dynamic Programming (Kĩ thuật quy hoạch động)

<Just Type to Remember>

<Theo “Kỹ thuật thiết kế giải thuật – Nguyễn Văn Linh”>

Nội dung kĩ thuật:

Như trong https://vuonghienuit.wordpress.com/2012/04/10/divide-and-conquer-ki-thu%E1%BA%ADt-chia-d%E1%BB%83-tr%E1%BB%8B/ đã nói, kĩ thuật chia để trị thường dẫn chúng ta đến một giải thuật đệ quy. Trong các giải thuật đó, có thể có một số giải thuật có độ phức tạp thời gian mũ. Tuy nhiên, thường chỉ có một số đa thức các bài toán con, điều đó có nghĩa là chúng ta đã phải giải bài toán con nào đó nhiều lần. Để tránh việc giải dư thừa một số bài toán con, chúng ta tạo ra một bảng để lưu trữ kết quả của các bài toán con và khi cần chúng ta sẽ sử dụng kết quả đã được lưu trữ trong bảng mà không cần phải giải lại bài toán đó. Lấp đầy bảng kết quả của bài toán con theo một quy luật nào đó để nhận được kết quả của bài toán ban đầu (cũng đã được lưu trong một số ô nào đó của bảng) được gọi là quy hoạch động (dynamic programming). Trong một số trường hợp để tiết kiệm ô nhớ, thay vì dùng một bảng, ta chỉ dùng 1 vectơ.

Có thể tóm tắt giải thuật quy hoạch động như sau:

1. Tạo bảng bằng 2 cách:

    • Gán giá trị cho một số ô nào đó.
    • Gán giá trị cho các ô khác nhờ vào giá trị của các ô trước đó.

2. Tra bảng và xác định kết quả của bài toán ban đầu.

Ưu điểm của phương pháp quy hoạch động là chương trình thực hiện nhanh do không phải tốn thời gian giải lại một bài toán con đã được giải.

Kỹ thuật quy hoạch động có thể dùng để giải các bài toán tối ưu, các bài toán có công thức truy hồi.

Phương pháp quy hoạch động sẽ không đem lại hiệu quả trong các trường hợp sau:

  • Không tìm được công thức truy hồi.
  • Số lượng các bài toán con cần giải quyết và lưu giữ kết quả lả rất lớn.
  • Sự  kết hợp lời giải của bài toán con chưa chắc cho ta lời giải của bài toán ban đầu.

 

Một số bài toán có thể giải bằng quy hoạch động: “Bài toán tính số tổ hợp”, “Bài toán cái ba lô”, “Bài toán đường đi người giao hàng”,…

 

Advertisements

Greedy algorithm (Kĩ thuật tham lam)

<Just Type to Remember>

<Theo “Kỹ thuật thiết kế giải thuật – Nguyễn Văn Linh”>

 

1. Bài toán tối ưu tổ hợp:

Là một dạng của bài toán tối ưu, nó có dạng tổng quát như sau:

  • Cho hàm f(X) xác định trên một tập hữu hạn các phần tử D. Hàm f(X) được gọi là hàm mục tiêu.
  • Mỗi phần tử X thuộc D có dạng X = (x1, x2,…xn) được gọi là một phương án.
  • Cần tìm một phương án X thuộc D sao cho hàm  f(X) đạt min (max). Phương án X như vậy gọi là tối ưu.

Ta có thể tìm thấy phương án tối ưu bằng “vét cạn” nghĩa là xét tất cả các phương án trong tập D (hữu hạn) để tìm phương án tốt nhất. Mặc dù tập D là hữu hạn nhưng để tìm phương án tối ưu cho một bài toán kích thước n bằng vét cạn ta có thể cần một thời gian hàm mũ.

2. Nội dung kĩ thuật tham lam (tham ăn):

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 ăn món ngon thứ hai, lại ăn hết món ngon thứ hai và chuyển sang món ngon thứ 3..

Kĩ thuật tham lam thường được vận dụng để giải bài toán tối ưu tổ hợp bẳng cách xây dựng một phương án X. Phương án X này được xây dựng bằng cách lựa chọn từng thành phần  Xi của X cho đến khi hoàn chỉnh (đủ n thành phần). Với mỗi Xi, ta sẽ chọn Xi tối ưu. Với cách này thì có thể ở bước cuối cùng ta sẽ phải chấp nhận giá trị cuối cùng còn lại.

Áp dụng kĩ thuật tham lam sẽ cho ta một giải thuật thời gian đa thức, tuy nhiên nói chung chúng ta chỉ đạt được một phương án tốt chứ chưa hẳn là tối ưu.

Có rất nhiều bài toán mà ta có thể giải bằng kĩ thuật này.

Các bài toán ví dụ: Các bạn tìm hiểu các bài toán như: “Bài toán trả tiền của máy rút tiền tự động ATM”, “Bài toán cái balô”, “Bài toán đường đi của người giao hàng”, …