Bài tập Biểu diễn vấn đề trong không gian trạng thái, các chiến lược tìm kiếm

Ôn thi Trí tuệ nhân tạo – Đại học CNTT & TT – Collected by Diamond Gate Email: ductrong90ictu@gmail.com – Website: www.BeautifulLife.cwahi.net 1 Chú thích: Các bài tập ở đây do cô Hương gửi PHẦN 1. BIỂU DIỄN VẤN ĐỀ TRONG KHÔNG GIAN TRẠNG THÁI. CÁC CHIẾN LƯỢC TÌM KIẾM Bài 1. Các chiến lược tìm kiếm (Tư tưởng thuật toán, điểm dừng của thuật toán, độ phức tạp của thuật toán, hàm đánh giá) Bài 2. Quy trình giải một bài toán bằng tìm kiếm: Tìm kiếm mù, tìm kiếm kinh nghiệm, tìm kiếm nghiệm tối ưu. Bài 3. Hãy áp dụng chiến lược tìm kiếm theo chiều sâu và theo chiều rộng cho các đồ thị không gian trạng thái sau (Trình bày từng bước, vẽ cây tìm kiếm) Bài 4. Cho đồ thị E H C F B I A D G J K Ôn thi Trí tuệ nhân tạo – Đại học CNTT & TT – Collected by Diamond Gate Email: ductrong90ictu@gmail.com – Website: www.BeautifulLife.cwahi.net 2 u0=A T={J} + Áp dụng thuật toán leo đồi với đồ thị trên (trình bày từng bước; vẽ cây tìm kiếm). + Áp dụng thuật toán tốt nhất-đầu tiên với đồ thị trên (trình bày từng bước; vẽ cây tìm kiếm). Bài 5. Cho đồ thị sau: A B N D H I E F G J K 12 3 2 3 81 472 0 6 M 2 A B C D H I E F G J KN M Ôn thi Trí tuệ nhân tạo – Đại học CNTT & TT – Collected by Diamond Gate Email: ductrong90ictu@gmail.com – Website: www.BeautifulLife.cwahi.net 3 u0 = A. T = {I, N, K} + Áp dụng thuật toán tìm kiếm theo chiều rộng với đồ thị trên (trình bày từng bước; vẽ cây tìm kiếm). + Áp dụng thuật toán tìm kiếm theo độ sâu với đồ thị trên (trình bày từng bước; vẽ cây tìm kiếm). + Áp dụng thuật toán tìm kiếm theo độ sâu lặp (d=2) với đồ thị trên (trình bày từng bước; vẽ cây tìm kiếm). Bài 6. Cho đồ thị Ôn thi Trí tuệ nhân tạo – Đại học CNTT & TT – Collected by Diamond Gate Email: ductrong90ictu@gmail.com – Website: www.BeautifulLife.cwahi.net 4 u0=A T={E,K} + Áp dụng thuật toán A* với đồ thị trên (trình bày từng bước; vẽ cây tìm kiếm). + Áp dụng thuật toán nhánh cận với đồ thị trên (trình bày từng bước; vẽ cây tìm kiếm). PHẦN 2. TRI THỨC VÀ LẬP LUẬN Bài 1. - Cú pháp và ngữ nghĩa của các ngôn ngữ biểu diễn tri thức: lôgic mệnh đề, lôgic vị từ cấp một - Các công thức tương đương trong lôgic mệnh đề, lôgic vị từ cấp một - Các luật suy diễn. Chứng minh bằng luật suy diễn A B N D H J E F G K 12 3 2 3 81 42 0 12 2 3 2 12 3 3 62 0 Ôn thi Trí tuệ nhân tạo – Đại học CNTT & TT – Collected by Diamond Gate Email: ductrong90ictu@gmail.com – Website: www.BeautifulLife.cwahi.net 5 - Luật phân giải, chứng minh bác bỏ bằng luật phân giải - Các thủ tục: thủ tục chứng minh bác bỏ bằng luật phân giải, thủ tục hợp nhất, thủ tục chuẩn hóa Bài 2. Hãy chuẩn hóa các công thức sau: 1.((AB)(CD))E 2.((AE)(GH))(BD) 3. ((EF)(GH))(AB) 4. ((CD)(EH))(AF) 5. (F(DH))((AS) 6. ((AB)C)(DE) 7. ((AB)C)(DE) 8. ((AB)C)D 9. (AB)((CD)E) 10. (AB)((CD)E) Bài 3. Ôn thi Trí tuệ nhân tạo – Đại học CNTT & TT – Collected by Diamond Gate Email: ductrong90ictu@gmail.com – Website: www.BeautifulLife.cwahi.net 6 Chứng minh AB B(CD) CE E D Chứng minh A là hệ quả lôgic (AB)(GH) A(CD) (BH)E CE Chứng minh G là hệ quả lôgic (AH)(ED) G(AB) BH EG Chứng minh D là hệ quả lôgic ((AB)(EH))(FG) AE BD EDG Chứng minh F là hệ quả lôgic (AG)(HE) AB BD DH Chứng minh E là hệ quả lôgic (AE)(GH) GF (HB)D FD Chứng minh A là hệ quả lôgic (AB)(CD) CE D F Chứng minh (AB) là hệ quả lôgic Ôn thi Trí tuệ nhân tạo – Đại học CNTT & TT – Collected by Diamond Gate Email: ductrong90ictu@gmail.com – Website: www.BeautifulLife.cwahi.net 7 Bài 4. Hãy chuẩn hóa các công thức sau: 1. x(yR(x,y)E(x))yQ(y) 2. x((yP(x,y)R(x)) (yQ(y) S(x)) 3. y(xR(x,y) P(y))  (zQ(z,y)A(y)) 4. x(yQ(x,y)R(x)) y(xP(y,x)S(y) 5. (xR(x) yQ(y)) (yxP(x,y)zS(z)) 6. (xP(x)xQ(x))(xyR(x,y)xA(x)) 7. x(yP(x,y)yQ(x,y))xR(x) 8. xy(zP(x,y,z)Q(x,y))xR(x) 9. xy((zP(x,y,z)Q(x,y))xR(x) 10. (xP(x)xyQ(x,y))(xR(x)xA(x)) AB (CD)A (BE)F D C Chứng minh F là hệ quả lôgic (AB)C CD D B Chứng minh A là hệ quả lôgic A(BC) BD C D Chứng minh A là hệ quả lôgic Ôn thi Trí tuệ nhân tạo – Đại học CNTT & TT – Collected by Diamond Gate Email: ductrong90ictu@gmail.com – Website: www.BeautifulLife.cwahi.net 8 Bài 5. P(x,y)vR(x)vH(y) R(a)vS(x) H(b)vP(a,b) Chứng minh S(a) là hệ quả lôgic R(a,y)vQ(x)vP(x,z) R(a,b)vS(x) Q(c)vP(c,a) Chứng minh S(a) là hệ quả lôgic Q(x,y)vH(y)vR(x) R(a)vP(x,y) H(c)vQ(a,c) Chứng minh P(a,c)là hệ quả lôgic P(x,y)R(x) A(x)P(x,y) A(a) Chứng minh R(a) là hệ quả lôgic (Q(x,y)P(x))R(x,y) Q(a,c)S(x) P(x)R(x,y) Ôn thi Trí tuệ nhân tạo – Đại học CNTT & TT – Collected by Diamond Gate Email: ductrong90ictu@gmail.com – Website: www.BeautifulLife.cwahi.net 9 P(x)Q(x,y)vR(y) P(a)vH(a,b) H(x,y) R(b) Chứng minh Q(a,b) là hệ quả lôgic P(x)Q(f(x),y) P(a) Q(f(a),b)R(y) P(x)Q(x,y) P(x)R(x) Q(a,b) Chứng minh R(b) là hệ quả lôgic Chứng minh R(a) là hệ quả lôgic Bài 6. Cho cơ sở tri thức gồm các câu đúng sau đây: - Cầu thủ nào có thể lực tốt và nhanh nhẹn đều đá hay. - Cầu thủ nào siêng tập luyện hoặc có thể hình tốt thì có thể lực tốt. Chứng minh S(a) là hệ quả lôgic P(x,y,z)Q(y,z) Q(a,b)vR(b,c) R(z,x) Chứng minh P(c,a,b) là hệ quả lôgic P(x)Q(x,y) R(a) Q(f(a),b)R(a) Chứng minh P(b) là hệ quả lôgic Ôn thi Trí tuệ nhân tạo – Đại học CNTT & TT – Collected by Diamond Gate Email: ductrong90ictu@gmail.com – Website: www.BeautifulLife.cwahi.net 10 - Cầu thủ nào siêng tập luyện thì nhanh nhẹn - Công Vinh không có thể hình tốt nhưng siêng luyện tập 1/ Hãy biểu diễn tri thức trên bằng lôgic vị từ cấp 1 2/ Hãy chứng minh bằng phương pháp chứng minh bằng luật phân giải để chỉ ra rằng “Công Vinh đá bóng hay” Bài 7. 1/ Biểu diễn các câu sau bằng lôgic vị từ cấp 1. - Sinh viên nào giỏi tiếng Anh và giỏi toán đều giỏi lập trình. - Sinh viên nào thông minh hoặc kiên trì đều giỏi tiếng Anh - Sinh viên nào thông minh thì giỏi toán - Lan thông minh nhưng không kiên trì 2/ Hãy dùng luật phân giải để trả lời cho câu hỏi Lan có giỏi lập trình hay không? Bài 8. Cho CSTT sau: - Người nào thường chơi thể thao thì có sức khỏe tốt. - Người nào có sức khỏe tốt hoặc thông minh thì có nhiều sáng kiến. Ôn thi Trí tuệ nhân tạo – Đại học CNTT & TT – Collected by Diamond Gate Email: ductrong90ictu@gmail.com – Website: www.BeautifulLife.cwahi.net 11 - Người nào có nhiều sáng kiến thì trình độ chuyên môn tốt. Cho tập sự kiện - Ông An thông minh - Ông An không chơi thể thao. Hãy thực hiện suy diễn tiến với CSTT trên. Bài 9. Hãy tự đưa ra một CSTT gồm tối thiểu 5 câu và 2 sự kiện đầu vào hãy tiến hành lập luận tiến và lập luận lùi trên CSTT đó