M C ỤC LỤ
Danh mục hình vẽ .....................................................................................................iv
Danh mục bảng .........................................................................................................vi
Danh mục thuật ngữ tiếng Anh ............................................................................. vii
Chương 1. MỞ ĐẦU ................................................................................................. 1
1.1. Lời mở đầu ....................................................................................................... 1
1.2. Các khái niệm và thuật ngữ cơ sở .................................................................... 3
1.2.1. Bài toán tính toán, thuật toán và độ phức tạp tính toán của thuật toán . 3
1.2.2. Các kí hiệu tiệm cận ............................................................................... 6
1.2.3. Độ phức tạp tính toán của bài toán ........................................................ 8
1.2.4. NP- đầy đủ (NP – completeness)......................................................... 11
1.3. Một số cách tiếp cận giải các bài toán NP-khó .............................................. 18
1.3.1. Phương pháp xấp xỉ .............................................................................18
1.3.2. Phương pháp xác xuất .......................................................................... 19
1.3.3. Phương pháp heuristic .......................................................................... 20
1.4. Bài toán đóng thùng ....................................................................................... 21
1.4.1. Phát biểu bài toán ................................................................................. 21
1.4.2. Các biến thể của bài toán đóng thùng .................................................. 23
1.4.3. Ứng dụng của bài toán đóng thùng ...................................................... 25
Chương 2 MỘT SỐ PHƯƠNG PHÁP GIẢI BÀI TOÁN ĐÓNG THÙNG ..... 27
2.1. Tổng quan các phương pháp giải bài toán đóng thùng .................................. 27
2.2. Các phương pháp heuristic đơn giản ............................................................. 27
2.2.1. Các thuật toán trực tiếp ........................................................................ 27
2.2.2. Các phương pháp không trực tiếp ........................................................ 34
2.3. Phương pháp xấp xỉ ....................................................................................... 37
Chương 3 THUẬT TOÁN DI TRUYỀN ............................................................... 43
3.1. Sơ lược về tính toán tiến hóa và thuật toán di truyền .................................... 43
3.1.1. Lịch sử phát triển ................................................................................. 43
3.1.2. Đặc điểm và khả năng ứng dụng của tính toán tiến hóa ...................... 45
3.2. Sơ đồ hoạt động của thuật toán di truyền ...................................................... 46
3.2.1. Giới thiệu một số khái niệm ................................................................. 46
