ÁP DỤNG KỸ THUẬT QUY HOẠCH ĐỘNG GIẢI CÁC BÀI TOÁN TỐI ƯU
MỞ ĐẦU
- Lý do chọn đề tài
Trong quá trình học tập, chúng ta gặp rất nhiều các bài tập về Toán-Tin.Các bài tập dạng này rất phong phú và đa dạng.Thực tế chưa có thuật toán hoàn chỉnh có thể áp dụng cho mọi bài toán. Tuy nhiên người ta đã tìm ra một số thuật toán chung như chia để trị, tham lam, quay lui,… Các thuật toán này có thể áp dụng để giải một lớp khá rộng các bài toán hay gặp trong thực tế. Quy hoạch động có những nét giống như phương pháp “Chia để trị”, nó đòi hỏi việc chia bài toán thành những bài toán con kích thước nhỏ hơn, phương pháp chia để trị chia bài toán cần giải ra thành các bài toán con độc lập, sau đó các bài toán con này được giải một cách đệ quy, và cuối cùng tổng hợp các lời giải của các bài toán con ta thu được lời giải của bài toán đặt ra. Điểm khác cơ bản của quy hoạch động với phương pháp chia để trị là các bài toán con là không độc lập với nhau, nghĩa là các bài toán con cùng có chung các bài toán con nhỏ hơn. Trong tình huống đó, phương pháp chia để trị sẽ tỏ ra không hiệu quả, khi nó phải lặp đi lặp lại việc giải các bài toán con chung đó. Quy hoạch động sẽ giải một bài toán con một lần và lời giải của các bài toán con sẽ được ghi nhận, để tránh việc giải lại bài toán con mỗi khi ta gọi lại lời giải của nó.
Quy hoạch động thường được áp dụng để giải các bài toán tối ưu.Trong các bài toán tối ưu, ta có một tập các lời giải, mà mỗi lời giải như vậy được gán với một giá trị số. Ta cần tìm lời giải với giá trị số tối ưu (nhỏ nhất hoặc lớn nhất). Lời giải như vậy ta sẽ gọi là lời giải tối ưu.
Vì những lý do trên tôi xin chọn đề tài “ÁP DỤNG KỸ THUẬT QUY HOẠCH ĐỘNG GIẢI CÁC BÀI TOÁN TỐI ƯU”
- Mục đích nghiên cứu
Nghiên cứu, tổng hợp lý thuyết về Quy hoạch động.
Phân tích các bài toán tối ưu tổ hợp.
Áp dụng kỹ thuật Quy hoạch động giải các bài toán tối ưu.
- Phương pháp nghiên cứu
Thu thập, phân tích các tài liệu và thông tin liên quan đến quy hoạch động.
Lựa chọn một số thuật toán quy hoạch động để giải quyết vấn đề.
Trao đổi, thảo luận với giáo viên hướng dẫn để thực hiện đề tài.
- Đối tượng và phạm vi nghiên cứu
Đối tượng nghiên cứu: Kỹ thuật quy hoạch động và các bài toán ứng dụng Quy hoạch động.
Phạm vi nghiên cứu: Các bài toán tối ưu có thể giải được bằng kỹ thuật quy hoạch động.
- Bố cục đề tài
Ngoài phần lời cảm ơn, mục lục, bảng biểu và tài liệu tham khảo đề tài gồm có 3 chương:
Chương 1: Kỹ thuật Quy hoạch động
Chương 2: Các bài toán tối ưu tổ hợp
Chương 3: Cài đặt chương trình
CHƯƠNG 1
KỸ THUẬT QUY HOẠCH ĐỘNG
1.1. TỔNG QUAN VÀ MỘT SỐ KHÁI NIỆM CHUNG
Có những bài toán mà quyết định ở bước thứ i phụ thuộc vào quyết định ở các bước trước đó. Nếu ta xác định được hệ thức diễn đạt mối tương quan của quyết định ở bước thứ i với quyết định ở bước trước đó thì ta có thể triển khai chương trình theo hệ thức đã tìm được.
Khi đó việc giải các bài toán có kích thước lớn sẽ được chuyển về việc giải các bài toán cùng kiểu có kích thước nhỏ hơn. Các thuật toán này thường được thể hiện bằng các chương trình con đệ quy. Tuy nhiên, với kỹ thuật chia để trị thì nhiều bài toán con phải tính lại nhiều lần.
Vậy ý tưởng cơ bản của quy hoạch động đó là: Tránh tính toán lại các bài toán con nhiều lần, mà lưu giữ kết quả đã tìm kiếm được vào một bảng làm giá trị giả thiết cho việc tìm kết quả của trường hợp sau. Chúng ta sẽ lấp đầy dần các giá trị của bảng này bởi các kết quả của những trường hợp trước đã được giải. Kết quả cuối cùng chính là kết quả của bài toán cần giải.
Phương pháp quy hoạch động cùng nguyên lý tối ưu được nhà toán học Mỹ R.Bellman đề xuất vào những năm 50 của thế kỷ 20. Phương pháp này đã được áp dụng để giải hàng loạt bài toán thực tế trong các quá trình kỹ thuật của công nghệ, tổ chức sản xuất, kế hoạch hoá kinh tế… Tuy nhiên cần lưu ý rằng có một số bài toán giải bằng quy hoạch động tỏ ra không thích hợp.
Trong thực tế, ta thường gặp một số bài toán tối ưu loại sau: Có một đại lượng g hình thành trong một quá trình gồm nhiều giai đoạn và ta chỉ quan tâm đến kết quả cuối cùng là giá trị của g phải lớn nhất hoặc nhỏ nhất, ta gọi chung là giá trị tối ưu của g. Giá trị của g phụ thuộc vào những đại lượng xuất hiện trong bài toán mà mỗi bộ giá trị của chúng được gọi là một trạng thái của hệ thống và cũng phụ thuộc vào cách thức đạt được giá trị g trong từng giai đoạn mà mỗi cách thức được gọi là điều khiển. Đại lượng g thường được gọi là hàm mục tiêu và quá trình đạt được giá trị tối ưu của g được gọi là quá trình điều khiển tối ưu.
Bellman phát biểu nguyên lý tối ưu (cũng gọi là nguyên lý Bellman) mà ý tưởng cơ bản là như sau: “Với mỗi quá trình điều khiển tối ưu, đối với trạng thái ban đầu A0, với mọi trạng thái A trong quá trình đó, phần quá trình kể từ trạng thái A xem như trạng thái bắt đầu cũng là tối ưu”.
Chú ý rằng nguyên lý này được thừa nhận mà không chứng minh.
Phương pháp tìm điều khiển tối ưu theo nguyên lý Bellman thường được gọi là quy hoạch động. Thuật ngữ này nói lên thực chất của quá trình điều khiển là động: Có thể trong số bước đầu tiên lựa chọn điều khiển tối ưu dường như không tốt nhưng chung cả quá trình lại là tốt nhất.
Vậy ý tưởng cơ bản của quy hoạch động thật đơn giản: tránh tính toán lại mọi thứ hai lần, mà lưu giữ kết quả đã tìm kiếm được vào một bảng làm giá trị giả thiết cho việc tìm kết quả của trường hợp sau. Chúng ta sẽ lấp đầy các giá trị của bảng này bởi các kết quả của những trường hợp trước đã được giải.Kết quả cuối cùng chính là kết quả của bài toán cần giải. Nói cách khác phương pháp quy hoạch động đã thể hiện sức mạnh của nguyên lý chia để trị đến cao độ.
Ta có thể giải thích ý này qua bài toán sau: Cho một dãy số nguyên A1,A2,….An. Hãy tìm cách xóa đi một số ít nhất số hạng để dãy còn lại là dãy đơn điệu hay nói cách khác hãy chọn một số nhiều nhất các số sao cho dãy B gồm các số hạng đó theo trình tự xuất hiện trong dãy A là đơn điệu.
Quá trình chọn dãy B được điều khiển qua i giai đoạn để đạt được mục tiêu là số lượng số hạng của dãy B là nhiều nhất, điều khiển ở giai đoạn i thể hiện việc chọn hay không chọn dãy Ai vào dãy B.
Giả sử dãy đã cho là 1 8 10 2 4 6 7. Nếu ta chọn lần lượt 1, 8, 10 thì chỉ chọn được 3 số hạng nhưng nếu bỏ qua 8 và 10 thì ta chọn được 5 số hạng 1, 2, 4, 6, 7.
Khi giải một số bài toán bằng cách “chia để trị”, chuyển việc giải bài toán kích thước lớn về việc giải nhiều bài toán cùng kiểu có kích thước nhỏ hơn thì các thuật toán này thường được thể hiện bằng các chương trình con đệ quy. Khi đó, trên thực tế, nhiều kết quả trung gian phải được tính nhiều lần.
Nói các khác phương pháp quy hoạch động đã thể hiện sức mạnh của nguyên lý chia để trị đến cao độ.
Trong một số trường hợp, khi giải một bài toán A, trước hết ta tìm họ bài toán A(p) phụ thuộc tham số p (có thể là một vectơ) mà A(p0)=A với p0 là trạng thái ban đầu của bài toán A. Sau đó tìm cách giải họ bài toán A(p) với tham số p bằng cách áp dụng nguyên lý tối ưu của Bellman. Cuối cùng cho p=p0 sẽ nhận được kết quả của bài toán A ban đầu.
1.2. KỸ THUẬT QUY HOẠCH ĐỘNG
Để giải bài toán bằng quy hoạch động, ta cần phải tiến hành các bước sau:
Bước 1: Lập hệ thức ( tìm nghiệm của bài toán con đơn giản và tìm ra công thức xây dựng nghiệm của bài toán con thông qua nghiệm của các bài toán con cỡ nhỏ hơn)
Dựa vào nguyên lý tối ưu tìm cách chia quá trình giải bài toán thành từng giai đoạn, sau đó tìm hệ thức biểu diễn tương quan quyết định của bước xử lý với các bước đã xử lý trước đó. Hoặc tìm cách phân rã bài toán thành các “bài toán con” tương tự có kích thước nhỏ hơn, tìm hệ thức nêu quan hệ giữa kết quả bài toán kích thước đã cho với các kết quả của các “bài toán con” cùng kiểu có kích thước nhỏ hơn của nó nhằm xây dựng công phương trình truy toán (dạng hàm hoặc thủ tục đệ quy).
Bước 2: Tổ chức dữ liệu.
Tổ chức dữ liệu sao cho đạt được các yêu cầu sau :
a. Dữ liệu được tính toán dần theo từng bước.
b. Dữ liệu được lưu trữ để giảm lượng tính toán lặp lại.
c. Kích thước miền nhớ dành cho lưu trữ dữ liệu càng nhỏ càng tốt, kiểu dữ liệu được chọn phù hợp, nên chọn đơn giản dễ truy cập.
Bước 3: Truy vết
Truy vết thuật toán bằng cách thu gọn hệ thức và giảm kích thước miền nhớ. Thường dùng mảng một chiều thay cho mảng hai chiều nếu giá trị một dòng (hoặc cột) của mảng hai chiều chỉ phụ thuộc một dòng (hoặc cột) kề trước.
Trong một số trường hợp có thể thay thế mảng hai chiều với các giá trị phần tử chỉ nhận giá trị 0,1 bởi mảng hai chiều mới dùng kỹ thuật quản lý bit.
Trong phần một số bài toán ví dụ chúng ta sẽ nghiên cứu để hiểu rõ hơn về quy hoạch động qua những bài toán cụ thể.
1.3. MỘT SỐ BÀI TOÁN VÍ DỤ
1.3.1. Bài toán dãy Fibonacci: Tìm số hạng thứ N của dãy Fibonacci
1.3.2. Bài toán tính các hệ số trong khai triển của nhị thức newtơn (a+b)n
KẾT LUẬN CHƯƠNG 1
Bài toán tối ưu thường có nhiều phương pháp giải quyết, tuy nhiên dùng kỹ thuật quy hoạch động để giải thì giảm đi rất nhiều số lượng thao tác cần thực hiện nên làm giảm độ phức tạp của bài toán. Đặc biệt, nếu các phương pháp khác giải bài toán có độ phức tạp là hàm mũ thì lúc đó chọn kỹ thuật quy hoạch động để giải bài toán.
CHƯƠNG 2
CÁC BÀI TOÁN TỐI ƯU TỔ HỢP
2.1. BÀI TOÁN BA LÔ (DẠNG 0-1)
2.1.1. Bài toán
Một tên trộm tìm thấy n gói đồ vật, gói thứ i có khối lượng là mi, có giá trị là ci (mi, ci∈N), nhưng cái ba lô của anh ta chỉ có thể mang được khối lượng tối đa là M (M∈N). Tìm cách nhét đầy ba lô sao cho tổng giá trị của ba lô lớn nhất? Mỗi gói đồ vật chỉ có thể lấy nguyên vẹn từng gói hoặc không lấy.
Ví dụ, Cho n=5 gói hàng và M=13 là tổng khối lượng tối đa và các khối lượng, giá trị của từng món hàng cho bởi bảng sau:
| i | 1 | 2 | 3 | 4 | 5 |
| mi | 3 | 4 | 5 | 2 | 1 |
| ci | 4 | 5 | 6 | 3 | 1 |
Kết quả sẽ là chọn các gói:1(3,4), 2(4,5), 3(5,6), 5(1,1) và tổng giá trị ba lô:16
2.1.2. Phân tích bài toán
Ta có thể chia bài toán thành các bài toán con: thay vì xét i đồ vật ta xét i-1 đồ vật
Gọi F(i,v) là tổng giá trị lớn nhất của ba lô mà trọng lượng không vượt quá v khi chỉ sử dụng các đồ vật 1 .. i
Đối với mỗi đồ vật i ta cần trả lời câu hỏi: ba lô hiện tại có thể chứa thêm được đồ vật i hay không?
Ta có thể trả lời câu hỏi này như sau:
– Nếu trọng lượng còn lại hiện tại v của ba lô nhỏ hơn mi thì ba lô không thể chứa đồ vật thứ i
– Ngược lại v>mi thì có hai trường hợp xảy ra:
+ Trường hợp 1: Không thêm đồ vật i vào ba lô, chỉ sử dụng các dồ vật 1 .. i-1
+ Trường hợp 2: Thêm đồ vật i vào ba lô, khi đó giá trị của ba lô tăng lên ci nhưng trọng lượng còn lại của ba lô giảm đi mi( tức là bằng v-mi)
Trong hai trường hợp trên , trường hợp nào cũng cho tổng giá trị của ba lô lớn nhất sẽ được chọn
Từ phân tích trên F(i,v) được tính như sau:
2.1.3. Thuật toán
Lập công thức truy hồi:
Xây dựng bảng phương án
- Cấu trúc bảng phương án: Dùng bảng n+1 dòng và M+1 cột chứa giá trị của các F(i, v)
- Cách tính giá trị trên bảng phương án:
Truy vết tìm lại các gói hàng đã chọn
Bắt đầu từ ô F(n,M) trên dòng n ta dò ngược về dòng 0 theo nguyên tắc:
- Nếu F(i, v)≠ F(i–1, v) thì gói thứ i được chọn, ta truy tiếp ôF(i-1,v-mi)
- Nếu F( i, v) = F(i–1, v) thì gói thứ i không được chọn, ta truy tiếp ô F(i-1,v)
Ví dụ minh họa: Cho 4 đồ vật có khối lượng và giá trị tương ứng với 4 bộ số sau (2;3) (3;4) (4;5) (5;6), trọng lượng tối đa của ba lô có thể chứa là 5. Tìm cách nhét đầy ba lô sao cho tổng giá trị của ba lô là lớn nhất.
ÁP DỤNG KỸ THUẬT QUY HOẠCH ĐỘNG GIẢI CÁC BÀI TOÁN TỐI ƯU
ÁP DỤNG KỸ THUẬT QUY HOẠCH ĐỘNG GIẢI CÁC BÀI TOÁN TỐI ƯU
F:\DỮ LIỆU COP CỦA CHỊ YẾN\DAI HOC DA NANG\LUAN VAN KY THUAT\LUAN VAN 2014\LUAN VAN TOAN SO CAP\LUAN VAN (Nguyen Manh Huy)
