Thuật toán quy hoạch động
Wednesday, 4. June 2008, 10:45:22
Thuật toán
Trong bài Thuật toán chia đệ trị chúng ta đã thấy sức mạnh của kỹ thuật Chia để Trị bằng cách chia nhỏ bài toán cần làm. Tuy nhiên không phải bao giờ cũng có thể chia nhỏ bài toán thành các bài toán con và từ đó tìm ra lời giải của bài toán lớn. Trong các trường hợp như vậy, mặc dù chúng ta vẫn có thể chia nhỏ bài toán thành nhiều bài toán con, nhưng thời gian thu được sẽ tăng theo số mũ và thuật toán trở nên vô giá trị.
Thuật toán Qui Hoạch Động (Dynamic Programming)
Trên thực tế, việc chia thành các bài toán con thường chỉ chiếm thời gian là đa thức. Trong trường hợp này một bài toán con sẽ được lặp lại nhiều lần trong quá trình tìm kiếm lời giải. Để khỏi mất thời gian mỗi khi giải quyết các bài toán con, các bạn sẽ lưu trữ các lời giải này để tra cứu về sau mỗi khi cần đến. Công việc này sẽ đòi hỏi độ phức tạp thuật toán là đa thức.
Có một cách làm còn đơn giản hơn cách đã nêu trên. Chúng ta sẽ lưu giữ tất cả các lời giải của các bài toán con lại không cần biết rằng chúng có được dùng lại nhiều lần về sau hay không, không quan tâm đến việc các lời giải này có cần thiết cho lời giải của bài toán chính của chúng ta hay không. Cách làm như vậy có tên gọi là Qui hoạch động. Bản thân từ qui hoạch động được lấy từ lý thuyết điều khiển.
Cách cài đặt thực tế của thuật toán qui hoạch động không thống nhất nhưng điều chung nhất ở chúng là có một cái bảng và chúng ta cần lần lượt điền các thông số vào cái bảng này. Để minh họa chúng ta hãy xét một vài ví dụ.
Ví dụ 3: Trò chơi Tán thủ(5)
Giả sử có hai tán thủ A, B cần đấu trực diện với nhau, qui định chung là người thắng trước n ván sẽ là người thắng cuộc. Trên thực tế thường giá trị n = 4. Giả sử hai tán thủ A, B là mạnh ngang nhau và do đó sác xuất thắng, thua trong mỗi ván là 50/50. Giả sử P(i,j) là sác xuất sao cho A cần thắng thêm i ván nữa , B cần thắng thêm j ván nữa thì A sẽ chắc chắn thắng chung cuộc. Chúng ta cần tính những giá trị P(i,j) này với i, j bất kỳ.
Nếu i=0, j>0, tức là A đã thắng rồi và do đó P(0,j)=1. Nếu i>0, j=0, tức là B đã thắng và A đã thua rồi, do đó P(i,0)=0. Với i, j > 0 ta có nhận xét sau: sác xuất để A thắng chung cuộc dựa vào ván tiếp theo A thắng hay thua. Nếu ván tiếp theo A thắng, khi đó sác xuất để A thắng sẽ là P(i-1,j), còn nếu A thua ở ván tiếp theo thì sác xuất để A vẫn thắng chung cuộc sẽ là P(i,j-1). Vì ván tiếp theo khả năng A thắng thua là 50/50 nên ta có công thức P(i,j) = (P(i-1,j)+P(i,j-1))/2. Tóm lại ta có công thức truy hồi sau để tính P(i,j).
Từ công thức (4) với i+j=n ta dễ dàng tính được công thức truy hồi của độ phức tạp tính toán T(n) như sau:
T(1) = C(C-const)
T(n) = 2T(n-1) + D (D-const)
(5) Ta tính được T(n) = O(2n). Như vậy việc tính toán các hệ số P(i,j) sẽ có độ phức tạp tăng theo số mũ của n nếu tính toán bằng kỹ thuật đệ qui và đây là một kết quả rất lớn. Tuy nhiên công thức trên chỉ cho ta giới hạn trên của tính toán, để hiểu rõ hơn sự″tồi tệ″ thực sự của việc sử dụng đệ qui tính toán theo công thức(4) chúng ta sẽ thử tính toán giới hạn dưới của công việc tính toán này. (Giới hạn dưới của độ phức tạp được ký hiệu là big-omega: W).
