Áp dụng kỹ thuật quy hoạch động giải các bài toán tối ưu.

BỘ GIÁO DỤC VÀ ĐÀO TẠO

ĐẠI HỌC ĐÀ NẴNG

NGUYỄN MẠNH HUY

ÁP DỤNG KỸ THUẬT QUY HOẠCH ĐỘNG

GIẢI CÁC BÀI TOÁN TỐI ƢU

Chuyên ngành: Phƣơng pháp Toán sơ cấp

Mã số: 60.46.40

LUẬN VĂN THẠC SĨ KHOA HỌC

Đà Nẵng - Năm 2015

Công trình được hoàn thành tại

ĐẠI HỌC ĐÀ NẴNG

Ngƣời hƣớng dẫn khoa học: PGS.TSKH Trần Quốc Chiến

Phản biện 1: TS. Cao Văn Nuôi

Phản biện 2: TS. Hoàng Quang Tuyến

Luận văn đã được bảo vệ trước Hội đồng chấm Luận văn

tốt nghiệp thạc sĩ Khoa học họp tại Đại học Đà Nẵng vào ngày

10 tháng 01 năm 2015

Có thể tìm hiểu luận văn tại:

 Trung tâm Thông tin - Học liệu, Đại học Đà Nẵng

 Trung tâm Học liệu, Đại học Đà Nẵng

1

MỞ ĐẦU

1. 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”

2

2. 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.

3. 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.

4. Đố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.

5. 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

3

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ị

4

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ậ ý 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

5

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

6

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

7

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.

8

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:

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:

i 1 2 3 4 5

mi 3 4 5 2 1

ci 4 5 6 3 1