|
== 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 [[thuật toán tìm kiếm theo cây|cây tìm kiếm]] từ sớm (cực đại hóa ảnh hưởng của lựa chọn ''sớm'' hiện hành).
Several [[heuristic (computer science)|heuristic]]s are common to speed up the process. Because the variables can be processed in any order, it is generally efficient to try the most constrained ones first (i.e. the ones with fewest value options) as this prunes the [[Tree search algorithm|search tree]] early (maximizes the impact of the current ''early'' choice).
When choosing which value to assign, many implementations use forward checking to see which value restricts the least number of values, in the anticipation that such a choice is a) more likely to preserve a possible solution and b) a solution has been found when the number of outstanding constraints has been reduced to zero.
Sophisticated backtracking implementations often use a bounding function, which checks whether it is possible to obtain a solution, for the current partial solution. Thus, a bounding test that detects partial solutions that fail can improve search efficiency. Because it is run often, possibly at every step, the computational cost of bounding needs to be minimal, otherwise the overall efficiency of the algorithm is not improved. Effective bounding functions are created in a similar way to other [[Heuristic#Computer_Science|heuristic]] functions - by relaxing the rules of the problem slightly.
When backtracking is used in a [[constraint programming]] language, an added overhead occurs since information about the constraints, used by the constraint solver itself, needs to be updated as well. In these languages, a simple [[depth-first search]] is an adequate implementation technique, as used in [[Planner programming language|Planner]] and [[Prolog]].
In addition to retaining minimal recovery values used in backing up, backtracking implementations commonly keep a [[variable trail]], to record value change history. An efficient implementation will avoid creating a variable trail entry between two successive changes when there is no choice point, as the backtracking will erase all of the changes as a single operation.
An alternative to the variable trail is to keep a time stamp of when the last change was made to the variable. The time stamp is compared to the time stamp of a choice point. If the choice point has an associated time later than that of the variable, it is unnecessary to revert the variable when the choice point is backtracked, as it was changed before the choice point occurred.
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.
==Ví dụ ==
| 