Khác biệt giữa bản sửa đổi của “Quay lui (khoa học máy tính)”

 

== Giải thích ==

 

Phương pháp quay lui có quan hệ chặt chẽ với [[tìm kiếm tổ hợp]]

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 độ 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.

 

 

Để tăng tốc quá trình tìm kiếm, khi một giá trị được chọn, trước khi thực hiện lời gọi đệ quy, thuật toán thường xóa bỏ giá trị đó khỏi miền xác định của các biến có mâu thuẫn chưa được gán (kiểm tra tiến - ''forward checking'') và kiểm tra tất cả các hằng số để tìm các giá trị khác đã bị loại trừ bởi giá trị vừa được gán (lan truyền ràng buộc - ''constraint propagation'').

 

== Heuristic ==

 

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.

 

 

Sử dụng chiến lược quay lui dùng để giải bài toán liệt kê các cấu hình. Mỗi cấu hình được xây dựng bằng cách xây dựng từng phần tử, mỗi phần tử được chọn bằng cách thử tất cả các khả năng.'''

[[Tập tin:Thuật_toán_quay_lui,_Cây_tìm_kiếm_quay_lui.JPG]]

 

Tiếng Anh:

 

[[Thể loại:Vận trù học]]

[[en:Backtracking]]

[[es:Vuelta Atrás]]

[[fr:Retour sur trace]]

[[ko:퇴각검색]]