Bài giảng Phân tích thiết kế giải thuật: Branch and Bound - GV. Hà Đại Dương

Phương pháp quay lui, vét cạn có thể giải các bài toán tối ưu, bằng cách lựa chọn phương pháp tối ưu trong tất cả các lời giải tìm được. Nhưng nhiều bài toán không gian các lời giải là quá lớn, nên áp dụng phương pháp quay lui khó đảm bảo về thời gian cũng như kỹ thuật. Cho nên ta cần phải cải tiến thuật toán quay lui để hạn chế bớt việc duyệt các phương án. Có nhiều cách cải tiến, trong đó có phương pháp nhánh cận. Mời các bạn cùng tham khảo bài giảng để tìm hiểu cụ thể hơn về phương pháp nhánh cận.
Nội dung trích xuất từ tài liệu:
Bài giảng Phân tích thiết kế giải thuật: Branch and Bound - GV. Hà Đại Dương2/2/2017Analysis and Design of AlgorithmsLecture 14Branch and BoundLecturer: Ha Dai Duongduonghd@mta.edu.vn2/2/20171Nội dung1. Lược đồ chung2. Bài toán người du lịch3. Bài toán cái túi2/2/20172Nội dung1. Lược đồ chung2. Bài toán người du lịch3. Bài toán cái túi2/2/2017312/2/2017Giới thiệu2/2/20174Ý tưởng2/2/201752/2/2017622/2/2017Lược đồ chung2/2/201772/2/20178Nội dung1. Lược đồ chung2. Bài toán người du lịch3. Bài toán cái túi2/2/2017932/2/2017Bài toán2/2/201710Ý tưởng2/2/201711Cài đặt2/2/20171242/2/20172/2/2017132/2/2017142/2/2017155