CHƯƠNG 5 – CÁC PHƯƠNG PHÁP TÌM KIẾM LỜI GIẢI THỎA MÃN CÁC RÀNG BUỘC

2. Giải thuật quay lui vét cạn

Việc giải bài toán thỏa mãn các ràng buộc là tìm ra một phép gán giá trị cho tập các biến của bài toán sao cho tập các ràng buộc được thỏa mãn. Giả sử bài toán cần gán giá trị cho n biến, chúng ta có thể tìm lời giải của bài toán bằng các bước mô tả như sau: - Bắt đầu bằng phép gán rỗng, chưa gán giá trị cho biến nào cả { }. - Nếu tất cả các biến đã được gán giá trị, in ra lời giải và thoát khỏi chương trình - Tìm giá trị để gán cho biến chưa có giá trị mà không xung đột với các các biến đã được gán trước đó (xung đột hay không là dựa trên tập ràng buộc). Nếu không tìm được giá trị thỏa mãn các ràng buộc cho biến đang xét thì hủy bỏ phép gán giá trị cho biến liền trước đó và tìm giá trí mới cho nó. - Nếu biến đầu tiên không còn giá trị phù hợp để gán thì bài toán không có lời giải. Giải thuật gán giá trị cho n biến như trên gọi là giải thuật quay lui vét cạn hay thử và sai (backtracking). Trong giải thuật, mỗi bước thực hiện một phép gán với cách làm giống nhau và lời giải của bài toán chỉ xuất hiện ở bước gán cho biến cuối cùng. Giải thuật trên có thể cài đặt đệ quy như sau: Function Backtracking-Search(problem) returns a solution, or failure Return RescusiveBacktracking({},problem); --- Function RescusiveBacktracking(assignment, problem) returns a solution, or failure if (length(assignment)==n) return assignment ; var Å Chọn_biến_chưa_gán(problem, assignment); for each value in Miền_giá_trị(var,problem) if KiemTraNhấtQuán(assignment U{var=value}, problem) assignment= assignment U{var=value} RescusiveBacktracking(assignment, problem); assignment= assignment - {var=value} return failure; Bản chất của giải thuật RescusiveBacktracking là phép duyệt theo chiều sâu có thêm bước kiểm tra sự thỏa mãn của các ràng buộc ở mỗi bước. Thứ tự việc gán giá trị cho các biến trong bài toán tô màu đồ thị có thể biểu diễn bằng đồ thị sau: Một phần đồ thị biểu diễn thứ tự phép gán giá trị cho các biến của giải thuật Backtracking