Bài viết sưu tầm

Phương pháp thỏa mãn ràng buộc.

Phương pháp thỏa mãn ràng buộc hỗ trợ cho phương pháp sinh và thử, khi chú ý tới một số ràng buộc áp đặt lên các nút trong không gian bài toán. Mục đích đặt ra là xác định đường đi trong đồ thị không gian bài toán, đường đi từ trạng thái đầu đến trạng thái cuối đáp ứng một vài ràng buộc nào đó. Do vậy quá trình tìm kiếm lời giải bao gồm hai phần liên quan chặt chẽ với nhau:

• Tìm kiếm trong không gian các ràng buộc.
• Tìm kiếm trong không gian các bài toán ban đầu.

Nội dung của phương pháp như sau: Thực hiện các bước từ a) đến e) dưới đây cho đến khi tìm được lời giải đầy đủ của bài toán hoặc tất cả các đường đều đã duyệt qua nhưng không cho kết quả.

1. Chọn một đỉnh chưa được xét trong đồ thị tìm kiếm.
2. Áp dụng các luật suy diễn trên các ràng buộc đối với đỉnh đã chọn để tạo ra tập các ràng buộc mới.
3. Nếu tập các ràng buộc mới có mâu thuẫn thì đưa ra thông báo đường đi hiện thời tới nút đang xét dẫn tới bế tắc.
4. Nếu tập ràng buộc mô tả lời giải đầy đủ của bài toán thì dừng và đưa ra thông báo thành công. Ngược lại, sang bước sau.
5. Áp dụng các luật biến đổi không gian trạng thái tương ứng để tạo ra lời giải bộ phận, tương hợp với tập các ràng buộc hiện thời. Thêm các lời giải bộ phận này vào đồ thị tìm kiếm.