Bài giảng Các hệ thống thông minh nhân tạo và ứng dụng - Chương 5: Bài toán thỏa mãn ràng buộc có nội dung trình bày về khái niệm bài toán thỏa mãn ràng buộc (CSP), đồ thị ràng buộc, CSP với kĩ thuật quay lui, CSP với tìm kiếm cục bộ, . Mời các bạn cùng tham khảo chi tiết nội dung bài giảng! | CÁC HỆ THỐNG THÔNG MINH NHÂN TẠO amp ỨNG DỤNG Bài toán thoả mãn ràng buộc THS. BÙI THỊ DANH KHOA CNTT Nội dung chính Bài toán thoả mãn ràng buộc CSP Đồ thị ràng buộc CSP với kĩ thuật quay lui CSP với tìm kiếm cục bộ 2 Bài toán thoả mãn ràng buộc CSP Được xem như tập con đặc biệt của bài toán tìm kiếm. Trạng thái được định nghĩa bởi tập các biến Xi có giá trị nằm trong miền D Có trường hợp mỗi biến có miền giá trị D khác nhau. Trạng thái đích được nhận biết thông qua một tập các ràng buộc trên việc kết hợp giá trị cho các biến. 3 Ví dụ Tô màu đồ thị Các biến WA NT Q NSW V SA T Mỗi biến đại diện cho một bang Miền giá trị D red green blue Tập ràng buộc các bang kề nhau không được giống màu WA NT WA SA NT SA Lời giải phép gán màu thoả mãn các ràng buộc chẳng hạn WA red NT green Q red NSW green V red SA blue T green 4 Ví dụ N-Hậu Các biến Xij Miền giá trị D 0 1 Các ràng buộc quot i j k Xij Xik Î 0 0 0 1 1 0 quot i j k Xij Xkj Î 0 0 0 1 1 0 quot i j k Xij Xi k j k Î 0 0 0 1 1 0 quot i j k Xij Xi k j-k Î 0 0 0 1 1 0 åX ij N i j 5 Ví dụ N-Hậu Các biến Qk Miền giá trị D 1 2 3 N Các ràng buộc quot i j non _ threatening Qi Qj 6 CSP trong thực tế Phân công công việc chẳng hạn phân công giảng dạy Lập lịch lớp học ở đâu và khi nào Lập lịch giao thông Tổ chức mạch điện 7 Nội dung chính Bài toán thoả mãn ràng buộc CSP Đồ thị ràng buộc CSP với kĩ thuật quay lui CSP với tìm kiếm cục bộ 8 Đồ thị ràng buộc constraint graph Các node tròn đại diện cho các biến Các node vuông đại diện cho ràng buộc Các cạnh nối các biến thông qua node ràng buộc liên quan 9 Đồ thị ràng buộc là hàm giá trị cho biết mức độ thoả mãn ràng buộc thứ i. Trọng số của một phép gán hay lời giải x 1 2 Weight x x j 1. Mục tiêu bài toán là tìm phép gán có trọng số lớn nhất Đối với CSP x 0 1 10 Ví dụ Tô màu đồ thị Các biến X WA NT SA Q NSW V T Miền giá trị D R G B Các ràng buộc 1 X WA NT 2 X NT SA . 11 Ví dụ Sudoku Các biến mỗi ô vuông Miền giá trị D 1 2 9 Các ràng buộc 1 X allDiff cột1 2 X .
