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

1. Các bài toán thỏa mãn các ràng buộc

a. Bài toán 8 quân hậu Hãy đặt trên bàn cờ 8 quân hậu sao cho không có hai quân hậu nào cùng hang hoặc cùng cột hoặc cùng đường chéo. Bài toán 8 quân hậu có thể biểu diễn bởi 5 thành phần như sau: - Trạng thái: mảng một chiều 8 phần tử HAU[0,1,…,7], phần tử HAU[i] biểu diễn dòng đặt con hậu cột i. Ví dụ HAU[i]=j có nghĩa là con hậu cột I đặt ở dòng j. - Trạng thái đầu: Một mảng ngẫu nhiên 8 phần tử, mỗi phần tử nhận giá trị từ 0 đến 7 - Trạng thái đích: Gán các giá trị khác nhau phạm vi từ 0 đến 7 cho các phần tử của mảng sao cho i-HAU[i] ≠ j-HAU[j] (không nằm trên cùng đường chéo phụ) và i+HAU[i] ≠ j + HAU[j] (không nằm trên cùng đường chéo chính). - Chi phí: không xác định Trong bài toán này, trạng thái đích là không tường minh mà được xác định bởi tập các ràng buộc. Khác với các bài toán trước, lời giải của bài toán này không phải là đường đi từ trạng thái đầu đến trạng thái đích mà là một phép gán các giá trị cho các biến mô tả trong trạng thái của bài toán sao cho phép gán thỏa mãn các ràng buộc của trạng thái đích. Để giải các bài toán thỏa mãn các ràng buộc, chúng ta không cần xác định 5 thành phần như các bài toán trong các chương trước, mà chúng ta cần quan tâm đến các thành phần sau: - Tập các biến mô tả trạng thái của bài toán: HAU[0], HAU[1], .., HAU[7] trong bài toán 8 quân hậu (HAU[i] là số hiệu dòng đặt con hậu ở cột I, ví dụ HAU[0]=0 có nghĩa là con hậu cột đầu tiên (cột 0) sẽ đặt ở dòng đầu tiên (dòng 0). - Miền giá trị cho các biến: HAU[i] Є {0, 1, 2, 3, 4, 5, 6, 7} - Tập ràng buộc: với i≠j thì HAU[i] ≠HAU[j] (không có hai con hậu cùng hàng ngang), i-HAU[i] ≠ j-HAU[j] (không có hai con hậu nào cùng đường chéo phụ); i+HAU[i] ≠ j+HAU[j] (không có hai con hậu nào cùng đường chéo chính) Lời giải của bài toán là một phép gán giá trị trong miền giá trị cho các biến sao cho thỏa mãn các ràng buộc của bài toán. b. Bài toán tô màu đồ thị Sử dụng ba màu để tô bản đồ các tỉnh của một nước sao cho các tỉnh kề nhau thì có màu khác nhau. Ví dụ, nước Australia có 7 bang như hình vẽ, chỉ sử dụng ba màu: đỏ, xanh lơ và xanh da trời để tô màu 7 bang của nước Australia sao cho không có hai bang nào kề nhau lại có màu giống nhau. Bài toán này có thể mô tả bằng 3 thành phần như sau: - Tập các biến: WA, NT, Q, NSW, V, SA, T (các biến là các ký tự đầu của tên các bang) - Miền giá trị: 7 biến có thể nhận các giá trị trong tập {đỏ, xanh lá cây, xanh da trời} - Tập ràng buộc: WA≠NT, WA≠SA, NT≠SA, NT≠Q, SA≠Q, SA≠NSW, SA≠V, Q≠NSW, NSW≠V Lời giải của bài toán tô màu đồ thị là phép gán các giá trị {đỏ, xanh da trời, xanh lá cây} cho tập 7 biến thỏa mãn tập các ràng buộc. c. Bài toán giải mã các ký tự Tìm các chữ số thích hợp cho các ký tự để phép tính sau là đúng: Bài toán giải mã các ký tự được mô tả bằng 3 thành phần sau: - Tập các biến: T, W, O, F, U, R, N1, N2, N3 (N1, N2, N3 là 3 số nhớ của phép cộng ở các vị trí hàng đơn vị, hàng chục, hàng trăm) - Miền giá trị: Các biến có thể nhận các giá trị: {0, 1, .., 9} - Ràng buộc: T, W, O, F, U, R phải khác nhau đôi một; O + O = X +10.N1; N1 + W + W = U + 10.N2; N2 + T + T = O + 10.N3; F=N3; T≠0; F≠0 Lời giải của bài toán là một phép gán các chữ số từ 0 đến 9 cho các biến và thỏa mãn tập các ràng buộc.