1
QUY HOẠCH ĐỘNGQUY HOẠCH ĐỘNG
Chuyên đề:
2
Giảng viên: NGUYỄN DUY DŨNG
Đơn vị:Trư ờ ng THPT Chuyên Hà Tĩnh
SốĐT: 0913141823
Email: Dungduyit83@gmail.com
FaceBook: Dungduyit83
QUY HOẠCH ĐỘNG LÀ GÌ?
QUY HOẠCH ĐỘNG LÀ GÌ?
Bài toán
Quy hoạch động
(dynamic programming)
Chia đểtrị
(divide & conquer)
3
Thiết kếthuật toán
Mô hình hóa
Xây dựng cấu trúc dữliệu
Lập trình Kiểm thử
Vét cạn
(exhaustive search) Tham lam
(greedy)
Cách khác
Ba tính chất của bài toán tốiưu có thểgiải bằng quy hoạch động:
Bài toán lớ n có thể phân rã thành nhữ ng bài toán con đồ ng dạ ng, nhữ ng bài
toán con đó có thể phân rã thành nhữ ng bài toán nhỏ hơ n nữ a …( recursive
form).
Lờ i giả i tố i ư u củ a các bài toán con có thể sử dụ ng để tìm ra lờ i giả i tố i ư u
BÀI TOÁN QUY HOẠCH ĐỘNG
BÀI TOÁN QUY HOẠCH ĐỘNG
Ba tính ch t c a bài toán t i u có th gi i b ng quy ho ch đ ng:
Lờ i giả i tố i ư u củ a các bài toán con có thể sử dụ ng để tìm ra lờ i giả i tố i ư u
củ a bài toán lớ n ( optimal substructure)
Hai bài toán con trong quá trình phân rã có thể có chung mộ t số bài toán
con khác (overlapping subproblems).
Có thể hiể u
Hai tính chấ t đầ u tiên Có thể giả i bằ ng chia để trị và đệ quy
Tính chấ t thứ ba Đặ c trư ng cho tính hiệ u quả củ a quy hoạ ch độ ng
4
Bài toán giả i theo phư ơ ng pháp quy hoạ ch độ ng gọ i là
bài toán quy hoạ ch độ ng.
Công thứ c phố i hợ p nghiệ m củ a các bài toán con để có
nghiệ m củ a bài toán lớ n gọ i là công thứ c truy hồ i củ a
quy hoạ ch độ ng.
CÁC KHÁI NIỆM
CÁC KHÁI NIỆM
Tậ p các bài toán nhỏ nhấ t có ngay lờ i giả i để từ đó giả i
quyế t các bài toán lớ n hơ n gọ i là cơ sở quy hoạ ch độ ng.
Không gian luu trữ lờ i giả i các bài toán con để tìm cách
phố i hợ p chúng gọ i là bả ng phư ơ ng án củ a quy hoạ ch
độ ng.
5