TAILIEUCHUNG - 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 . Thuật toán quay lui vởi chuôi nhị . Những chuỗi bit. 200 . Bài toan ba . Chu trình Hamilton .206 . Đường đi của người bán . Thuật toán quay luỉ vái những phép hoán . Sinh những hoán . Chu trình Hamilton vớỉ đổ thị dày . Bài toán quán hậu hòa bình . .217 . Thuật toán quay lui với những tố Sính tố hợp. .219 . Chứng minh tính đúng đắn của thuật toán . . . 220 . Phân tích thuật . Tính tôi ưu của thuật toán . .224 . 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ả. . 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

TỪ KHÓA LIÊN QUAN
TÀI LIỆU MỚI ĐĂNG
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.