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