Bộ đề tổng hợp môn Trí tuệ nhân tạo

Chia sẻ: Nguyen Tuyen | Ngày: | Loại File: DOC | Số trang:18

Thêm vào BST

Báo xấu

350
lượt xem 51
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Câu 1.(3đ) Trình bày sự khác nhau giữa thuật toán và thuật giải Heuristics. Hãy nêu 1 ví dụ về thuật giải Heuristics Câu 2.(7đ) a. Trình bày thuật giải Robinson. b. Áp dụng thuật giải Robinson, chứng minh bài toán sau: p  q , (s   q)  (r  s) , p  u  r, u c. Hãy xây dựng cây định danh và tìm luật theo phương pháp vector đặc trưng của Quinlan để xác định một loại quả độc hay không độc theo bảng số liệu sau....

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bộ đề tổng hợp môn Trí tuệ nhân tạo

Bé §Ò Tæng Hîp - M«n TrÝ TuÖ Nh©n T¹o – K2CN4 Đề 1 Câu 1.(3đ) Trình bày sự khác nhau giữa thuật toán và thuật giải Heuristics. Hãy nêu 1 ví d ụ về thuật giải Heuristics Câu 2.(7đ) a. Trình bày thuật giải Robinson. b. Áp dụng thuật giải Robinson, chứng minh bài toán sau: ¬p ∨q , (s ∨¬ q) ∧(r ∨¬s) , p ∧u ⇒ r, u c. Hãy xây dựng cây định danh và tìm luật theo phương pháp vector đặc trưng của Quinlan để xác định một loại quả độc hay không độc theo bảng số liệu sau. Vị Vỏ Độc Tên Màu Ngọt Đỏ Nhẵn A không Đỏ Nhẵn B Cay không C Chua Vàng Có gai Không Độc D Cay Vàng có gai Ngọt E Tím Có gai Không Nhẵn F Chua Vàng Không Ngọt Nhẵn G Tím Không Độc H Cay Tím có gai Đề 2 (có giải) trang 13) Câu 1(3 đ) Trình bày khái niệm hàm heuristics. : Xây dựng hàm đánh giá h cho bài toán ở bảng 1 để giải bài toán TACI sau: 3 2 6 1 2 3 1 5 4 8 4 7 8 7 6 5 Ti TG Bảng 1 Câu 2(7 đ) a. Trình bày thuật giải A*. b. Giải bài toán tìm đường đi ngắn nhất từ A đến B trong đồ thị không gian tr ạng thái ở Hình 1 theo thuật giải A*. (Giá trị cạnh các đỉnh là hàm đánh giá h(T), c ạnh các cung là độ dài cung). 30 A 17 20 12 15 22 2 8 2 25 C 0D F 13 4 E I 12 10 17 Hình 1 9 12 E 10 G 16 16 K 13 14G 11 10 H 5 I H 9 K 18 8 6 N 12 7 B amittkduong@gmail.com - k2cn4.n-stars.org – 4rum K2CN4 1 0
Bé §Ò Tæng Hîp - M«n TrÝ TuÖ Nh©n T¹o – K2CN4 Đề 3 Câu 1 (3đ) a. Trình bày thuật giải Vương Hạo. b. Áp dụng thuật toán Vương hạo, chứng minh bài toán sau: p ∨¬q , (¬s ∨¬q) ∧(r ∨ , ¬p ∧u ⇒ r ∨u s) Câu 2 : (7đ) a. Trình bày thuật giải A KT . b. Dùng thuật toán A KT để giải bài toán TACI sau: LE LEY QUY OU DON QDN Trạng thái ban đầu Trạng thái kết thúc Đề 4 Câu 1: (4đ) Có 6 đội bóng thi đấu vòng tròn (lượt đi). Biết rằng : - Đội A đã đấu với dội B và đội D. - Đội C đã đấu với dội D và đội F - Đội D đã đấu với dội A và đội F. - Đội B đã đấu với dội E và đội F. AB C D E F A AB AC AD AE AF B BC BD BE BF C CD CE CF D DE DF E EF F Mỗi đội chỉ có được thi đấu 1 trận trong 1 tuần. Chỉ có 2 đội thamgia 1 trận đấu. Hãy xếp lịch thi đấu sao cho số tuần diễn ra các trận đấu còn lại là ít nhất ? (Dùng thuật toán tô màu) Câu 2: (6đ) Cho bảng quan sát : Quang cảnh Nhiệt độ STT Gió Picnic Nắng Nhẹ 1 Cao Không Mưa Thấp Mạnh 2 Không Nhẹ Được 3 Râm mát TB Nắng Mạnh 4 TB Không Mưa Mạnh 5 Cao Không Thấp Mạnh Được 6 Râm mát Mưa Nhẹ 7 TB Không Nắng Nhẹ Được 8 TB Mưa Thấp Nhẹ 9 Không amittkduong@gmail.com - k2cn4.n-stars.org – 4rum K2CN4 2
Bé §Ò Tæng Hîp - M«n TrÝ TuÖ Nh©n T¹o – K2CN4 Xác định điều kiện như thế nào để tổ chức Được hay Không buổi picnic ?(Dùng thuật toán Quinlan) Đề 5: BAØI 1:(3 ÑIEÅM) Giaû söû coù 9 cuoäc minting a,b,c,d,e,f,g,h,i ñöôïc toå chöùc. Moãi cuoäc mitting ñöôïc toå chöùc trong moät buoåi. Caùc cuoäc mitting sau khoâng ñöôïc dieãn ra ñoàng thôøi: ae,bc,cd,ed,abd,ahi,bhi,dfi,dhi,fgh. Haõy s öû duïng thuaät toaùn toâ maøu toái öu ñeå boá trí caùc cuoäc mitting vaøo caùc buoåi sao cho soá buoåi dieãn ra laø ít nhaát. BAØI 2: (3 ÑIEÅM) Cho ñoà thò coù ma traän chi phí nhö sau 1 2 3 4 5 6 ∞ 1 2 4 3 6 25 2 0 2 0 ∞ 3 1 1 7 33 19 4 2 6 ∞2 5 25 14 9 3 8 ∞ 31 15 192 2 4 Haõy söû duïng ∞ 1721 45 thuaät giaûi 4 15 GTS2 ñeå tìm 3 1 1 5 20 ∞ 6 haønh trình toát 656 5 nhaát vôùi p = 4 (v1=1, v2=2, v3=4, v4=6. BAØI 3:(4 ÑIEÅM) Söû duïng thuaät toaùn QuinLan ñeå giaûi quyeát baøi toaùn sau: Ñeå xaùc ñònh ngöôøi chaâu AÙ hay ngöôøi chaâu AÂu khi xem xeùt moät nhoùm ngöôøi caên cöù treân hình daùng, chieàu cao vaø giôùi tính theo baûng sau: amittkduong@gmail.com - k2cn4.n-stars.org – 4rum K2CN4 3
Bé §Ò Tæng Hîp - M«n TrÝ TuÖ Nh©n T¹o – K2CN4 Ñaë ñieå cm Daùg n Chieà cao u Giôùtính i Thuoä chaâ c u Ngöôø i 1 To Trung bình Nam Chaâ AÙ u 2 Nhoû Thaáp Nam Chaâ AÙ u 3 Nhoû Trung bình Nam Chaâ AÙ u 4 To Cao Nam Chaâ AÂ uu 5 Nhoû Trung bình Nöõ Chaâ AÂ uu 6 Nhoû Cao Nam Chaâ AÂ uu 7 Nhoû Cao Nöõ Chaâ AÂ uu 8 To Trung bình Nöõ Chaâ AÂ uu amittkduong@gmail.com - k2cn4.n-stars.org – 4rum K2CN4 4
Bé §Ò Tæng Hîp - M«n TrÝ TuÖ Nh©n T¹o – K2CN4 Đề 6 BAØI 1.:(3 ÑIEÅM) Söû duïnghuaät giaûi AKT – Tìm kieám vôùi tri thöùc boå sung (Algorthm for T Knowled geable Tree Search) ñeå giaûi baøi toaùn Taci theo caùc traïng thaùi: 2 8 3 1 6 4 7 5 1 2 4 8 5 7 6 3 Traïng thaùi ñaàu Traïng thaùi ñích BAØI 2.:(3 ÑIEÅM) Haõy söû duïng thuaät giaûi A* ñeå tìm ñöôøng ñi ngaén nhaát töø thaønh phoá A ñeán thaønh phoá B bieát khoaûng caùch öôùc löôïng töø caùc thaønh phoá ñeán thaønh phoá B ñöôïc cho nhö sau: ænh Ñ khoaûng caùch öôùc löôïng Z 374 O 70 A 366 Z 151 T 329 F 75 C 160 S 140 99 A R 193 120 P 98 118 80 B 0 T R B F 178 97 S 253 100 146 110 O 380 P 60 C BAØI 3.:(4 ÑIEÅM) Söû duïng phöông phaùp ñoä ño hoãn loaïn ñeå giaûi baøi toaùn sau: baûng döõ lieäu xaùc ñònh hieäu quaû cuûa vieäc söû Theo duïng kemMaø toù naéngu cao chaùy Chieà Teân uc Caâ naëg Duøg kem nn n Keáquaû t 1. Sarah Vaøg n Trung bình Nheï Khoâg n Chaù naég yn 2. Dana Vaøg n Cao Trung bình Coù Khoâg chaù naég n yn 3. Alex Naâu Luø n Trung bình Coù Khoâg chaù naég n yn 4. Annie Vaøg n Luø n Trung bình Khoâg n Chaù naég yn 5. Emily Ñoû Trung bình Naëg n Khoâg n Chaù naég yn 6. Pete Naâu Cao Naëg n Khoâg n Khoâg chaù naég n yn 7. John Naâu Trung bình Naëg n Khoâg n Khoâg chaù naég n yn 8. Katie Vaøg n Luø n Nheï Coù Khoâg chaù naég n yn amittkduong@gmail.com - k2cn4.n-stars.org – 4rum K2CN4 5
Bé §Ò Tæng Hîp - M«n TrÝ TuÖ Nh©n T¹o – K2CN4 Đề 7 BAØI 1:(3 ÑIEÅM) Söû duïng thuaät toaùn A* cho baøi toaùn thaùp Haø Noäi: Cho 3 coïc A,B,C. ôû coïc A ban ñaàu coù n ñóa saép xeáp theo thöù töï coù kích thöôùc lôùn daàn töø treân xuoáng. Haõy dòch chuyeån n ñóa ñoù sang coïc C sao cho: -Moãi laàn chæ ñöôïc di chuyeån chæ 1 ñóa. -Trong moãi coïc khoâng cho pheùp ñóa coù kích thöôùc lôùn treân ñóa coù kích thöôùc nhoû hôn. BAØI 2: (3 ÑIEÅM) Söû duïng Thuaät toaùn Vöông Haïo giaûi baøi toaùn sau: Ví duï: Chöùng minh raèng: Minh laø sinh vieân cuûa - Minh laø sinh vieân ngaønh coâng ngheä thoâng - Coâng ngheä thoâng tin laø moät ngaønh cuûa - Khoa tin hoïc laø moät boä phaân cuûa ÑHKHTN. BAØI 3:(4 ÑIEÅM) Söû duïng thuaät toaùn QuinLan ñeå giaûi quyeát baøi Quyeát ñònh mua haøng hay khoâng mua theo baûng STT Maøu saéc Hình Quyeát Kích côû daùng ñònh 1 Trung bình Ñoû Caàu Mua 2 Lôùn Vaøng Hoäp Mua 3 Trung bình Xanh Truï Khoâng 4 Nhoû Xanh Caàu Mua 5 Trung bình Xanh Noùn Khoâng 6 Nhoû Xanh Noùn Khoâng 7 Trung bình Ñoû Truï Mua amittkduong@gmail.com - k2cn4.n-stars.org – 4rum K2CN4 6
Bé §Ò Tæng Hîp - M«n TrÝ TuÖ Nh©n T¹o – K2CN4 Đề 8 BAØI 1.:(3 ÑIEÅM) Söû duïng Thuaät giaûi AKT – Tìm kieám vôùi tri thöùc boå sung (Algorthm for Knowled geable Tree Search) ñeå giaûi baøi toaùn Taci theo caùc traïng thaùi: 1 2 3 4 5 6 7 8 1 2 3 5 7 6 4 8 Traïng thaùi ñaàu Traïng thaùi ñích BAØI 2.:(3 ÑIEÅM) Haõy söû duïng thuaät toaùn Robinson chöùng minh baøi (i) {p->q,q->r,r->s,p} Hoûi: p^s? (ii) {a^b->c,b^c->d,a^b} Hoûi d? BAØI 3.:(4 ÑIEÅM) Söû duïng phöông phaùp ñoä ño hoãn loaïn ñeå giaûi baøi Theo baûng döõ lieäu xaùc ñònh hieäu quaû cuûa vieäc söû duïng kem chaùy naéng Teân Maø toù uc Chieà cao Caâ naëg Duøg kem u nn n Keáquaû t 1. Sarah Vaøg n Trung bình Nheï Khoâg n Chaù naég yn 2. Dana Vaøg n Cao Trung bình Coù Khoâg chaù naég n yn 3. Alex Naâu Luø n Trung bình Coù Khoâg chaù naég n yn 4. Annie Vaøg n Luø n Trung bình Khoâg n Chaù naég yn 5. Emily Ñoû Trung bình Naëg n Khoâg n Chaù naég yn 6. Pete Naâu Cao Naëg n Khoâg n Khoâg chaù naég n yn 7. John Naâu Trung bình Naëg n Khoâg n Khoâg chaù naég n yn 8. Katie Vaøg n Luø n Nheï Coù Khoâg chaù naég n yn amittkduong@gmail.com - k2cn4.n-stars.org – 4rum K2CN4 7
Bé §Ò Tæng Hîp - M«n TrÝ TuÖ Nh©n T¹o – K2CN4 ĐỀ 9 BAØI 1:(3 ÑIEÅM) (1) Phaân coâng, lòch coâng taùc, lòch thi ñaáu: - Coù moät cuoäc hoäi thaûo khoa hoïc vôùi 9 chuû ñeà khaùc nhau, moãi chuû ñeà dieãn ra trong moät buoåi. - Caùc chuû ñeà sau khoâng ñöôïc ñoàng thôøi: AE, BC, CD, ED, ABD, AHI, BHI, DFI, DHI, FGH. - Xaây döïng lòch sao cho soá buoåi dieãn ra laø ít nhaát. Gôïi yù: soá maøu = soá buoåi. BAØI 2: (3 ÑIEÅM) Söû duïng Thuaät toaùn Vöông Haïo giaûi baøi toaùn sau: Ví duï: Chöùng minh raèng: Minh laø sinh vieân cuûa - Minh laø sinh vieân ngaønh coâng ngheä thoâng - Coâng ngheä thoâng tin laø moät ngaønh cuûa - Khoa tin hoïc laø moät boä phaân cuûa ÑHKHTN. BAØI 3:(4 ÑIEÅM) Söû duïng thuaät toaùn QuinLan ñeå giaûi quyeát baøi Ñeå xaùc ñònh ngöôøi chaâu AÙ hay ngöôøi chaâu AÂu khi xem xeùt moät nhoùm ngöôøi caên cöù treân hình daùng, chieàu cao vaø giôùi tính theo baûng sau: Ñaë ñieå cm Daùg n Chieà cao u Giôùtính i Thuoä chaâ c u Ngöôø i 1 To Trung bình Nam Chaâ AÙ u 2 Nhoû Thaáp Nam Chaâ AÙ u 3 Nhoû Trung bình Nam Chaâ AÙ u 4 To Cao Nam Chaâ AÂ uu 5 Nhoû Trung bình Nöõ Chaâ AÂ uu 6 Nhoû Cao Nam Chaâ AÂ uu 7 Nhoû Cao Nöõ Chaâ AÂ uu 8 To Trung bình Nöõ Chaâ AÂ uu amittkduong@gmail.com - k2cn4.n-stars.org – 4rum K2CN4 8
Bé §Ò Tæng Hîp - M«n TrÝ TuÖ Nh©n T¹o – K2CN4 BỘ ĐỀ BỔ SUNG ĐỀ 1(có giải trang 9) Câu 1. a. Trình bày sự khác nhau giữa thuật toán và thuật giải Heuristics. b. Áp dụng nguyên lý thứ tự của kỹ thuật heuristics trình bày tư tưởng c ủa bài toán chia N vật có khối lượng khác nhau thành M nhóm đều nhau. Gi ải bài toán chia 8 vật thành 3 nhóm, các vật có trọng lượng như sau: n1 = 28, n2 = 12, n3 = 36, n4 = 16, n5 = 23, n6 = 32, n7= 21, n8 = 15. c. Trình bày tư tưởng và mã giả của thuật giải leo đồi. A 15 C 10 E d. Giải bài toán tìm đường 9 D đi từ điểm A đến điểm B K 14 IE 13 trong đồ thị cho ở hình 1 11 F K I G 12 theo thuật giải leo đồi dốc G đứng. H H8 0 B Hình 1 Câu 2. a. Trình bày thuật giải Robinson. b. Áp dụng thuật giải Robinson, chứng minh tập mệnh đề sau: ¬p ∨q , (s ∨¬ q) ∧(r ∨¬s) , p ∧u ⇒ r, u c. Hãy xây dựng cây định danh và tìm luật theo phương pháp vector đặc trưng của Quinlan để xác định một loại quả độc hay không độc theo bảng số liệu sau. Vị Vỏ Độc Tên Màu Ngọt Đỏ Nhẵn A không Đỏ Nhẵn B Cay không C Chua Vàng Có gai Không Độc D Cay Vàng có gai Ngọt E Tím Có gai Không Nhẵn F Chua Vàng Không Ngọt Nhẵn G Tím Không Độc H Cay Tím có gai amittkduong@gmail.com - k2cn4.n-stars.org – 4rum K2CN4 9
Bé §Ò Tæng Hîp - M«n TrÝ TuÖ Nh©n T¹o – K2CN4 Giải Đề số 1 Câu 1. (3 điểm) a. Sự khác nhau giữa thuật toán và thuật giải Heuristics. (0,5 điểm) Thuật toán là dãy hữu hạn các bước, mỗi bước mô tả chính xác các phép toán hoặc hành động cần thực hiện để giải quyết một vấn đề. Trong thuật toán, mỗi bước phải được mô tả m ột cách chính xác sao cho m ột bước chỉ được hiểu theo một nghĩa nhất định, mỗi bài toán chỉ có m ột thu ật toán duy nhất hoặc không giải được bằng thuật toán. Trong thực tế, nhiều bài toán có thể giải bằng những cách giải chấp nhận đ ược nhưng không đáp ứng đầy đủ các tiêu chuẩn c ủa thuật toán, các cách gi ải này g ọi là thuật giải. Thuật giải được đề cập đến nhiều trong khoa học trí tuệ nhân tạo là thuật giải heuristics, đó là các quy tắc thô, phương pháp, chi ến lược hay m ẹo rút ra t ừ kinh nghiệm để giải quyết một vấn đề. Giải bài toán bằng thuật gi ải heuristics d ễ dàng đưa ra lời giải nhưng có thể không phải là lời giải tối ưu. b. Chia N vật có khối lượng khác nhau thành M nhóm có khối lượng đ ều nhau bằng nguyên lý thứ tự. (1,0 điểm) * Tư tưởng: ( 0,25điểm) 1. Sắp xếp N vật theo thứ tự có khối lượng giảm dần; 2. Lặp lại cho đến khi không còn vật nào 2.1. Chọn nhóm Mi có khối lượng các vật là nhỏ nhất 2.2. Đặt vật Nj có khối lượng lớn nhất vào nhóm Mi. 2.3. Tính lại khối lượng của các nhóm. * Áp dụng: (0,75 điểm) 1. Sắp xếp các vật theo thứ tự trọng lượng giảm dần. n3=36, n6 = 32, n1 = 28, n5 =23, n7=21, n4=16, n8=15, n2=12. 2. Chọn Lần lặp 1: - Chọn nhóm M1, đặt n3 vào nhóm M1 - Tính khối lượng của các nhóm: M1:36, M2:0, M3:0. Lần lặp 2: - Chọn nhóm M2, đặt n6 vào nhóm M2 - Tính khối lượng của các nhóm: M1:36, M2:32, M3:0. Lần lặp 3: - Chọn nhóm M3, đặt n1 vào nhóm M3 - Tính khối lượng của các nhóm: M1:36, M2:32, M3:28. Lần lặp 4: - Chọn nhóm M3, đặt n5 vào nhóm M3 - Tính khối lượng của các nhóm: M1:36, M2:32, M3:51. Tiếp tục lặp cho đến hết các vật ta được kết quả: Nhóm M1 gồm các vật n3, n4, n2 có khối lượng: 64 Nhóm M2 gồm các vật n6, n7 có khối lượng: 53 Nhóm M3 gồm các vật n1, n5, n8 có khối lượng: 66 amittkduong@gmail.com - k2cn4.n-stars.org – 4rum K2CN4 10
Bé §Ò Tæng Hîp - M«n TrÝ TuÖ Nh©n T¹o – K2CN4 c. Tư tưởng, mã giả thuật giải leo đồi (1,0): * Tư tưởng (0,5 điểm): 1. Nếu trạng thái đầu cũng là trạng thái kết thúc thì thoát, thông báo tìm đ ược l ời giải. Ngược lại đặt trạng thái hiện hành (Ti) là trạng thái khởi đầu. 2. Lặp lại cho đến khi đạt đến trạng thái kết thúc ho ặc cho đến khi không còn một trạng thái tiếp theo hợp lệ (Tk) của trạng thái hiện hành: 2.1. Đặt Tk là trạng thái tiếp theo hợp lệ của trạng thái hiện hành Ti. 2.2. Đánh giá trạng thái Tk mới: 2.2.1. Nếu Tk là trạng thái kết thúc thì trả về trạng thái này và thoát. 2.2.2. Nếu Tk không phải là trạng thái kết thúc nhưng tốt hơn trạng thái hi ện hành thì cập nhật Tk thành trạng thái hiện hành. 2.2.3. Nếu Tk không tốt hơn trạng thái hiện hành thì tiếp tục vòng lặp. * Mã giả (0,5 điểm): Ti:= T0 ; stop:=false; While stop = false do Begin If Ti≡ TG then Begin ; stop:=true; End else Begin Better:=false; While (Better=false) And (stop=false) do Begin If then Begin ; stop:=true; End else Begin Tk:=; If then Begin Ti :=Tk ; Better:=true; End; End; End; {while} End;{else} End; A d. Tìm đường đi từ điểm A đến điểm B theo thuật giải leo đồi dốc đứng (0,5). Bước 1: Đặt trạng thái hiện hành là trạng 15 C E 10 thái A, phát triển các trạng thái hợp lệ c ủa A, 9D I là C, D, E. Trong các trạng thái trên D là E trạng thái tốt nhất, chọn D để phát triển tiếp. K 13 F 11 Bước 2. Phát triển D được các trạng thái F, I. GI Trong 2 trạng thái trên, I là trạng thái tốt hơn, H chọn I để phát triển tiếp, Bước 3> Chọn I để phát tiển được B, G. 0B G 12 Trong 2 trạng thái hợp lệ của I, B là trạng thái tốt hơn, đồng thời B là tạng thái đích nên thuật giải kết thúc. Cây tìm kiếm như hình bên. amittkduong@gmail.com - k2cn4.n-stars.org – 4rum K2CN4 11
Bé §Ò Tæng Hîp - M«n TrÝ TuÖ Nh©n T¹o – K2CN4 Câu 2 (2,0 điểm) a. Phát biểu thuật giải Robinson. (0,5 điểm) Thuật giải Robinson hành động dựa trên phương pháp chứng minh bằng ph ản chứng. b1: Đưa vấn đề về dạng chuẩn và phát biểu giải thiết và kết luận của vấn đ ề dưới dạng sau: GT1, GT2, ...,GTn ⇒ KL1, KL2,...,KLm Trong đó các GTi và KLj được xây dựng từ các biến mệnh đề và các phép logic: ∧∨ ¬. ,, b2: Nếu GTi có phép ∧thì thay bằng dấu",". Nếu KLj có phép ∨thì thay bằng dấu ",". b3: Biến đổi dạng chuẩn ở b1 về dạng sau: GT1, GT2, ...,GTn ,¬ KL1, ¬KL2,..., ¬KLm b4: Nếu trong danh sách mệnh đề ở b3 có mệnh đề đối ngẫu thì m ệnh đề được chứng minh. Ngược lại thì chuyển sang b5. b5: Xây dựng một mệnh đề mới bằng cách tuyển m ột c ặp m ệnh đ ề trong danh sách mệnh đề. Nếu mệnh đề mới có các biến mệnh đề đối ngẫu thì lo ại b ỏ các bi ến đó. b6. Thay thế hai mệnh đề vừa tuyển trong danh sách m ệnh đề b ằng m ệnh đ ề mới. b7. Nếu không xây dựng được thêm một mệnh đề m ới nào và trong danh sách mệnh đề không có hai mệnh đề nào đối ngẫu nhau thì vấn đề không đ ược ch ứng minh. Nếu danh sách mệnh đề không còn m ệnh đề nào (danh sách r ỗng: Φ), vấn đề được chứng minh. b. Áp dụng thuật giải, chứng minh tập mệnh đề sau: (0,5 điểm) ¬p ∨q , (s ∨¬ q) ∧(r ∨¬s) , p ∧u ⇒ r, u ¬p ∨q , s ∨¬ q, r ∨¬s , p , u ⇒ r, u ¬p ∨q , s ∨¬ q, r ∨¬s , p , u, ¬r,¬ u (¬p ∨q , s ∨¬ q), r ∨¬s , p , u, ¬r,¬ u (¬p ∨s, r ∨¬s) , p , u, ¬r,¬ u (¬p ∨r , p) , u, ¬r,¬ u (r ∨¬r), u, ¬ u u, ¬ u = Φ Danh sách mệnh đề trở thành danh sách rỗng, vấn đề được chứmg minh. c. Tính vector đặc trưng cho các thuộc tính dẫn xuất (1 điểm): Thuộc tính mục tiêu của bài toán là quả có độc ta chọn thuộc tính dẫn xuất để phân hoạch: - Thuộc tính vị: VVị(Ngọt) = (T(ngọt, độc), T(ngọt, không độc)) = (0/3, 3/3). VVị(Cay) = (T(cay, độc), T(cay, không độc)) = (2/3, 1/3). VVị(Chua) = (T(Chua, độc), T(Chua, không độc)) = (0/2, 2/2). - Thuộc tính màu: VMàu(đỏ) = (T(đỏ, độc), T(đỏ, không độc)) = (0/2, 2/2). VMàu(vàng) = (T(vàng, độc), T(vàng, không độc)) = (1/3, 2/3). amittkduong@gmail.com - k2cn4.n-stars.org – 4rum K2CN4 12
Bé §Ò Tæng Hîp - M«n TrÝ TuÖ Nh©n T¹o – K2CN4 VMàu(tím) = (T(tím, độc), T(tím, không độc)) = (2/3, 1/3). - Thuộc tính vỏ: VVỏ(nhẵn)=(T(nhẵn, độc), T(nhẵn, không độc)) = (0/4, 4/4). VVỏ(gai)=(T(gai, độc), T(gai, không độc)) = (3/4, 1/4). Các thuộc tính vỏ, thuộc tính màu có 1 vector đơn vị, thuộc tính vị có 2 vector đơn vị vậy ta chọn thuộc tính vị là thộc tính phân hoạch, quả gạch chân là quả có độc (hình a). vị Ngọt Chua Hình 1 cay B, D, H C, F A, E, G Còn lại tập PCay còn lẫn lộn quả độc và không độc, tiếp tục phân hoạch thành các tập con theo hai thuộc tính màu và vỏ: - Thuộc tính màu: VMàu(đỏ) = (T(đỏ, độc), T(đỏ, không độc)) = (0/1, 1/1). VMàu(vàng) = (T(vàng, độc), T(vàng, không độc)) = (1/1, 0/1). VMàu(tím) = (T(tím, độc), T(tím, không độc)) = (1/1, 0/1). - Thuộc tính vỏ: VVỏ(Có gai)=(T(Có gai, độc), T(Có gai , không độc)=(2/2, 0/2) VVỏ(Nhẵn)=(T(Nhẵn, độc), T(nhẵn , không độc)=(0/1, 1/1) Thuộc tính vỏ có 2 vector đơn vị, vậy ta chon thuộc tính này làm vector phân hoạch tiếp được cây định danh như (hình b). Từ cây đinh danh ta có thể suy ra hệ luật như sau: 1. Quả có vị ngọt và quả có vị chua không độc; 2. Quả có vị cay vỏ nhẵn không độc; 3. Quả có vị cay và có gai độc. vị Ngọt Chua cay C, F A, E, G Hình 2 vỏ Nhẵn Có gai B D, H amittkduong@gmail.com - k2cn4.n-stars.org – 4rum K2CN4 13
Bé §Ò Tæng Hîp - M«n TrÝ TuÖ Nh©n T¹o – K2CN4 Giải Đề số 2(trang 2) Câu 1. (3 điểm) a. Trình bày khái niệm hàm heuristics. Xây dựng hàm đánh giá cho bài toán Ta canh (bài toán 8 số). (1 điểm) Hàm heuristics (kí hiệu h) là một ước lượng về khả năng dẫn đến lời gi ải của bài toán. Với mỗi tạng thái T i bất kỳ trong không gian trạng thái, xác định một giái trị h(Ti) là số đo sự đánh giá về trạng thái T i, hay chi phí để đi từ trạng thái T 0 đến trạng thái đích TG. Hàm h(Ti) là hàm thực dương, trong quá trình tìm kiếm giá trị hàm h(T i) sẽ giảm dần. Tại trạng thái đích h(TG) = 0. Trong bài toán Tacanh (8 số) có 2 cách xây dựng hàm đánh gía h(Ti). 3 2 6 1 2 3 1 5 4 8 4 7 8 7 6 5 Ti TG Hàm h1: với mỗi trạng thái Ti, h(Ti) là số quân không nằm đúng vị trí của nó trong trạng thái đích. h1(Ti) = 5. Hàm h2: tính theo tổng các dịch chuyển của các quân nằm sai vị trí v ề v ị trí c ủa nó trong trạng thái đích. h2(Ti)= 1 + 0 + 2 + 0 + 5 + 3 + 0 + 2 = 13. b. Trình bày thuật giải A* (1 điểm). 1. Đặt OPEN chỉ chứa T0 ; Đặt g(T0)=0; h(T0)=0; f(T0)=0; đặt CLOSE là tập rỗng. 2. Lặp lại các bước sau cho đến khi gặp điều kiện đúng. 2.1. Nếu OPEN rỗng, bài toán vô nghiệm: thoát. 2.2. Ngược lại chọn Tmax trong OPEN sao cho f(Tmax) là nhỏ nhất. 2.2.1. Lấy Tmax ra khỏi OPEN và đưa Tmax vào CLOSE. 2.2.2. Nếu Tmax là TG thì thoát, thông báo lời giải là Tmax 2.2.3. Nếu Tmax không phải TG, tạo danh sách tất cả các trạng thái kế tiếp của Tmax. Gọi một trạng thái này là Tk. vơi mỗi Tk thực hiện các bước sau: 2.2.3.1. Tính g(Tk)=g(Tmax) + cost(Tmax, Tk). 2.2.3.2. Nếu tồn tại Tk' trong OPEN trùng Tk Nếu g(Tk)
Bé §Ò Tæng Hîp - M«n TrÝ TuÖ Nh©n T¹o – K2CN4 Lan truyền sự thay đổi giá trị g, f cho tất cả các trạng thái kế ti ếp c ủa T i (ở tất cả các cấp) đã được lưu trữ trong CLOSE và OPEN. 2.3.3.4. Nếu Tk chưa xuất hiện trong cả OPEN và CLOSE thì Thêm Tk vào OPEN Tính: f(Tk) = g(Tk) + h(Tk). c. Tìm đường đi từ A đến B theo thuật giải A* (1 điểm) B1: OPEN ={(A, g=0, h=0, f=0)} CLOSE ={} lấy A ra khỏi OPEN đặt vào CLOSE OPEN ={} CLOSE ={(A, g=0, h=0, f=0)} Phát triển A, được các đỉnh C, D, E, F. Đặt 4 đỉnh vào OPEN, tính gía trị hàm f: f(C) = 42; f(D) =32; f(E) = 39; f(F) = 42; OPEN = {(D, 12, 20, 32 ), (E, 15, 24, 39), (C, 17, 25, 42), (F, 20, 22, 42)) B2: Chọn D tốt nhất trong OPEN đặt vào CLOSE và loại D khỏi OPEN OPEN = {(E, 15, 24, 39), (C, 17, 25, 42), (F, 20, 22, 42)) CLOSE = {(A, g=0, h=0, f=0), (D, 12, 20, 32 ) cha(D)= A} Phát triển D được các đỉnh H, E đặt vào OPEN, tính f. Vì E có g(E)=20 >g(E) ∈OPEN nên ta không cập nhật lại đỉnh E trong OPEN OPEN = {(E, 15, 24, 39), (C, 17, 25, 42), (F, 20, 22, 42), (H, 22, 16, 38)} B3: H là đỉnh tốt nhất trong OPEN, H không có trong CLOSE, đ ặt H vào CLOSE và loại H khỏi OPEN. OPEN = {(E, 15, 24, 39), (C, 17, 25, 42), (F, 20, 22, 42)} CLOSE = {(A, g=0, h=0, f=0), (D, 12, 20, 32 ), (H, 22, 16, 38) cha(H) = D } Phát triển H được các đỉnh K, B đặt vào OPEN, tính f: OPEN = {(E, 15, 24, 39), (C, 17, 25, 42), (F, 20, 22, 42), (E, 20, 24, 44), (K, 33, 14,47), (B,31,0, 31)} B4: Trong OPEN B là đỉnh tốt nhất, nên đặt B vào CLOSE, loại B khỏi OPEN. OPEN = {(E, 15, 24, 39), (C, 17, 25, 42), (F, 20, 22, 42), (E, 20, 24, 44), (K, 33, 14,47)} CLOSE = {(A, g=0, h=0, f=0), (D, 12, 20, 32 ), (H, 22, 16, 38), (B,31,0, 31) cha(B) =H} Vậy đường đi ngắn nhất từ A đến B tìm được là A→ D→H→B với g(B) = 31. Cây tìm kiếm có dạng như sau: A 42 32 39 42 D F C E E K 38 H 44 E G H 31 B K 14 amittkduong@gmail.com - k2cn4.n-stars.org – 4rum K2CN4 15
Bé §Ò Tæng Hîp - M«n TrÝ TuÖ Nh©n T¹o – K2CN4 Câu 2. (2điểm) a. Thuật giải Vương Hạo (0,5 điểm). b1: Phát biểu lại giả thiết và kết luận của vấn đề theo dạng chuẩn sau: GT1, GT2, ...,GTn ⇒ KL1, KL2,...,KLm Trong đó các GTi và KLj được xây dựng từ các biến mệnh đề và các phép logic: ∧∨ ¬. ,, b2: Chuyển vế các GTi và KLj là các mệnh đề có dạng phủ định. b3: Nếu GTi có phép ∧thì thay bằng dấu",". Nếu KL j có dấu ∨thì thay bằng dấu ",". b4: Nếu GTi có phép ∨thì tách thành 2 dòng con. Nếu KL j có phép ∧thì tách thành 2 dòng con. b5: Một dòng được chứng minh nếu tồn tại chung một mệnh đề ở cả hai phía. b6a: Nếu một dòng không còn phép nối ∧ hoặc phép hoặc ∨ ở cả hai vế và ở cả hai vế không có chung một biến mệnh đề, thì dòng đó không được chứng minh. b6b: một vấn đề được chứng minh nếu tất cả các dòng dẫn xuất từ dạng chuẩn ban đầu đều được chứng minh. b. Chứng minh tập mệnh đề: (0,5 điểm) p ∨¬q , (¬s ∨ ∧(r ∨ , ¬p ∧u ⇒ r ∨u q) s) ⇔ p ∨¬q , ¬s ∨q, r ∨ , ¬p , u ⇒ r, u s ⇔ p ∨¬q , ¬s ∨q, r ∨ , u ⇒ r , u, p s ⇔ p ∨¬q , ¬s ∨q, r ∨ , u ⇒ r , u, p s Tách phép ∨ (p ∨¬q) thành 2 dòng con : 1: p, ¬s ∨q, r ∨ , u ⇒ r , u, p (đcm vì có mệnh đề p ở hai phía) s 2:¬q , ¬s ∨q, r ∨ , u ⇒ r , u, p ⇔ ¬s ∨q, r ∨ , u ⇒ r , u, p, q s s Tách phép ∨: ¬s ∨q thành 2 dòng con 2.1: q, r ∨ , u ⇒ r , u, p, q (đcm vì có mệnh đề q ở hai phía) s 2.2: ¬s , r ∨ , u ⇒ r , u, p, q ⇔ r ∨ , u ⇒ r , u, p, q, s s s Tách phép ∨ r ∨s thành 2 dòng con : 2.2.1: s , u ⇒ r , u, p, q, s (đcm vì có s, u ở cả hai phía) 2.2.2: r , u ⇒ r , u, p, q, s (đcm vì có r, u ở cả hai phía) Các dòng dẫn xuất từ dạng chuẩn ban đầu đều được chứng minh , v ậy v ấn đ ề được chứng minh. c. Phương pháp phân hoạch theo Quinlan để xây dựng cây định danh (0,5 điểm). Quinlan chọn thuộc tính phân hoạch bằng cách xây dựng các vector đặc tr ưng cho mỗi giá trị của từng thuộc tính dẫn xuất và thuộc tính mục tiêu. Cách tính như sau: Với mỗi thuộc tính dẫn xuất A còn có thể sử dụng để phân hoạch, tính: VA(j) = (T(j,r1), T(j,r2),..., T(j,rn)) Trong đó: (tổng số phần tử trong phân hoạch có giá trị thuộc tính dẫn xuất A là j và có giá trị thuộc tính mục tiêu là ri) T(j,ri)= (tổng số phần tử trong phân hoạch có giá trị thuộc tính dẫn xuất A là r1, r2, rn là các giá trị của thuộc tính mục tiêu. j) ∑ T(j, ri ) = 1 j amittkduong@gmail.com - k2cn4.n-stars.org – 4rum K2CN4 16
Bé §Ò Tæng Hîp - M«n TrÝ TuÖ Nh©n T¹o – K2CN4 Một véc tơ VA(j) được gọi là vector đơn vị nếu nó chỉ có duy nhất m ột thành phần có giá trị 1 và các thành phần khác có giá trị 0. Thuộc tính được chọn để phân hoạch là thuộc tính có nhiều vector đơn vị nhất. Sau khi phân hoạch xong, ta xây dựng cây định danh. Căn c ứ vào cây đ ịnh danh, phát sinh và ối ưu tập luật. amittkduong@gmail.com - k2cn4.n-stars.org – 4rum K2CN4 17
Bé §Ò Tæng Hîp - M«n TrÝ TuÖ Nh©n T¹o – K2CN4 Luật Morgan Phủ định của phủ ¬ (¬P) ≡ P định (P⇒Q) ≡ (¬P ∨Q) Tương phản (P⇒Q) ≡ (¬ P⇒ ¬ Q) ¬(P ∨Q) ≡ (¬P ∧¬Q) De Morgan ¬ (P ∧Q) ≡ (¬P ∨¬ Q) (P ∧Q) ≡ (Q ∧P) Giao hoán (P ∨Q) ≡ (Q ∨P) Kết hợp (P ∧Q) ∧R ≡ (P ∧ ∧R)) (Q (P ∨Q) ∨R ≡ (P ∨ ∨R)) (Q Phân phối P ∨ Q ∧R) ≡ (P ∨Q) ∧ ∨R) ( (P P ∧ Q ∨R) ≡ (P ∧Q) ∨ ∧R) ( (P P ∨P ≡ P P ∧P ≡ P P ∨¬P ≡ 1 P ∧¬P ≡ 0 ≡ ¬ ∧∨⇒ amittkduong@gmail.com - k2cn4.n-stars.org – 4rum K2CN4 18