Lecture 14
Branch and Bound
Nội dung
1. Lược đồ chung
2. Bài toán người du lịch
3. Bài toán cái túi
14 trang |
Chia sẻ: phuongt97 | Lượt xem: 618 | Lượt tải: 0
Nội dung tài liệu Bài giảng Phân tích và thiết kế thuật toán - Bài 14: Branch and Bound - Hà Đại Dương, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
2/2/2017
1
Lecture 14
Branch and Bound
Lecturer: Ha Dai Duong
duonghd@mta.edu.vn
Analysis and Design of Algorithms
2/2/2017 1
Nội dung
1. Lược đồ chung
2. Bài toán người du lịch
3. Bài toán cái túi
2/2/2017 2
Nội dung
1. Lược đồ chung
2. Bài toán người du lịch
3. Bài toán cái túi
2/2/2017 3
2/2/2017
2
Giới thiệu
2/2/2017 4
Ý tưởng
2/2/2017 5
2/2/2017 6
2/2/2017
3
Lược đồ chung
2/2/2017 7
2/2/2017 8
Nội dung
1. Lược đồ chung
2. Bài toán người du lịch
3. Bài toán cái túi
2/2/2017 9
2/2/2017
4
Bài toán
2/2/2017 10
Ý tưởng
2/2/2017 11
Cài đặt
2/2/2017 12
2/2/2017
5
2/2/2017 13
2/2/2017 14
2/2/2017 15
2/2/2017
6
Cài đặt
2/2/2017 16
2/2/2017 17
2/2/2017 18
2/2/2017
7
Khởi tạo
2/2/2017 19
Minh họa
2/2/2017 20
2/2/2017 21
2/2/2017
8
2/2/2017 22
Nội dung
1. Lược đồ chung
2. Bài toán người du lịch
3. Bài toán cái túi
2/2/2017 23
Bài toán
2/2/2017 24
2/2/2017
9
Ý tưởng
2/2/2017 25
2/2/2017 26
2/2/2017 27
2/2/2017
10
2/2/2017 28
2/2/2017 29
2/2/2017 30
2/2/2017
11
2/2/2017 31
Cài đặt
2/2/2017 32
2/2/2017 33
2/2/2017
12
2/2/2017 34
Cài đặt
• Khởi tạo
2/2/2017 35
Minh họa
• Cho bài toán
2/2/2017 36
2/2/2017
13
2/2/2017 37
2/2/2017 38
Bài tập
1. Thực hiện từng bước thuật toán nhánh cận
cho bài toán người du lịch trên đồ thị sau.
2/2/2017 39
2/2/2017
14
Bài tập
2. Cài đặt thuật toán giải bài toán người du lịch
(dựa trên thuật toán liệt kê các hoán vị) theo
phương pháp nhánh cận. Đánh giá độ phức tạp
thuật toán bằng lý thuyết, bằng thực nghiệm và
so sánh.
3. Cài đặt thuật toán giải bài toán cái túi (dựa trên
thuật toán liệt dãy nhị phân độ dài N) theo
phương pháp nhánh cận. Đánh giá độ phức tạp
thuật toán bằng lý thuyết, bằng thực nghiệm và
so sánh
2/2/2017 40
Các file đính kèm theo tài liệu này:
bai_giang_phan_tich_va_thiet_ke_thuat_toan_bai_14_branch_and.pdf