TAILIEUCHUNG - 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

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 .

• Kỹ thuật lập trình
• Bài giảng Các hệ thống thông minh nhân tạo
• Hệ thống thông minh nhân tạo
• Bài toán thỏa mãn ràng buộc
• Đồ thị ràng buộc
• Kĩ thuật quay lui
• Tìm kiếm cục bộ
• Trí tuệ nhân tạo
• Mô hình tính toán hành vi con người
• Hệ thống tính toán hành xử một cách thông minh
• Biểu diễn tri thức
• Hệ thống logic
• Logic mệnh đề
• Logic bậc nhất
• Ngôn ngữ logic
• Bài toán tìm kiếm 1
• Cây tìm kiếm
• Thuật toán tìm kiếm mù
• Bài toán tìm đường đi
• Bài toán tìm kiếm 2
• Tìm kiếm tham lam
• Thuật giải A*
• Hàm ước lượng mức độ
• Hạn chế của logic mệnh đề
• Qui tắc De Morgan
• Phép đồng nhất
• Máy học
• Phương pháp Naïve Bayes
• Phương pháp ID3
• Phương pháp ILA
• Thuật toán máy học
• Bài giảng Tìm kiếm heuristic leo đồi
• Thuật giải di truyền
• Thuật giải leo đồi
• Các thuật toán tìm kiếm cục bộ
• Lựa chọn của thuật giải di truyền
• Nội dung về thuật giải leo đồi
• Phân tích thuật toán
• Thiết kế thuật toán
• Bài giảng Phân tích thuật toán
• Bài toán cây phủ tối thiểu
• Bài toán người giao hàng
• Bài giảng Trí tuệ nhân tạo
• Giải quết vấn đề
• Chiến lược tìm kiếm
• Tri thức bổ sung
• Giải thuật tìm kiếm cục bộ
• Lập trình phần mềm
• Ngôn ngữ lập trình C
• Ngôn ngữ lập trình
• Chiến lược tham lam
• Tối ưu cục bộ
• Tìm kiếm lời giải tối ưu cục bộ
• Giải thuật tối ưu hóa rừng cây
• Lưới tính toán
• Công việc độc lập
• Bài toán lập lịch
• Giải thuật FOA
• Gieo mầm cục bộ
• Đàn kiến xây dựng dóng hàng
• Mạng tương tác protein
• Dóng hàng mạng PPI
• Các thuật toán SPINAL
• Bài toán người du lịch
• Giải thuật meta heuristic
• Tối ưu hóa tổ hợp
• Lý thuyết khoa học máy tính