Phương pháp quy hoạch động.

ĐẠI HỌC ĐÀ NẴNG

TRƯỜNG ĐẠI HỌC SƯ PHẠM

KHOA TIN

----------

PHẠM THỊ THẢO

QUY HOẠCH ĐÔNG

KHÓA LUẬN TỐT NGHIỆP

- 1 -

Phiếu Nhận Xét Của Giáo Viên Hướng Dẫn.

..............................................................................

..............................................................................

..............................................................................

..............................................................................

..............................................................................

..............................................................................

..............................................................................

..............................................................................

..............................................................................

..............................................................................

..............................................................................

..............................................................................

..............................................................................

..............................................................................

..............................................................................

Đà Nẵng, ngày…tháng…năm 2012

Giáo viên hướng dẫn

PGS.TSKH Trần Quốc Chiến

Phiếu Nhận Xét Của Giáo Viên Phản Biện.

..............................................................................

..............................................................................

..............................................................................

..............................................................................

..............................................................................

..............................................................................

..............................................................................

..............................................................................

..............................................................................

..............................................................................

..............................................................................

..............................................................................

..............................................................................

..............................................................................

..............................................................................

Đà Nẵng, ngày…tháng…năm 2012

Giáo viên phản biện.

LỜI CẢM ƠN

Xin được gởi lời cảm ơn chân thành đến quý thầy cô trường Đại Học

Sư Phạm Đại Học Đà Nẵng, những người đã tận tâm dạy dỗ, truyền đạt cho

chúng tôi những kiến thức và những bài học kinh nghiệm quý giá trong suốt

thời gian qua.

Xin được gởi lời cảm ơn tới quý thầy cô giáo trong khoa Toán và khoa

Tin, đặc biệt là thầy giáo Trần Quốc Chiến đã hết lòng hỗ trợ, chỉ bảo tận

tình, giúp đỡ tôi hoàn thành khóa luận.

Cuối cùng, tôi xin được gởi lời cảm ơn tới cán bộ quản lý thư viện

trường Đại Học Sư Phạm Đại Học Đà Nẵng cùng các bạn trong tập thể lớp

08CTT1 đã giúp tôi trong quá trình thu thập tài liệu để hoàn thành khóa luận.

Đà Nẵng, ngày 25 tháng 5 năm 2012

Sinh viên

Phạm Thị Thảo

- 1 -

LỜI MỞ ĐẦU

1. LÝ DO CHỌN ĐỀ TÀI.

Khoa học luôn gắn liền với thực tiễn. Nếu như con người muốn tìm ra

một phương pháp hoạt động ít hao tốn nhất về thể lực và vật chất mà vẫn có

kết quả như mong muốn thì khoa học luôn tìm ra những phương pháp tốt nhất

nhằm giải quyết các bài toán trên máy tính nhanh chóng, ít tốn bộ nhớ và độ

phức tạp nhỏ nhất.

Hơn hai thập kỷ qua, nghành khoa học về phương pháp tối ưu đã có

những bước tiến lớn, đặc biệt từ khi máy tính được phổ biến rộng rãi và có

tính năng ngày càng mạnh. Nếu như giữa những năm 60 các bài toán phi

tuyến khoảng mười biến còn được coi là cỡ quá lớn, rất khó giải thì nay nhiều

bài toán hàng trăm, hàng nghìn biến có thể được xử lý dễ dàng. Như vậy, các

phương pháp tối ưu có vai trò ngày càng tăng trong thời đại kỹ thuật cao hiện

nay.

Bài toán tối ưu đặt ra là phải tìm ra một nghiệm thỏa mãn một số điều

kiện nào đó mà nghiệm đó là tốt nhất theo một chỉ tiêu cụ thể. Đã có nhiều

thuật toán giải quyết vấn đề này như thuật toán nhánh cận, giải thuật tham

lam, phương pháp quy hoạch động, chia để trị. Ở đây, ta bàn đến phương

pháp quy hoạch động để giải bài toán tối ưu.

Đối với những ai yêu thích môn lập trình thì có lẽ giải thuật qui hoạch

động tương đối quen thuộc trong việc giải quyết các vấn đề tin học. Tuy

nhiên, sẽ thật là khó để có thể tìm được cơ cở và công thức cho việc sử dụng

quy hoạch động. Chính vì vấn đề này, quy hoach động lại trở thành không

phổ biến. Đối với những bài toán như vậy, chúng ta lại cố gắng đi tìm cách

giải khác ví dụ như vét cạn hay tham lam....điều đó thật không hay!

Trong phần đề tài này em sẽ trình bày về phương pháp quy hoạch động.

Tuy nhiên em không thể trình bày một cách hoàn chỉnh về quy hoạch động

mà chỉ giới thiệu về phương pháp, cách dùng quy hoạch động để thiết kế một