Đang chuẩn bị liên kết để tải về tài liệu:
Giáo trình - Một số vấn đề về thuật toán - chương 7

Chương 7: Thuật toán quay lui Thường thường khi ta giải bài toán, nhiều khi không có cách nào tốt hơn là thử tất cả các khả năng của nghiệm bài toán có thể xảy ra. Cách tiếp cận như vậy người ta gọi là tìm kiếm toàn diện, như vậy việc tìm lời giải rất chậm, nhưng nhiều khi có còn hơn không có lời giải nào! | ChươNq 7 THUẬT TOÁN QUAY LUI 7.1. Thuật toán quay lui vởi chuôi nhị phân.200 7.1.1. Những chuỗi bit. 200 7.1.2. Bài toan ba lô.205 7.1.3. Chu trình Hamilton .206 7.1.4. Đường đi của người bán hang.210 7.2. Thuật toán quay luỉ vái những phép hoán vị.212 7.2.1. Sinh những hoán vị.212 7.2.2. Chu trình Hamilton vớỉ đổ thị dày đặc.216 7.2.3. Bài toán quán hậu hòa bình . .217 7.3. Thuật toán quay lui với những tố hợp.219 7.3.1 Sính tố hợp. .219 7.3.2. Chứng minh tính đúng đắn của thuật toán . . . 220 7.3.3. Phân tích thuật toán.222 7.3.4. Tính tôi ưu của thuật toán . .224 7.4. Bàỉ tập. .226 Thường thường khi ta giải bài toán nhiều khi không có cách nào tốt hơn là thử tất cả các khả năng của nghiệm bài toán có thể xảy ra. Cách tiếp cận như vây người ta gọi là tìm kiêm toàn diện như vây việc tìm lời giải rất chậm nhưng nhiều khi có còn hơn không có cách giải nào Đặc biệt khi cỡ bài toán đủ nhồ để ta có ihế kiên trì giải được. Kỷ thuật thuật toán dể gỉảỉ theo kiểu này là sủr dụng thuật toán chia để trị thích hợp nhất. Rất nhiều bài toán tìm kiếm toàn diện có thể giầm dáng kể độ phức tạp đến bằng bài toán sinh ra những đối tượng tổ hợp đơn giản thường thường nhất là sinh ra chuỗi sinh hoán vị và sinh ra tổ hợp. Vì vậy ta nghiên cứu trong chương này những thuật toán công cụ cơ bản Những thuật toán cho việc sinh ra những đối tượng cơ bản như Sinh ra 2fl chuỗi nhị phân có đô dài n bit. 200 Chương 7. Thuật toán quay lui Sinh ra ìỉ chuôi k bit từ chuỗi có đô dài n. Sinh ra rt hoán vị từ n đốì tượng. Sinh ra w- Ị tổ hợp từ n vật chọn lây r vật một lẫn. r n r Kĩ thuật tỉa nhánh trong tìm kiếm toàn diện cho ta một phương pháp quay lui nhanh chóng vầ có hiệu quả. 7.1. THUẬT TOÁN QUAY LUI VỚI CHUổl NHỊ PHÂN Trong phần này ta nghiên cứu nguyên tắc chung về thuật toán quaý lui vớì chuôi nhị phân với fc-chuỗi kĩ thuật tỉa đi những nhánh không cần thiết khi tìm lời giải và học cách viết một thuật toán quay lui như thế nào. Nhửng cơ sở trên được áp dụng cho một dạng bài toán ba lồ bài toán