16/11/2014 09:57:52 PM

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

Phương pháp thoả mãn ràng buộc.

Phương pháp thoả 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ả.

a) Chọn một đỉnh chưa được xét trong đồ thị tìm kiếm.

b) Á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.

c) 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 hện thời tới nút đang xét dẫn tới bế tắc.

d) 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 lai, sang bước sau.

e) Á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.

Ví dụ. Xét bài toán điền các chữ số phân biệt thay cho các chữ cái S, E, N, D, M, O, R, Y sao cho phép cộng sau là đúng:

SEND

+ MORE

= MONEY

Các ràng buộc ban đầu:

- Các chữ cái khác nhau không nhận cùng một giá trị.

- Các ràng buộc số học (cộng có nhớ hoặc không có nhớ.

Gọi C1, C2, C3, C4 lần lượt lá số nhớ của các cột từ phải sang trái. Khi đó ta xây dựng các ràng buộc cụ thể như sau:

E, N, D,O, R, Y thuộc tập {0 ..9} (1)

S, M thuộc tập {1..9} (2)

C1, C2, C3, C4 thuộc tập {0,1} (3)

D + E = Y + 10*C1 (4)

N + R + C1 = E + 10*C2 (5)

E + O + C2 = N + 10*C3 (6)

S + M + C3 = O + 10*C4 (7)

M = C4 (8)

Từ ràng buộc (2) và (8) suy ra M = 1 và C4=1 (9)

Từ ràng buộc (7) và (9) suy ra S +C3 = O + 9, lúc này có hai phương án để lựa chọn:

Phương án 1:

C3 = 0, khi đó ta có S = O + 9, như vậy S = 9 và O = 0 (10-1)

Từ ràng buộc (6) ta có E + C2 = N, suy ra C2 = 1 và

E + 1 = N (11-1)

Từ ràng buộc (5), ta có R + C1 = 9, như vậy R = 8 vàC1 = 1 (12-1)

(do kết hợp với các ràng buộc (2) và (10-1).

Từ ràng buộc (4) ta có D + E = Y +10. Đến bứơc này ta có thể khảng định các giá trị của D, E, Y chỉ có thể nhận trong tập {2, 3, 4, 5, 6, 7}. Ngoài ra D + E >= 12. Vì vậy chỉ có các khả năng sau có thể xãy ra:

- D = 5 và E = 7

- D = 7 và E = 5 (hai truờng hợp này Y = 2)

- D = 6 và E = 7

- D = 7 và E = 6 (hai trường hợp sau Y = 3)

Xét khả năng thứ nhất. Từ ràng buộc (11-1) ta suy ra N = 8 mâu thuẫn với (12-1) nên bị loại

Xét khả năng thứ hai. Từ ràng buộc (11-1) ta suy ra N= 6. Kiểm tra điều kiện bài toán đều thoả mãn. Vậy ta có nghiệm là:

S = 9, E = 5, N= 6, D = 7, M= 1, O = 0, R = 8, Y = 2.

Xét khả năng thứ ba. Từ ràng buộc (11-1) suy ra N = 8 mâu thuẫn với (12-1)

Xét khả năng thứ tư. Từ ràng buộc (11-1) suy ra N=7 = D mâu thuẫn.

Phương án 2.

C3 = 1. Từ ràng buộc (7) ta có S = O + 8, suy ra S = 8 và O = 0 (10-2)

(vì M=1 và S <= 9).