1
KHOA CÔNG NGHỆ THÔNG TIN
Phân Tích Thiết Kế Thuật Toán Nâng Cao
Nguyễn Phước Thắng
Vĩnh Long, ngày 27 tháng 11 năm 2022
TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT VĨNH LONG
2
NỘI DUNG:
TỔNG QUAN THUẬT TOÁN
1
ỨNG DỤNG THUẬT TOÁN
2
VÍ DỤ DEMO
3
3
1. TỔNG QUAN THUẬT TOÁN
a. Kỹ thuật Quy Hoạch Động (Dynamic Programming)
Nhà toán học Richard Bellman đã phát minh ra kỹ thuật Quy hoạch động vào năm 1953.
Kỹ thuật quy hoạch động là một trong những kỹ thuật giúp chúng ta thiết kế các chương trình có thời gian thực hiện tốt và hiệu quả
4
* Trong giải thuật đệ quy, một số bài toán con nào đó bị giải nhiều lần, do đó tốn rất nhiều thời gian.
* Giải pháp: Lưu trữ kết quả bài toán con, khi cần thì sử dụng kết quả đó mà không cần phải giải lại bài toán con.
* Do đó nhiều bài toán con nên cần sử dụng một bảng để lưu trữ kết quả của bài toán con.
* Tạo bảng bằng cách:
* Kết quả của bài toán ban đầu cũng nằm trong bảng này, do đó chỉ cần tra bảng để xác định kết quả của bài toán ban đầu.
5
Ưu điểm của quy hoạch động:
Quy hoạch động sẽ không đem lại hiệu quả khi:
6
Một bài toán khá quen thuộc là tính số tổ hợp chập k của n theo công thức truy hồi:
Công thức trên đã gợi ý cho chúng ta một giải thuật đệ qui như sau: �
7
Đánh giá độ phức tạp thuật toán đệ quy:
8
Áp dụng kỹ thuật qui hoạch động để khắc phục tình trạng trên, ta xây dựng một bảng gồm n + 1 hàng (từ 0 đến n) và n + 1 cột (từ 0 đến n) và điền giá trị cho C(i, j) theo qui tắc tam giác Pascal như sau:
i j | 0 | 1 | 2 | 3 | 4 |
0 | 1 | | | | |
1 | 1 | 1 | | | |
2 | 1 | 2 | 1 | | |
3 | 1 | 3 | 3 | 1 | |
4 | 1 | 4 | 6 | 4 | 1 |
9
Đánh giá độ phức tạp thuật toán quy hoạch động:
10
CÁC ỨNG DỤNG THUẬT TOÁN TRONG ĐỜI SỐNG:
11
DEMO CHƯƠNG TRÌNH:
12
CHÚC THẦY CÙNG CÁC ANH CHỊ DỒI DÀO SỨC KHỎE!