Toán rơi rạc để nộp-đã chuyển đổi PDF

Preview

Summary

Hà Nội, ngày 18 tháng 11 năm 2021TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘIVIỆN TOÁN ỨNG DỤNG VÀ TIN HỌCTIỂU LUẬNĐỀ TÀI:QUY HOẠCH ĐỘNGGIẢNG VIÊN: LÊ KIM THƯHọ và tên: Bùi Đức Hoàng Mã sinh viên: 20206142Mã lớp: 129846 Mã học phần: MIMục lục A. Tổng quan về quy hoạch động 1. Giới thiệu chung a) Khái niệm b...

Description

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN TOÁN ỨNG DỤNG VÀ TIN HỌC   

TIỂU LUẬN ĐỀ TÀI:

QUY HOẠCH ĐỘNG

GIẢNG VIÊN: LÊ KIM THƯ

Họ và tên: Bùi Đức Hoàng Mã sinh viên: 20206142 Mã lớp: 129846 Mã học phần: MI3010

Hà Nội, ngày 18 tháng 11 năm 2021

Mục lục A. Tổng quan về quy hoạch động .......................................................................................... 2 1. Giới thiệu chung ............................................................................................................... 2 a) Khái niệm ...................................................................................................................... 2 b) Ưu điểm ......................................................................................................................... 2 c) Nhược điểm ................................................................................................................... 2 2. Thuật toán chia để trị ...................................................................................................... 3 3. Nguyên lý tối ưu của Bellman ......................................................................................... 4 4. Đặc điểm chung của phương pháp quy hoạch động..................................................... 4 5. Các bước giải bài toán tối ưu bằng quy hoạch động .................................................... 5 a) Các cách tiếp cận .......................................................................................................... 5 b) Các bước giải bài toán quy hoạch động ..................................................................... 6 B. Một số bài toán liên quan đến quy hoạch động kinh điển .............................................. 6

1. Bài toán tính 𝒏! ................................................................................................................ 6

2. Triển khai nhị thức Newton (𝒂 + 𝒃)𝒏 ............................................................................ 7

3. Bài toán xếp ba lô ............................................................................................................. 9

4. Bài toán tìm đường đi nhỏ nhất.................................................................................... 11 5. Bài toán tìm dãy con chung dài nhất ........................................................................... 11 6. Bài toán tìm dãy con đơn điệu tăng dài nhất không liên tiếp .................................... 13 C. Kết luận ............................................................................................................................. 15

Page | 1

A. Tổng quan về quy hoạch động 1. Giới thiệu chung a) Khái niệm Phương pháp quy hoạch động do nhà toán học người Mĩ Richard Bellman (1920- 1984) phát minh vào năm 1953. Trong ngành khoa học máy tính, quy hoạch động ( Dynamic Programming) là một phương pháp giảm thời gian chạy của các thuật toán thể hiện các tính chất của các bài toán con gối nhau (overlapping subproblem) và cấu trúc con tối ưu (optimal substructure). Đây là một phương pháp rất hiệu quả để giải nhiều bài toán tin học, đặc biệt là những bài toán tối ưu. Những bài toán này thường có nhiều nghiệm chấp nhận được và mỗi nghiệm có một giá trị lớn nhất hoặc nhỏ nhất (tối ưu). Hiện nay các bài thi trong các cuộc thi code, cuộc thi hackathon đa số đều cần đến quy hoạch động. Tất nhiên vẫn có cách giải khác để giải bài toán đó. Nhưng vì các cuộc thi code có giới hạn về thời gian, cũng như bộ nhớ của chương trình, nên một thuật toán hiệu quả là cực kỳ cần thiết. Và trong các trường hợp như vậy, quy hoạch động là một trong những thuật toán hết sức cần thiết và quan trọng. b) Ưu điểm Quy hoạch động là ta giải các bài toán con đơn giản nhất của bài toán mẹ. Sau đó kết hợp chúng lại để tìm lời giải cho bài toán lớn lần lượt như thế cho tới khi tìm được đáp án của bài toán yêu cầu theo phương pháp quy nạp. Quy hoạch động thể hiện được sức mạnh ở chỗ với mỗi bài toán con, bài toán nhỏ đã giải được đều sẽ được lưu trữ lại và đem ra sử dụng khi cần. Do đó giúp ta tiết kiệm thời gian giải. c) Nhược điểm Việc kết hợp các bài toán con thành bài toán lớn, hay chia bài toán lớn thành các bài toán nhỏ là một công việc đòi hỏi sự nhanh nhạy và chặt chẽ trong lập luận. Vì thế nó là một công việc hết sức khó khăn để tìm công thức truy hồi và đôi khi đưa ta vào bế tắc. Hơn nữa, khi giải với phương pháp quy hoạch động, việc xuất hiện số lượng bài toán con cần lưu trữ lớn là điều không thể tránh khỏi. Gây Page | 2

ra hiện tượng tràn bộ nhớ, tốn rất nhiều bộ nhớ để lưu trữ, đòi hỏi máy tính phải có khối lượng bộ nhớ lớn. 2. Thuật toán chia để trị Hay còn gọi là các bài toán con gối nhau. “ Chia để trị” là một trong những phương pháp thông dụng nhất trong tin học. Trong thuật toán đệ quy, nguyên lý chia để trị (devide and conquer) thường đóng vai trò cốt lõi trong việc thiết kế thuật toán. Để giải một bài toán lớn, ta chia nhỏ nó thành hữu hạn các “ bài toán con độc lập”, giải quyết từng “ bài toán con" một cách riêng lẻ rồi tổ hợp dần lời giải, liên kết lại chúng lại thành bài toán ban đầu. Phương pháp chia để trị thường được áp dụng đối với những bài toán lớn, có thể chia nhỏ và mang bản chất bài toán đệ quy. Quá trình đệ quy lần lượt xếp dần các bài toán con vào ngăn xếp bộ nhớ và thực hiện giải các bài toán con theo thứ tự từ đơn giản nhất cho đến phức tạp, đến khi giải được bài toán mẹ ban đầu. Quy hoạch động là một dạng đặc biệt của thuật toán chia để trị. Do đó quy hoạch động có thể giải bằng đệ quy ( chia để trị) nhưng ngược lại thì chưa chắc. Thuật toán chia để trị được cài đặt bằng đệ quy mà trong đó những bài toán con sẽ được giải nhiều lần, điều này dẫn đến làm tăng thời gian thực hiện chương trình. Trong khi đó quy hoạch động tối ưu hơn ở chỗ thuật toán sẽ ghi lại kết quả các bài toán con vào trong các biến ( thường là biến mảng) và sử dụng chúng khi cần thiết mà không phải giải lại bài toán con. Khi đó việc thực thi sẽ tốn ít thời gian hơn, tăng tốc độ thực hiện chương trình, tuy nhiên việc sử dụng bộ nhớ có thể sẽ tốn tài nguyên hơn. Một số thuật toán: Ví dụ 1: Tính số hạng thứ N của dãy Fibonacci. Công thúc đệ quy của dãy Fibonacci: F(1)=1, F(2)=1, F(N)=F(N-1) + F(N-2) với N > 2. Lời giải( mã giả) : Int Fibonacci (int N ) { If (N=1) or (N=2) then F:=1 Else F:=F(N-1)+F(N-2) } Ví dụ 2: Tìm số Catalan thứ N biết Catalan là dãy số thoả mãn biểu thức: Page | 3

𝑛−1 0 𝑛ế𝑢 𝑛 = 0 𝐶𝑛 = { ∑𝑖=0 𝐶𝑖 𝐶𝑛−𝑖−1 𝑛ế𝑢 𝑛 > 0

Mã giả:

A[0]=1, A[1]=1; For i:=1 to N+1 do{ For j:=0 to i do A[i]+= A[j]*A[i-j-1]; } Return A[N]; 3. Nguyên lý tối ưu của Bellman Nguyên lý tối ưu của Bellman là một nguyên lý thừa nhận mà không chứng minh. Ta biết rằng phương pháp quy hoạch động thường xuyên được dùng cho việc giải các bài toán tối ưu, bài toán yêu cầu tìm phương pháp tốt nhất trong các giải pháp có thể tìm được. Và nguyên lý tối ưu của Bellman chính là cơ sở cốt lõi cho bài toán quy hoạch động. Nguyên lý tối ưu Bellman được phát biểu như sau: “Dãy tối ưu các quyết định trong một quá trình quyết định nhiều giai đoạn có thuộc tính là dù trạng thái và các quyết định ban đầu bất kể như thế nào, những quyết định còn lại phải tạo thành một cách giải quyết tối ưu không phụ thuộc vào trạng thái được sinh ra từ những quyết định ban đầu”. Do đó khi ta muốn giải một bài toán bằng phương pháp quy hoạch động. Trong một vài bài toán đơn giản quy hoạch động có thể diễn ra trong một bước, nhưng nếu bài toán gồm nhiều bước thì hãy chắc rằng bài toán lớn phải được xây dựng từ những “ bài toán con” một cách tối ưu, hay được xây dựng từ nghiệm tối ưu của những “bài toán con” ở các bước trước, khi đó bài toán lớ n mới được giải một cách tối ưu. 4. Đặc điểm chung của phương pháp quy hoạch động Với phương pháp quy hoạch động, chúng ta bắt đầu từ việc giải hữu hạn những bài toán con nhỏ nhất ( bài toán cơ sở), từ đó từng bước tổng hợp, quy nạp lại để giải những bài toán lớn hơn cho tới khi giải được bài toán lớn nhất ( bài toán ban đầu). Page | 4

Khi giải một bài toán theo phương pháp chia để trị, ta phải chia bài toán lớn thành hữu hạn các bài toán con cùng kiểu nhỏ hơn và giải quyết lần lượt chúng bằng giải thuật đệ quy. Khi đó, trên thực tế nhiều bài toán con có kết quả trung gian giống nhau phải nhưng vẫn phải tính lại nhiều lần, dẫn tới việc lãng phí tài nguyên bộ nhớ và làm chậm tốc độ chạy. Đối với phương pháp quy hoạch động, để tối ưu bài toán và tránh việc phải tính toán lại một số kết quả trùng lặp gặp lại nhiều lần, hoặc các kết quả trung gian giống nhau. Ta thường xây dựng 1 bảng phương án dùng cho việc lưu trữ các kết quả đã tìm được. Mảng này thường là một mảng N chiều và được tính toán theo công thức quy hoạch ta đã tìm được. Việc áp dụng bảng phương án đã khiến quy hoạch động tối ưu hơn rất nhiều, giảm thiếu các quá trình tính toán, và thể hiện sức mạnh của thuật toán quy hoạch động so với các thuật toán khác. Làm nổi bật lên nguyên lí chia để trị. Thường thì không có bài toán hay dấu hiệu nhận biết nào cho ta biết khi nào phải dùng phương pháp quy hoạch động nhưng nếu bài toán đó thể hiện tính chất của các bài toán con gối nhau hay có cấu trúc tối ưu thì đó là lúc chúng ta nên dùng tới phương pháp quy hoạch động.

5. Các bước giải bài toán tối ưu bằng quy hoạch động a) Các cách tiếp cận Bài toán quy hoạch động thường được dùng một trong hai cách tiếp cận sau: • Top – down ( Từ trên xuống): Trong cách tiếp cận này ta sẽ chia bài toán lớn thành các bài toán con, và giải quyết chúng lần lượt. Bất cứ khi nào giải quyết xong một bài toán con, chúng ta sẽ lưu kết quả vào bộ nhớ để tránh việc phải giải quyết lại nếu như bài toán con đó được gọi lại nhiều lần. Đây là đệ quy và lưu trữ được kết hợp với nhau. • Bottom-up ( Từ dưới lên): Trong cách tiếp cận này, ta sẽ giải quyết vấn đề theo hướng từ dưới lên. Tất cả các bài toán con có thể cần đến đều được giải trước, sau đó sẽ được dùng để xây dựng lời giải cho các bài toán lớn hơn. Thường được thực hiện bằng cách lưu kết quả vào một mảng N chiều. Cách tiếp cận này hơi tốt hơn về không gian bộ nhớ dùng cho ngăn xếp và số lời gọi hàm. Tuy nhiên, đôi khi việc xác định

Page | 5

tất cả các bài toán con cần thiết cho việc giải quyết bài toán cho trước không được trực giác lắm. b) Các bước giải bài toán quy hoạch động • Bước 1: Lập công thức truy hồi Dựa vào nguyên lý tối ưu, ta chia bài toán thành từng giai đoạn, tìm cách phân rã bài toán thành hữu hạn các “ bài toán con” tương tự có kích thước nhỏ hơn, tìm hệ thức quan hệ giữa kết quả của bài toán có kích thước đã cho với kết quả của các “ bài toán con” cùng kiểu có kích thước nhỏ hơn. • Bước 2: Tổ chức dữ liệu và chương trình cho bài toán Ta tổ chức dữ liệu dựa trên các yêu cầu sau: ✓ Dữ liệu được tính toán dần theo các bước. ✓ Dư liệu được lưu trữ vào bảng phương án để giảm lượng tính toán lặp lại. Các giá trị sau khi tính toán thường được lưu trữ trong các mảng N chiều một cách có thứ tự giúp cho việc tính toán, truy cập có thể tiến hành một cách thuận lợi và khoa học. • Bước 3: Truy vết, tìm nghiệm của bài toán dựa vào bảng phương án Dựa vào bảng phương án đã có sau khi giải, ta tìm kết quả tối ưu của bài toán. Sau khi đã tìm được nghiệm tối ưu của bài toán. Để bài toán cho ra hiệu suất tốt nhất, giảm thiểu quy trình, tiết kiệm thời gian và bộ nhớ, ta tìm cách phát triển thuật bằng cách thu gọn hệ thức truy hồi hoặc cung cấp các thuật toán.

B. Một số bài toán liên quan đến quy hoạch động kinh điển 1. Bài toán tính 𝒏!

Bài toán: Hãy tính giá trị của 𝑛! khi biết giá trị của n. Input: Số nguyên dương n

Output: Giá trị của 𝑛!

Phân tích bài toán:

Page | 6

1 , 𝑛=0 Ta có định nghĩa như sau 𝑛! = { 𝑛 ∗ (𝑛 − 1)! , 𝑛 > 0 Như vậy để tính được 𝑛! ta tính (𝑛 − 1)! Sau đó ghi nhớ và áp dụng cho các

vòng lặp sau đến giá trị 0. Thuật toán:

Gọi GT[n] là giá trị của 𝑛!

Ta có công thức quy hoạch động như sau: GT[n] := n*GT[n-1];

Như vậy việc tính 𝑛! sẽ được thực hiện vòng lặp:

GT[0]:=1;

For i:=1 to n do GT[i]:= i*GT[i-1];

Kết quả: Giá trị của 𝑛! là giá trị nằm trong phần tử GT[n]. 2. Triển khai nhị thức Newton (𝒂 + 𝒃)𝒏

Bài toán: Hãy triển khai nhị thức Newton (𝑎 + 𝑏)𝑛 khi biết giá trị của n. (Tìm các hệ số trong khai triển). Input: số nguyên dương n.

Output: nhị thức (𝑎 + 𝑏)𝑛 đã được triển khai Ví dụ: với n=2;

(𝑎 + 𝑏)2 = 𝑎2 + 2𝑎𝑏 + 𝑏2

Phân tích bài toán:

Nhị thức Newton được triển khai theo công thức như sau: Với 𝐶𝑛𝑘 =

( 𝑎 + 𝑏) 𝑛 = ∑

𝑛 𝐶 𝑘 𝑎𝑘 𝑏𝑛−𝑘 𝑘=0 𝑛

𝑛(𝑛−1)(𝑛−2)….(𝑛−𝑘+1) 𝑘!

=

𝑛!

𝑘!(𝑛−𝑘)!

Như vậy muốn triển khai được nhị thức Newton ta phải tính được 𝐶𝑛𝑘 với 0≤ 𝑘 ≤ 𝑛. Ta có công thức tính tổ hợp chập k của n:

Page | 7

𝑘 = 0; 𝑘 = 𝑛 𝑘 𝐶𝑛𝑘 = { 𝐶1𝑘−1 + 𝐶𝑛−1 1≤ 𝑘 ≤ 𝑛−1 𝑛−1 • Ta xây dựng một bảng C gồm n+1 dòng và n+1 cột biểu diễn phần tử từ 0 đến n. • C[i, j] lưu trữ gí trị của Newton(i, j) theo quy tắc sau ( quy tắc tam giác Pascal): o C[0,0]=1; o C[i, 0]=1; o C[i, i] =1 với 0< i≤ 𝑛.

o C[i, j] = C[i-1, j-1] + C[i-1, j] với 0 0, 𝑥𝑖 ≠ 𝑦𝑖 i

0

1

2

3

4

B

U

N

H

0

0

0

0

0

j

0 1

B

0

1

1

1

1

2

U

0

1

2

2

2

3

I

0

1

2

2

2

4

H

0

1

2

2

3

5

O

0

1

2

2

3

6

A

0

1

2

2

3

7

N

0

1

2

3

3

Page | 12

8

G

0

1

2

3

3

Kết luận: Vậy dãy con chung dài nhất của BUIHOANG và BUNH là 3 là dãy BUH hoặc BUN. Thuật toán: Int C[m,n]; For i:=0 to m For j:=0 to n If(i=0 or j=0) then C[i, j]=0; Else If (Xi = Yj) then C[i,j] = C[i-1,j-1] + 1; Else C[i,j]= max(C[i,j-1], C[i-1,j]); 6. Bài toán tìm dãy con đơn điệu tăng dài nhất không liên tiếp

Bài toán: Cho một dãy số nguyên gồm n phần tử 𝑎1 , 𝑎2 , . . . , 𝑎𝑛 . Hãy tìm một

dãy con của dãy đã cho sao cho các phần tử là đơn điệu tăng. Input: Dòng đầu số nguyên n là độ dài của dãy.

Dòng sau gồm n phần tử 𝑎1 , 𝑎2 , . . . , 𝑎𝑛 cách nhau một dấu cách.

Output: Độ dài của dãy con tăng dài nhất. Danh sách các phần tử trong dãy con đó. Ví dụ: Input

Output

10

6

3457821293

345789

Phân tích bài toán: • Trước tiên ta sẽ lập một mảng A[0…n] để lưu các giá trị của 𝑎1 , 𝑎2 , . . . , 𝑎𝑛 và một mảng con L.

• Với i chạy từ 0 tới n. ta sẽ dùng mảng L để lưu lại giá trị theo công thức truy hồi. Page | 13

Ví dụ với A[2]=5 ta xét i chạy từ 0 đến 2, nếu như không có giá trị A[i] nào lớn hơn A[2] thì L[2] = L[1]+1. Còn nếu như tồn tại giá trị i thuộc (0,2) sao cho A[i] > A[2] thì ta sẽ tính lại L[i]=1 tại vị trí lớn hơn đó. Lặp lại cho tới khi chạy hết các giá trị. • Ta tìm được công thức truy hồi: { i

𝒏ế𝒖 ∃𝒋 = (𝟎, 𝒊) 𝒔𝒂𝒐 𝒄𝒉𝒐 𝒂𝒊 < 𝒂𝒋

𝑳[𝒊] = 𝟏

𝑳[𝒊] = 𝑴𝒂𝒙𝑳[𝒋]𝟎≤𝒋 𝒂𝒋 ∀𝒋 = (𝟎, 𝒊)

0

1

2

3

4

5

6

7

8

9

Mảng 3 A

4

5

7

8

2

1

2

9

3

Mảng 1

2

3

4

5

1

1

2

6

1

L Kết luận: Vậy độ dài chuỗi con dài nhất là 6: . Thuật toán: Int A[100],Int L[100]; Int Lmax //lưu giá trị max từ đầu tới phần tử i L[0]=1; For i:= 1 to n do{ Lmax=0; For j:=0 to i { If ( A[i] > A[j] ) If (L[j]>Lmax) then Lmax=L[j]; } L[i]=Lmax +1; }

Page | 14

C. Kết luận Quy hoạch động là một thuật toán hiện đại, một lớp thuật toán quan trọng, hiệu quả và có ứng dụng nhiều trong ngành khoa học máy tính. Thuật toán quy hoạch động có có thể giải được hầu hết các bài toán tối ưu. Tuy nhiên khi giải bài toán quy hoạch động, ta cần tìm đến công thức truy hồi của nó thật đúng đắn, tối ưu và chứng minh được độ chính xác tin cậy của nó. Một số tài liệu hay nên tham khảo về quy hoạch động: • Dynamic Programming || Richard Bellman • Dynamic Programming and Optimal Control || Dimitri Bertsekas • Algorithm Design Techniques || Narasimha Karumanchi

Page | 15...