Thuật toán quy hoạch động

Chia sẻ: Tranhung Phihung | Ngày: | Loại File: DOC | Số trang:6

0
1.208
lượt xem
266
download

Thuật toán quy hoạch động

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:
Lưu

Nội dung Text: Thuật toán quy hoạch động

  1. 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
  2. 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). Để tính được giá trị này chúng ta sẽ tính số lần gọi hàm P khi thực hiện đệ qui cách tính P(i,j) theo công thức (4). Công thức (4) với i+j=n nếu xem xét kỹ sẽ gợi ý cho chúng ta về một đẳng thức tương tự của hệ số tổ hợp là (tổ hợp chập i từ n phần tử, số cách chọn ra i phần tử từ tập hợp ban đầu n phần tử). Từ nhận xét trên dễ dàng suy ra rằng số lần gọi hàm P trong lời gọi P(i,j) sẽ ít nhất là . Với i=j=n/2 dễ thấy giá trị này sẽ bằng Vậy ta vừa chứng minh được rằng . cận dưới độ phức tạp tính toán P(i,j) là là một giá trị rất lớn (tuy có nhỏ hơn 2n) và hầu như không thể áp dụng tính toán trên thực tế. Cách tính P(i,j) tốt nhất là vừa tính vừa điền số vào bảng như mô tả trong hình 3 dưới đây.
  3. Bảng hệ số P(i,j) được điền tuần tự như sau: Trước tiên để ý rằng hàng dưới cùng của bảng là toàn 0 và hàng đầu tiên bên phải sẽ là toàn 1. Xuất phát từ góc phải dưới chúng ta lần lượt điền số vào bảng theo hướng Tây-Bắc dọc theo đường chéo ngược với i+j không thay đổi. Thuật toán điền số P(i,j) vào bảng được mô tả như sau: Function Ođs(i,j: integer):real; (7) var s,k:integer; Begin for s:=1 to i+j do begin P[0,s]:=1; P[s,0]:=0; for k:=1 to s-1 do P[k,s-k]:=(P[k-1,s-k]+P[k,s-k-1])/2; end; Ođs:=(P[i,j]); End; {Ođs} Ta hãy thử phân tích thuật toán trên. Vòng lặp bên trong là O(s) thời gian, hai lệnh gán 0 và 1 chỉ là O(1) thời gian, như vậy tổng số thời gian tính từ vòng lặp ngoài sẽ là với n=i+j. Chắc các bạn đã thấy sự kỳ diệu của phương pháp điền bảng số so sánh với việc gọi đệ qui, và đó là tư tưởng của thuật toán qui hoạch động. Ví dụ 4: Bài toán Phân hoạch Tam giác
  4. Ta sẽ xét thêm một ví dụ nữa minh họa cho kỹ thuật qui hoạch động, đó là bài toán tam giác hóa đa giác. Giả sử có một đa giác trên mặt phẳng với các đỉnh cho trước. Yêu cầu nối các ″cung″ nối giữa hai đỉnh bất kỳ của đa giác để chia đa giác thành các tam giác nhỏ hơn (phân hoạch tam giác) sao cho tổng các dây cung nối là nhỏ nhất. Một cách chọn dây cung như vậy được gọi là một Phân hoạch tam giác tối thiểu. Hình 4 mô tả một đa giác 7 cạnh với một phân hoạch tam giác. Từ dữ liệu trên hình vẽ ta tính được tổng chiều dài của phân hoạch này là tuy nhiên phân hoạch này không là tối ưu. Bây giờ chúng ta sẽ dùng kỹ thuật qui hoạch động để giải bài toán phân hoạch tam giác này. Để tiện cho việc theo dỏi, chúng ta sẽ ký hiệu các đỉnh của đa giác là V0, V1,.., Vn-1 theo chiều kim đồng hồ. Tổng chiều dài các dây cung của một phân hoạch sẽ được gọi là Giá trị của phân hoạch này. Trước tiên chúng ta có một số nhận xét sau đây: Bổ đề 1. Trong mọi phân hoạch tam giác, hai đỉnh kề nhau bất kỳ của đa giác bao giờ cũng có tối thiểu một đỉnh được nối với một dây cung. Giả sử Vi,Vi-1 là hai đỉnh kề mà không được nối với bất cứ dây dung nào của phân hoạch tam giác. Khi đó vùng phân hoạch chứa cạnh ViVi+1 sẽ phải chứa thêm hai cạnh nữa là Vi-1Vi và Vi+1Vi+2 và do đó vùng phân hoạch này không là tam giác. Bổ đề 2. Giả sử (Vi,Vj) là một dây cung của phân hoạch tam giác, khi đó phải tồn tại một đỉnh Vk sao cho (Vi,Vk) và (Vk,Vj) sẽ là cạnh của đa giác hoặc dây cung của phân hoạch. Thật vậy, cạnh (Vi,Vj) phải là cạnh của một tam giác của phân hoạch. Đỉnh thứ 3 chính là Vk cần tìm. Để bắt đầu tìm kiếm phân hoạch tam giác tối ưu, chúng ta chọn 2 đỉnh kề bất kỳ,
  5. chẳng hạn V0 và V1. Khi đó phải tồn tại đỉnh Vk sao cho V0Vk và V1Vk là cạnh hoặc dây cung của phân hoạch. Với mỗi cách chọn k như vậy ta đưa bài toán tìm phân hoạch về 2 bài toán con, tương ứng với 2 đa giác con xác định bởi dây cung vừa tìm được phân chia đa giác ban đầu thành 2 phần. Với ví dụ đa giác 7 cạnh đã nêu trên giả sử ta chọn đỉnh V3 với cung V0V3, khi đó sẽ đưa về 2 bài toán con ứng với hai đa giác sau đây: Tiếp theo chúng ta cần giải quyết bài toán phân hoạch tam giác cho hai trường hợp tương ứng với hình 5 trên. Ví dụ với Bài toán con 2, nếu chúng ta bắt đầu từ cung V3V5 thì sẽ chia thành 2 bài toán con nữa tương ứng với hai đa giác con là (V3,V4,V5) và (V0,V3,V5,V6). Cách tiếp cận như vậy sẽ có thời gian tăng số mũ với n. Chú thích của người viết. (1) Sắp xếp trộn. Thuật toán sắp xếp tách dãy ban đầu thành 2 dãy và sau đó tiến hành ″trộn″ hai dãy này lại với nhau theo hình thức xét lần lượt từng phần tử đầu của các dãy này. (2) Tìm kiếm nhị phân. Thuật toán tìm kiếm trên một dãy đã sắp thứ tự dựa trên ý tưởng luôn chia dãy đã cho thành 2 phần bằng nhau và đưa việc tìm trên dãy lớn về bài toán tìm kiếm trên các dãy con này. (3) Phương pháp tính nhân trong nhà trường phổ thông. Chia nhỏ việc nhân 2 số n-chữ số XY thành n bài toán con, mỗi bài toán con nhân X với một số có một chữ số. Với mỗi bài toán con như vậy việc nhân mất O(n) thời gian, do vậy tổng số độ phức tạp là O(n2). (4) Tới đây sẽ có bạn thắc mắc rằng thế thì tại sao không dạy cách nhân mới này cho học sinh ngay từ trên ghế nhà trường. Tuy nhiên thuật toán mô tả ở đây hoàn toàn không tốt hơn cách nhân thông thường ở trường phổ thông với n<5000. Ma(.t kha'c no' la.i qua' phu+'c ta.p va` kho^ng sa'ng su?a nhu+ thua^.t toa'n ho.c sinh ddang su+? du.ng hie^.n nay.
  6. (5) Nguyên tác là cụm từ World Series Ođs, chúng tôi sửa lại cho thích hợp hơn với thực tế của Việt Nam. (6) Cách tính như sau: Với i=j=n/2 ta cần phải chứng minh: Ta chứng minh bất đẳng thức này qui nạp theo n (n-chẵn). Với n=2, bất đẳng thức là hiển nhiên. Giả sử nó đã đúng với n, ta sẽ chứng minh nó cũng đúng với n+2. Thật vậy khi đó ta có: . theo qui nạp giá trị này sẽ lớn hơn hoặc bằng . bất đẳng thúc cuối cùng xảy ra vì .

CÓ THỂ BẠN MUỐN DOWNLOAD

Đồng bộ tài khoản