›
›

Bài giảng Trí tuệ nhân tạo - Bài 5: Giải quyết vấn đề. Thỏa mãn ràng buộc - Thân Quang Khoát

Download
Trí Tuệ Nhân Tạo  
(Artificial Intelligence)  
Thân Quang Khoát  
[email protected]  
Viện Công nghệ thông tin và Truyền thông  
Trường Đại Học Bách Khoa Hà Nội  
Năm học 2020  
Nội dung môn học:  
n Giới thiệu về Trí tuệ nhân tạo  
n Tác tử  
n Giải quyết vấn đề: Tìm kiếm, Thỏa mãn ràng buộc  
n Logic và suy diễn  
n Biểu diễn tri thức  
n Học máy  
Trí tuệ nhân tạo  
2
Ràng buộc  
n Một ràng buộc (constraint) là một quan hệ trên một tập các biến  
q Mỗi biến có (gắn với) một tập các giá trị có thể nhận – gọi là miền  
giá trị (domain)  
q Trong môn học này, chúng ta chỉ xét các miền hữu hạn các giá trị  
rời rạc  
n Một ràng buộc có thể được biểu diễn bằng  
q Một biểu thức (toán học / logic)  
q Một bảng liệt kê các phép gán giá trị phù hợp cho các biến  
n Ví dụ về ràng buộc  
q Tổng các góc trong một tam giác là 180o  
q Độ dài của từ W là 10 ký tự  
q X nhỏ hơn Y  
q Tuấn có thể tham dự buổi seminar vào thứ 3 sau 14h  
q …  
Trí tuệ nhân tạo  
3
Bài toán thỏa mãn ràng buộc  
n Một bài toán thỏa mãn ràng  
buộc (Constraint Satisfaction  
Problem – CSP) bao gồm:  
q Một tập hữu hạn các biến X  
q Miền giá trị (một tập hữu hạn các  
giá trị) cho mỗi biến D  
q Một tập hữu hạn các ràng buộc C  
n Một lời giải (solution) của bài toán  
thỏa mãn ràng buộc là một phép  
gán đầy đủ các giá trị của các  
biến sao cho thỏa mãn tất cả các  
ràng buộc  
Ví dụ:  
Các biến x1,…,x6.  
Miền giá trị {0,1}.  
Các ràng buộc:  
•x1+x2+x6=1  
•X1-x3+x4=1  
•x4+x5-x6>0  
•x2+x5-x6=0  
n Một bài toán thỏa mãn ràng buộc  
có thể được biểu diễn bằng một  
đồ thị (graph)  
Trí tuệ nhân tạo  
4
Ví dụ: Bài toán tô màu bản đồ (1)  
n Các biến: WA, NT, Q, NSW,  
V, SA, T  
n Các miền giá trị: D = {red,  
green, blue}  
n Các ràng buộc: Các vùng liền  
kề nhau phải có màu khác  
nhau  
n Ví dụ:  
q WA ≠ NT  
q (WA,NT) = {(red,green),  
(red,blue), (green,red),  
(green,blue), (blue,red),  
(blue,green)}  
Trí tuệ nhân tạo  
5
Ví dụ: Bài toán tô màu bản đồ (2)  
n Các lời giải là các phép  
gán đầy đủ và chính xác  
(thỏa mãn tất cả các ràng  
buộc)  
n Ví dụ: WA=red,  
NT=green, Q=red,  
NSW=green, V=red,  
SA=blue, T=green  
Đồ thị các ràng buộc  
n Đối với bài toán thỏa mãn  
ràng buộc nhị phân (binary  
CSP): Mỗi ràng buộc chỉ  
liên quan đến 2 biến  
n Đồ thị các ràng buộc  
(constraint graph)  
q Các nút biểu diễn các biến  
q Các cạnh biểu diễn các ràng  
buộc  
Trí tuệ nhân tạo  
7
Các kiểu bài toán thỏa mãn ràng buộc  
n Các biến rời rạc  
q Các miền giá trị hữu hạn  
n Với n biến và kích thước miền giá trị d, thì số lượng các phép gán  
đầy đủ giá trị cần xét là O(dn)  
n Ví dụ: Các bài toán thỏa mãn ràng buộc nhị phân (Boolean CSPs)  
q Các miền giá trị vô hạn  
n Miền giá trị các số nguyên, các chuỗi, ...  
n Ví dụ: Trong bài toán xếp lịch công việc, các biến là các ngày bắt  
đầu và kết thúc đối với mỗi công việc  
n Cần một ngôn ngữ biểu diễn ràng buộc (constraint language), ví dụ:  
StartJob1 + 5 ≤ StartJob3  
n Các biến liên tục  
q Ví dụ: Các mốc thời gian bắt đầu và kết thúc đối với các quan  
sát bằng kính viễn vọng không gian Hubble  
q Bài toán với các ràng buộc tuyến tính có thể giải quyết được ở  
mức chi phí thời gian đa thức.  
Trí tuệ nhân tạo  
8
Các kiểu ràng buộc  
n Ràng buộc đơn (unary constraint) chỉ liên quan đến 1  
biến  
q Ví dụ: SA ≠ green  
n Ràng buộc nhị phân (binary constraint) liên quan đến 2  
biến  
q Ví dụ: SA ≠ WA  
n Ràng buộc bậc cao (higher-order constraint) liên quan  
đến nhiều hơn 2 biến  
q Ví dụ: Các ràng buộc trong bài toán mật mã số học (trình bày ở  
slide tiếp theo)  
Trí tuệ nhân tạo  
9
Ví dụ: Bài toán mật mã số học  
n Các biến: F T U W R O X1 X2 X3 (các nhớ của các phép +)  
n Miền giá trị: {0,1,2,3,4,5,6,7,8,9}  
n Các ràng buộc: Giá trị của các biến (F,T,U,W,R,O) khác nhau  
q O + O = R + 10 * X1  
q X1 + W + W = U + 10 * X2  
q X2 + T + T = O + 10 * X3  
q X3 = F  
q T ≠ 0  
q F ≠ 0  
Trí tuệ nhân tạo  
10  
Vài bài toán CSP trong thực tế  
n Các bài toán giao nhiệm vụ  
q Ví dụ: Giáo viên nào dạy lớp nào?  
n Các bài toán lập thời khóa (gian) biểu  
q Ví dụ: Lớp học nào được dạy vào thời gian nào và ở đâu?  
n Các bài toán lập lịch vận tải (giao hàng) của các công ty  
n Các bài toán lập lịch sản xuất của các nhà máy  
n Lưu ý: Nhiều bài toán thực tế liên quan đến các biến có giá  
trị thực (liên tục)  
Trí tuệ nhân tạo  
11  
Sắp lịch tàu điện ngầm Tokyo  
Tìm kiếm lời giải bằng kiểm thử (1)  
n Là phương pháp giải quyết vấn đề tổng quát nhất  
n Phương pháp giải quyết bằng kiểm thử (Generate and  
Test)  
q Sinh ra một khả năng (candidate) của lời giải  
q Kiểm tra xem khả năng này có thực sự là một lời giải  
n Áp dụng phương pháp kiểm thử đối với bài toán CSP  
q Bước 1. Gán các giá trị cho tất cả các biến  
q Bước 2. Kiểm tra xem tất cả các ràng buộc được thỏa mãn hay  
không  
q Lặp lại 2 bước này cho đến khi tìm được một phép gán thỏa mãn  
Trí tuệ nhân tạo  
13  
Tìm kiếm lời giải bằng kiểm thử (2)  
n Điểm yếu nghiêm trọng của phương pháp tìm kiếm bằng  
kiểm thử là việc phải xét quá nhiều các khả năng gán mà  
không thỏa mãn các ràng buộc  
n Ví dụ  
q
q
q
Các biến X,Y,Z lấy các giá trị {1,2}  
Các ràng buộc: X=Y, X¹Z, Y>Z  
Các phép (khả năng) gán: (1,1,1); (1,1,2); (1,2,1);  
(1,2,2); (2,1,1); (2,1,2); (2,2,1)  
Trí tuệ nhân tạo  
14  
Tìm kiếm lời giải bằng kiểm thử (3)  
n Làm thế nào để cải thiện phương pháp kiểm thử?  
q Sinh ra các khả năng (các phép gán giá trị) một cách thông minh  
hơn  
n Không theo thứ tự tuần tự  
n Sử dụng các kết quả (thông tin) thu được từ bước kiểm tra  
(bước 2)  
q Phát hiện sớm (từ trước) các mâu thuẫn  
n Các ràng buộc được kiểm tra ngay sau khi mỗi biến được gán  
giá trị (chứ không phải đợi đến khi tất cả các biến được gán giá  
trị)  
Trí tuệ nhân tạo  
15  
Tìm kiếm quay lui (1)  
n Tìm kiếm quay lui (backtracking) là giải thuật tìm kiếm  
được sử dụng phổ biến nhất trong CSP  
q Dựa trên giải thuật tìm kiếm theo chiều sâu (depth-first search)  
q Mỗi lần gán, chỉ làm việc (gán giá trị) cho một biến  
q (Tìm kiếm bằng kiểm thử: mỗi lần gán xác định các giá trị cho tất  
cả các biến)  
n Phương pháp tìm kiếm quay lui đối với bài toán CSP  
q Gán giá trị lần lượt cho các biến – Việc gán giá trị của biến này  
chỉ được làm sau khi đã hoàn thành việc gán giá trị của biến khác  
q Sau mỗi phép gán giá trị cho một biến nào đó, kiểm tra các ràng  
buộc có được thỏa mãn bởi tất cả các biến đã được gán giá trị  
cho đến thời điểm hiện tại – Quay lui (backtrack) nếu có lỗi  
(không thỏa mãn các ràng buộc)  
Trí tuệ nhân tạo  
16  
Tìm kiếm quay lui (2)  
n Các yếu tố ảnh hưởng đến phương pháp tìm kiếm quay  
lui  
q Thứ tự được xét của các biến?  
n Ưu tiên các biến quan trọng hơn (được định nghĩa tùy vào bài  
toán cụ thể)  
n Ưu tiên xét trước các biến có ít giá trị (miền giá trị nhỏ)  
n Ưu tiên xét trước các biến tham gia vào nhiều ràng buộc  
q Với mỗi biến, thứ tự được xét của các giá trị?  
n Thứ tự ưu tiên của các giá trị với mỗi biến được định nghĩa tùy  
thuộc vào bài toán cụ thể  
Trí tuệ nhân tạo  
17  
Giải thuật tìm kiếm quay lui  
Trí tuệ nhân tạo  
18  
Tìm kiếm quay lui: Ví dụ (1)  
NT  
Q
WA  
SA  
NSW  
V
Trí tuệ nhân tạo  
19  
Tìm kiếm quay lui: Ví dụ (2)  
NT  
Q
WA  
SA  
NSW  
V
Trí tuệ nhân tạo  
20  
Tải về để xem bản đầy đủ
pdf 44 trang Thùy Anh 17260 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Trí tuệ nhân tạo - Bài 5: Giải quyết vấn đề. Thỏa mãn ràng buộc - Thân Quang Khoát", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfbai_giang_tri_tue_nhan_tao_bai_5_giai_quyet_van_de_thoa_man.pdf