Bài giảng Trí tuệ nhân tạo - Bài 5: Giải quyết vấn đề Tìm kiếm, Thỏa mãn ràng buộc (Phần 3) - Nguyễn Nhật Quang
Trí Tuệ Nhân Tạo
Nguyễn Nhật Quang
Trường Đại học Bách Khoa Hà Nội
Viện Công nghệ Thông tin và Truyền thông
Năm học 2012-2013
Nội dung môn học:
Giới thiệu về Trí tuệ nhân tạo
Tác tử
Giải quyết vấn đề: Tìm kiếm, Thỏa mãn ràng buộc
Logic và suy diễn
Biểu diễn tri thức
Biểu diễn tri thức không chắc chắn
Trí tuệ nhân tạo
2
Ràng buộc
Một ràng buộc (constraint) là một quan hệ trên một tập các biến
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)
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
Một ràng buộc có thể được biểu diễn bằng
Một biểu thức (toán học / logic)
Một bảng liệt kê các phép gán giá trị phù hợp cho các biến
Ví dụ về ràng buộc
Tổng các góc trong một tam giác là 180o
Độ dài của từ W là 10 ký tự
X nhỏ hơn Y
Tuấn có thể tham dự buổi seminar vào thứ 4 sau 14h
…
Trí tuệ nhân tạo
3
Bài toán thỏa mãn ràng buộc
Một bài toán thỏa mãn ràng
buộc (Constraint Satisfaction
Problem – CSP) bao gồm:
Một tập hữu hạn các biến X
Miền giá trị (một tập hữu hạn các
giá trị) cho mỗi biến D
Một tập hữu hạn các ràng buộc C
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
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
Một bài toán thỏa mãn ràng buộc
thường đượ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)
Các biến: WA, NT, Q, NSW,
Các miền giá trị: Di = {red,
green, blue}
kề nhau phải có màu khác
nhau
WA ≠ NT
(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)
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)
Ví dụ: WA=red,
NT=green, Q=red,
NSW=green, V=red,
SA=blue, T=green
Đồ thị các ràng buộc
Đố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
Đồ thị các ràng buộc
(constraint graph)
Các nút biểu diễn các biến
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
Các biến rời rạc
Các miền giá trị hữu hạ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)
Ví dụ: Các bài toán thỏa mãn ràng buộc nhị phân (Boolean CSPs)
Các miền giá trị vô hạn
Miền giá trị các số nguyên, các chuỗi, ...
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 vic
Cần một ngôn ngữ biểu diễn ràng buộc (constraint language), ví dụ:
StartJob1 + 5 ≤ StartJob3
Các biến liên tục
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
Bài toán 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 bằng phương pháp lập trình tuyến tính
Trí tuệ nhân tạo
8
Các kiểu ràng buộc
Ràng buộc đơn (unary constraint) chỉ liên quan đến 1
biến
Ví dụ: SA ≠ green
Ràng buộc nhị phân (binary constraint) liên quan đến 2
biến
Ví dụ: SA ≠ WA
Ràng buộc bậc cao (higher-order constraint) liên quan
đến nhiều hơn 2 biến
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
Các biến: F T U W R O X1 X2 X3 (các nhớ của các phép +)
Miền giá trị: {0,1,2,3,4,5,6,7,8,9}
Các ràng buộc: Giá trị của các biến (F,T,U,W,R,O) khác nhau
O + O = R + 10 * X1
X1 + W + W = U + 10 * X2
X2 + T + T = O + 10 * X3
X3 = F
T ≠ 0
F ≠ 0
Trí tuệ nhân tạo
10
Các bài toán CSP trong thực tế
Các bài toán giao nhiệm vụ
y lp nào?
Các bài toán lập thời khóa (gian) biểu
Ví dụ: Lớp học nào được dạy vào thời gian nào và ở đâu?
Các bài toán lập lịch vận tải (giao hàng) của các
công ty
Các bài toán lập lịch sản xuất của các nhà máy
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
Tìm kiếm bằng kiểm thử (1)
Là phương pháp giải quyết vấn đề tổng quát nhất
Phương pháp giải quyết bằng kiểm thử (Generate and
Test)
Sinh ra một khả năng (candidate) của lời giải
Kiểm tra xem khả năng này có thực sự là một lời giải
Áp dụng phương pháp kiểm thử đối với bài toán CSP
Bước 1. Gán các giá trị cho tất cả các biến
Bước 2. Kiểm tra xem tất cả các ràng buc c thỏ
không
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
12
Tìm kiếm bằng kiểm thử (2)
Điểm yếu nghiêm trọng của phương pháp tìm kiếm bằng
(hiển nhiên) không thỏa mãn các ràng buộc
Ví dụ
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);
Trí tuệ nhân tạo
13
Tìm kiếm bằng kiểm thử (3)
Làm thế nào để cải thiện phương pháp kiểm thử?
Sinh ra các khả năng (các phép gán giá trị) một cách
thông minh hơn
Sử dụng các kết quả (thông tin) thu được từ bước
kiểm tra (bước 2)
Phát hiện sớm (từ trước) các mâu thuẫ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
14
Tìm kiếm quay lui (1)
Tìm kiếm quay lui (backtracking) là giải thuật tìm kiếm
Dựa trên giải thuật tìm kiếm theo chiều sâu (depth-first search)
Mỗi lần gán, chỉ làm việc (gán giá trị) cho một biến
(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)
Phương pháp tìm kiếm quay lui đối với bài toán CSP
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
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
15
Tìm kiếm quay lui (2)
Các yếu tố ảnh hưởng đến phương pháp tìm kiếm quay
lui
Thứ tự được xét của các biến?
toán cụ thể)
Ưu tiên xét trước các biến có ít giá trị (miền giá trị nhỏ)
Ưu tiên xét trước các biến tham gia vào nhiều ràng buộc
Với mỗi biến, thứ tự được xét của các giá trị?
Tha các giá trvi mi bin nh nghĩ
thuộc vào bài toán cụ thể
Trí tuệ nhân tạo
16
Giải thuật tìm kiếm quay lui
Trí tuệ nhân tạo
17
Tìm kiếm quay lui – Ví dụ (1)
Trí tuệ nhân tạo
18
Tìm kiếm quay lui – Ví dụ (2)
Trí tuệ nhân tạo
19
Tìm kiếm quay lui – Ví dụ (3)
Trí tuệ nhân tạo
20
Tải về để xem bản đầy đủ
43 trang
24400
Free
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 đề Tìm kiếm, Thỏa mãn ràng buộc (Phần 3) - Nguyễn Nhật Quang", để 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:
- bai_giang_tri_tue_nhan_tao_bai_5_giai_quyet_van_de_tim_kiem.pdf
