TAILIEUCHUNG - Phân tích thiết kế giải thuật - Chương 6: Giải thuật quay lui

Một phương pháp tổng quát để giải quyết vấn đề: thiết kế giải thuật tìm lời giải cho bài tóan không phải là bám theo một tập qui luật tính tóan được xác định mà là bằng cách thử và sửa sai (trial and error). Khuôn mẫu thông thường là phân rã quá trình thử và sửa sai thành những công tác bộ phận. Thường thì những công tác bộ phận này được diễn tả theo lối đệ quy một cách thuận tiện và bao gồm việc thăm dò một số hữu hạn những công tác con | Chương 6 Giải thuật quay lui Giải thuật quay lui Giải thuật nhánh-và-cận Giải thuật quay lui Một phương pháp tổng quát để giải quyết vấn đề: thiết kế giải thuật tìm lời giải cho bài tóan không phải là bám theo một tập qui luật tính tóan được xác định mà là bằng cách thử và sửa sai (trial and error). Khuôn mẫu thông thường là phân rã quá trình thử và sửa sai thành những công tác bộ phận. Thường thì những công tác bộ phận này được diễn tả theo lối đệ quy một cách thuận tiện và bao gồm việc thăm dò một số hữu hạn những công tác con. Ta có thể coi toàn bộ quá trình này như là một quá trình tìm kiếm (search process) mà dần dần cấu tạo và duyệt qua một cây các công tác con. Cho một bàn cờ n n với n2 ô. Một con hiệp sĩ – được di chuyển tuân theo luật chơi cờ vua – được đặt trên bàn cở tại ô đầu tiên có tọa độ x0, y0. Vấn đề là tìm một lộ trình gồm n2 –1 bước sao cho phủ toàn bộ bàn cờ (mỗi ô được viếng đúng một lần). Cách rõ ràng để thu giảm bài toán phủ n2 ô là xét bài toán, hoặc

TÀI LIỆU LIÊN QUAN
TỪ KHÓA LIÊN QUAN
Đã 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.