Khác biệt giữa bản sửa đổi của “Quay lui (khoa học máy tính)”
Nội dung được xóa Nội dung được thêm vào
n r2.7.3) (Bot: Thêm sr:Бектрекинг |
n Robot: Sửa đổi hướng |
||
Dòng 1:
'''Quay lui''' ([[tiếng Anh]]: ''backtracking'') là một chiến lược tìm kiếm lời giải cho các [[bài toán thỏa mãn ràng buộc]]. Người đầu tiên đề ra thuật ngữ này (''backtrack'') là [[danh sách nhà toán học|nhà toán học]] người [[Hoa Kỳ|Mỹ]] [[Derrick Henry Lehmer|D. H. Lehmer]] vào những năm 1950.
== Giải thích ==
Dòng 7:
== Cài đặt ==
Về bản chất, tư tưởng của phương pháp 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 chiều sâu|tìm kiếm theo độ sâu]] trong một tập hợp các lời giải. Trong quá trình tìm kiếm, nếu ta 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 nơi có các hướng khác và thử hướng lựa chọn tiếp theo. Khi đã thử hết các lựa chọn xuất phát từ điểm lựa chọn đó, ta quay lại điểm lựa chọn trước đó và thử hướng lựa chọn tiếp theo tại đó. Quá trình tìm kiếm thất bại khi không còn điểm lựa chọn nào nữa.
Quy trình đó thường được cài đặt bằng một hàm [[đệ quy]] mà trong đó mỗi thể hiện của hàm lấy thêm một biến và lần lượt gán tất cả các giá trị có thể cho biến đó, với mỗi lần gán trị lại gọi chuỗi đệ quy tiếp theo để thử các biến tiếp theo. Chiến lược quay lui tương tự với tìm kiếm theo độ sâu nhưng sử dụng ít không gian bộ nhớ hơn, nó chỉ lưu giữ trạng thái của một lời giải hiện tại và cập nhật nó.
Dòng 14:
== Heuristic ==
Người ta thường sử dụng một số phương pháp [[heuristic (khoa học máy tính)|heuristic]] để tăng tốc cho quá trình quay lui. Do các biến có thể được xử lý theo thứ tự bất kỳ, việc thử các biến bị ràng buộc chặt nhất (nghĩa là các biến có ít lựa chọn về giá trị nhất) thường có hiệu quả do nó tỉa [[
Các cài đặt quay lui phức tạp thường sử dụng một hàm biên, hàm này kiểm tra xem từ lời giản chưa đầy đủ hiện tại có thể thu được một lời giải hay không, nghĩa là nếu đi tiếp theo hướng hiện tại thì liệu có ích hay không. Nhờ đó, một kiểm tra biên phát hiện ra các lời giải dở dang chắc chắn thất bại có thể nâng cao hiệu quả của tìm kiếm. Do hàm này hay được chạy, có thể tại mỗi bước, nên chi phí tính toán các biên cần tối hiểu, nếu không, hiệu quả toàn cục của thuật toán sẽ không được cải tiến. Các hàm kiểm tra biên được tạo theo kiểu gần như các hàm heuristic khác: nới lỏng một số điều kiện của bài toán.
| |||