Page 0 of 84 MỤC LỤC Phương pháp duyệt Chuyên đề1. Duyệt vét cạn.................................................................................................................. 1 Chuyên đề2. Duyệt nhánh cạnh..................................................................................................... 12 Chuyên đề3. Duyệt ưu tiên............................................................................................................... 24 Tìm kiếm nhịphân Chuyên đề4. Tìm kiếm nhịphân vàứng dụng......................................................................... 27 Xửlýbít Chuyên đề5. Xửlý bit.......................................................................................................................... 30 Quy hoạch động Chuyên đề6. Quy hoạch động cơ bản.......................................................................................... 36 Chuyên đề7. Quy hoạch động trạng thái.................................................................................... 49 Đồthị Chuyên đề8. Tìm kiếm theo chiều rộng..................................................................................... 58 Chuyên đề9. Tìm kiếm theo chiều sâu........................................................................................ 69 ăn Tr Võ V ị - CQB | Confidential PHƯƠNG PHÁP DUYỆT Chuyên đề1.Duyệt vétcạn-Backtracking ĩa nhưng Quay lui, vét cạn, thử sai, duyệt… là một số tên gọi tuy không đồng ngh cùng chỉ một phương pháp trong tin học: tìm nghiệm của một bài toán bằng cách xem xét tất cả các phương án có thể. Đối với con người phương pháp này thường không khả thi vì số phương án cần kiểm tra lớn. Tuy nhiên đối với máy tính, nhờ tốc độ xử lý nhanh, máy tính có thể giải rất nhiều bài toán bằng phương pháp quay lui vét cạn. Người đầu tiên đề ra chiến lược này là nhà toán học người Mỹ Derrick Henry Lehmer (1905–1991) vào những năm 1950. Ưu điểm của phương pháp quay lui, vét cạn là luôn bảo đảm tìm ra nghiệm đúng, chính xác. Tuy nhiên, hạn chế của phương pháp này là thời gian thực thi lâu, độ phức tạp lớn. Vềbản chất, tư tưởng của phương pháp này là thử từng khả năng cho đến khi tìm thấy lời giải đúng. Đó là một quá trình tìm kiếm theo độ sâu trong một tập các lời giải. Trong quá trình tìm kiếm, nếu gặp một hướng lựa chọn không thỏa mãn, ta quay lui, về điểm lựa chọn có các hướng khác và thử hướng lựa chọn tiếp theo. ã th Khi đ ửhết tất cả các hướng lựa chọn xuất phát từ một điểm, ta quay lại điểm ư lựa chọn kế trước. Quá trình tìm kiếm kết thúc khi không còn h ớng lựa chọn nào đểthử. Chiến lược quay lui tương tự với tìm kiếm theo độ sâu nhưng tốn ít không gian nhớhơn, thời gian tìm kiếm lại nhanh hơn. Mô hình thuật toán Backtracking: procedure try(i:integer); begin ...