Bài giảng Nhập môn trí tuệ nhân tạo - Từ Minh Phương

Nội dung text: Bài giảng Nhập môn trí tuệ nhân tạo - Từ Minh Phương

1. HỌC VI ỆN CÔNG NGH Ệ B ƯU CHÍNH VI ỄN THÔNG TỪ MINH PH ƯƠ NG BÀI GI ẢNG Nh ập môn trí tu ệ nhân t ạo Hà n ội 2010 1
2. LỜI NÓI ĐẦ U Trí tu ệ nhân t ạo là m ột nhánh c ủa khoa h ọc máy tính v ới m ục tiêu nghiên c ứu xây d ựng và ứng d ụng các h ệ th ống thông minh nhân t ạo. Đây là m ột trong nh ững l ĩnh v ực được quan tâm nghiên c ứu nhi ều nh ất c ủa khoa h ọc máy tính hi ện nay v ới nhi ều k ết qu ả được ứng d ụng rộng rãi. Môn h ọc Nh ập môn trí tu ệ nhân t ạo là môn h ọc mang tính chuyên ngành trong ch ươ ng trình đào t ạo công ngh ệ thông tin h ệ đạ i h ọc. Mục tiêu c ủa môn h ọc nh ằm giúp sinh viên làm quen v ới khái ni ệm trí tu ệ nhân t ạo thông qua vi ệc gi ới thi ệu m ột s ố k ỹ thu ật và ứng d ụng c ụ th ể. Với vi ệc h ọc v ề trí tu ệ nhân t ạo, m ột m ặt, sinh viên s ẽ được làm quen v ới nh ững ph ươ ng pháp, cách gi ải quy ết v ấn đề không thu ộc l ĩnh v ực toán r ời r ạc ho ặc gi ải thu ật truy ền th ống, ch ẳng h ạn các ph ươ ng pháp d ựa trên heuristics, các ph ươ ng pháp d ựa trên tri th ức, d ữ li ệu. Mặt khác, sinh viên s ẽ được làm quen v ới kh ả n ăng ứng d ụng ti ềm tàng các k ỹ thu ật trí tu ệ nhân t ạo trong nhi ều bài toán th ực t ế. Do trí tu ệ nhân t ạo hi ện đã phát tri ển thành m ột l ĩnh v ực r ộng v ới khá nhi ều l ĩnh v ực chuyên sâu, vi ệc l ựa ch ọn các n ội dung để gi ới thi ệu cho sinh viên là v ấn đề không đơ n gi ản. Trong tài li ệu này, các n ội dung được l ựa ch ọn ho ặc là nh ững n ội dung có tính tiêu bi ểu, kinh điển c ủa trí tu ệ nhân t ạo nh ư n ội dung v ề bi ểu di ễn tri th ức b ằng logic, các ph ươ ng pháp tìm ki ếm, ho ặc là nh ững n ội dung có tính ứng d ụng và đang có tính th ời s ự hi ện nay, tiêu bi ểu là ph ươ ng pháp suy di ễn xác su ất và các k ỹ thu ật h ọc máy. Do khuôn kh ổ có h ạn c ủa tài li ệu v ới tính ch ất là bài gi ảng, ph ần gi ới thi ệu v ề vi ệc s ử dụng k ỹ thu ật trí tu ệ nhân t ạo trong ứng d ụng c ụ th ể không được trình bày nhi ều. Chúng tôi dành ph ần l ựa ch ọn ứng d ụng c ụ th ể cho gi ảng viên trong quá trình lên l ớp và h ướng d ẫn sinh viên. Tùy điều ki ện, gi ảng viên có th ể l ựa ch ọn trong danh m ục ứng d ụng r ất phong phú để gi ới thi ệu và minh h ọa cho các n ội dung c ủa tài li ệu. Nội dung tài li ệu được trình bày thành n ăm ch ươ ng. Ch ươ ng 1 là ph ần gi ới thi ệu t ổng quan v ề trí tu ệ nhân t ạo bao g ồm khái ni ệm, l ịch s ử hình thành, s ơ l ược v ề nh ững k ỹ thu ật và ứng d ụng tiêu bi ểu. Nội dung ch ươ ng không đi quá sâu vào vi ệc đị nh ngh ĩa chính xác trí tu ệ nhân t ạo là gì, thay vào đó, sinh viên được gi ới thi ệu về nh ững l ĩnh v ực nghiên c ứu chuyên sâu và l ịch s ử phát tri ển, tr ước khi làm quen v ới n ội dung c ụ th ể trong các ch ươ ng sau. Ch ươ ng 2 trình bày cách gi ải quy ết v ấn đề b ằng ph ươ ng pháp tìm ki ếm. Các ph ươ ng pháp tìm ki ếm bao g ồm: tìm ki ếm mù, tìm ki ếm có thông tin, và tìm ki ếm c ục b ộ. Khác v ới một s ố tài li ệu khác v ề trí tu ệ nhân t ạo, n ội dung v ề tìm ki ếm có đố i th ủ không được đề c ập đến trong tài li ệu này. Ch ươ ng 3 tóm t ắt v ề v ấn đề s ử d ụng, bi ểu di ễn tri th ức và suy di ễn, tr ước khi đi sâu trình bày v ề bi ểu di ễn tri th ức và suy di ễn v ới logic. Trong hai h ệ th ống logic được trình bày là logic m ệnh đề và logic v ị t ừ, n ội dung ch ươ ng được dành nhi ều h ơn cho logic v ị t ừ. Do n ội dung v ề l ập trình logic hi ện không còn ứng d ụng nhi ều, chúng tôi không gi ới thi ệu v ề v ấn đề lập trình và xây d ựng ứng d ụng c ụ th ể ở đây. Ch ươ ng 4 là m ở r ộng c ủa bi ểu di ễn tri th ức và suy di ễn v ới vi ệc s ử d ụng nguyên t ắc suy di ễn xác su ất và m ạng Bayes. Sau khi trình bày v ề s ự c ần thi ết c ủa l ập lu ận trong điều ki ện 2
3. không rõ ràng cùng v ới nguyên t ắc suy di ễn xác su ất, ph ần chính c ủa ch ươ ng t ập trung vào khái ni ệm cùng v ới ứng d ụng m ạng Bayes trong bi ểu di ễn tri th ức và suy di ễn. Ch ươ ng 5 là ch ươ ng nh ập môn v ề h ọc máy. Trong ch ươ ng này, sinh viên được làm quen v ới khái ni ệm, nguyên t ắc và ứng d ụng c ủa h ọc máy. Trong ph ạm vi ch ươ ng c ũng trình bày ba k ỹ thu ật h ọc máy dùng cho phân lo ại là cây quy ết đị nh, phân lo ại Bayes và phân lo ại dựa trên ví d ụ. Đây là nh ững ph ươ ng pháp đơ n gi ản, d ễ gi ới thi ệu, đồ ng th ời là nh ững ph ươ ng pháp tiêu bi ểu và có nguyên lý khác nhau, thu ận ti ện để trình bày v ới tính ch ất nh ập môn. Tài li ệu được biên so ạn t ừ kinh nghi ệm gi ảng d ạy h ọc ph ần Nh ập môn trí tu ệ nhân t ạo của tác gi ả t ại H ọc vi ện Công ngh ệ b ưu chính vi ễn thông, trên c ơ s ở ti ếp thu ph ản h ồi t ừ sinh viên và đồng nghi ệp. Tài li ệu có th ể s ử d ụng làm tài li ệu h ọc t ập cho sinh viên đại h ọc ngành công ngh ệ thông tin và các ngành liên quan, ngoài ra có th ể s ử d ụng v ới m ục đích tham kh ảo nhanh cho nh ững ng ười quan tâm t ới trí tu ệ nhân t ạo. Trong quá trình biên so ạn tài li ệu, m ặc dù tác gi ả đã có nhi ều c ố g ắng song không th ể tránh kh ỏi nh ững thi ếu sót. Ngoài ra, trí tu ệ nhân t ạo một l ĩnh v ực rộng, đang ti ến b ộ r ất nhanh của khoa h ọc máy tính đòi h ỏi tài li ệu ph ải được c ập nh ật th ường xuyên. Tác gi ả r ất mong mu ốn nh ận được ý ki ến ph ản h ồi, góp ý cho các thi ếu sót c ũng nh ư ý ki ến v ề vi ệc c ập nh ật, hoàn thi ện n ội dung c ủa tài li ệu. Hà n ội 2010 Tác gi ả 3
4. Mục l ục CH ƯƠ NG 1: GI ỚI THI ỆU CHUNG 7 1.1. KHÁI NI ỆM TRÍ TU Ệ NHÂN T ẠO 7 1.2. L ỊCH S Ử HÌNH THÀNH VÀ PHÁT TRI ỂN 9 1.3. CÁC L ĨNH V ỰC NGHIÊN C ỨU VÀ ỨNG D ỤNG CHÍNH 10 1.3.1. Các l ĩnh v ực nghiên c ứu 10 1.3.2. Một s ố ứng d ụng 11 CH ƯƠ NG 2: GI ẢI QUY ẾT V ẤN ĐỀ B ẰNG TÌM KI ẾM 13 2.1. GI ẢI QUY ẾT V ẤN ĐỀ VÀ KHOA H ỌC TTNT 13 2.2. BÀI TOÁN TÌM KI ẾM TRONG KHÔNG GIAN TR ẠNG THÁI 13 2.2.1. Phát bi ểu bài toán tìm ki ếm 13 2.2.2. Một s ố ví d ụ 14 2.2.3. Các tiêu chu ẩn đánh giá thu ật toán tìm ki ếm 15 2.2.4. Thu ật toán tìm ki ếm t ổng quát và cây tìm ki ếm 16 2.3. TÌM KI ẾM KHÔNG CÓ THÔNG TIN (TÌM KI ẾM MÙ) 17 2.3.1. Tìm ki ếm theo chi ều r ộng (Breadth-first search – BFS) 17 2.3.2. Tìm ki ếm theo giá thành th ống nh ất (Uniform-Cost-Search) 19 2.3.3. Tìm ki ếm theo chi ều sâu (Depth-First-Search: DFS) 19 2.3.4. Tìm theo hai h ướng (Bidirectional Search) 23 2.4. TÌM KI ẾM CÓ THÔNG TIN (INFORMED SEARCH) 25 2.4.1. Tìm ki ếm tham lam (Greedy Search) 25 2.4.2. Thu ật toán A* 26 2.4.3. Các hàm heuristic 27 2.4.4. Thu ật toán IDA* (thu ật toán A* sâu d ần) 28 2.5. TÌM KI ẾM C ỤC B Ộ 30 2.5.1. Thu ật toán leo đồ i (Hill climbing) 31 2.5.2. Thu ật toán tôi thép (Simulated Annealing) 33 2.5.3. Một s ố thu ật toán tìm ki ếm c ục b ộ khác 35 CH ƯƠ NG 3: BI ỂU DI ỄN TRI TH ỨC VÀ SUY DI ỄN LOGIC 36 3.1. S Ự C ẦN THI ẾT S Ử D ỤNG TRI TH ỨC TRONG GI ẢI QUY ẾT V ẤN ĐỀ 36 3.2. LOGIC M ỆNH ĐỀ 37 3.2.1. Cú pháp 37 3.2.2. Ng ữ ngh ĩa 38 3.3. SUY DI ỄN V ỚI LOGIC M ỆNH ĐỀ 40 3.3.1. Suy di ễn logic 40 3.3.2. Suy di ễn s ử d ụng b ảng chân lý 40 3.3.3. Sử d ụng các quy t ắc suy di ễn 41 3.4. LOGIC V Ị T Ừ (LOGIC B ẬC 1) 44 3.4.1. Đặc điểm 44 3.4.2. Cú pháp và ng ữ ngh ĩa 44 4
5. 3.5. SUY DI ỄN V ỚI LOGIC V Ị T Ừ 49 3.5.1. Quy tắc suy di ễn 49 3.5.2. Suy di ễn ti ến và suy di ễn lùi 51 3.5.3. Suy di ễn s ử d ụng phép gi ải 54 3.5.4. Hệ th ống suy di ễn t ự độ ng: l ập trình logic 59 CH ƯƠ NG 4: SUY DI ỄN XÁC SU ẤT 60 4.1. V ẤN ĐỀ THÔNG TIN KHÔNG CH ẮC CH ẮN KHI SUY DI ỄN 60 4.2. NGUYÊN T ẮC SUY DI ỄN XÁC SU ẤT 61 4.3. M ỘT S Ố KHÁI NI ỆM V Ề XÁC SU ẤT 62 4.3.1. Các tiên đề xác su ất 62 4.3.2. Xác su ất đồ ng th ời 62 4.3.3. Xác su ất điều ki ện 63 4.3.4. Tính độc l ập xác su ất 64 4.3.5. Quy t ắc Bayes 65 4.4. M ẠNG BAYES 67 4.4.1. Khái ni ệm m ạng Bayes 67 4.4.2. Tính độc l ập xác su ất trong m ạng Bayes 69 4.4.3. Cách xây d ựng m ạng Bayes 70 4.5. SUY DI ỄN V ỚI M ẠNG BAYES 73 4.5.1. Suy di ễn d ựa trên xác su ất đồ ng th ời 73 4.5.2. Độ ph ức t ạp c ủa suy di ễn trên m ạng Bayes 74 4.5.3. Suy di ễn cho tr ường h ợp riêng đơ n gi ản 74 4.5.4. Suy di ễn b ằng ph ươ ng pháp l ấy m ẫu 76 4.6. ỨNG D ỤNG SUY DI ỄN XÁC SU ẤT 78 CH ƯƠ NG 5: HỌC MÁY 81 5.1. KHÁI NI ỆM H ỌC MÁY 81 5.1.1. Học máy là gì 81 5.1.2. Ứng d ụng c ủa h ọc máy 81 5.1.3. Một s ố khái ni ệm 82 5.1.4. Các d ạng h ọc máy 82 5.2. H ỌC CÂY QUY ẾT ĐỊ NH 84 5.2.1. Khái ni ệm cây quy ết đị nh 84 5.2.2. Thu ật toán h ọc cây quy ết đị nh 85 5.2.3. Các đặc điểm thu ật toán h ọc cây quy ết đị nh 90 5.2.4. Vấn đề quá v ừa d ữ li ệu 91 5.2.5. Sử d ụng thu ộc tính có giá tr ị liên t ục 92 5.2.6. Sử d ụng cách đánh giá thu ộc tính khác 93 5.3. PHÂN LO ẠI BAYES ĐƠN GI ẢN 94 5.3.1. Ph ươ ng pháp phân lo ại Bayes đơn gi ản 94 5.3.2. Vấn đề tính xác su ất trên th ực t ế 96 5.3.3. Ứng d ụng trong phân lo ại v ăn b ản t ự độ ng 96 5.4. H ỌC D ỰA TRÊN VÍ D Ụ: THU ẬT TOÁN K HÀNG XÓM G ẦN NH ẤT 97 5.4.1. Nguyên t ắc chung 97 5
6. 5.4.2. Ph ương pháp k-hàng xóm g ần nh ất 98 5.4.3. Một s ố l ưu ý v ới thu ật toán k-NN 99 5.5. S Ơ L ƯỢC V Ề M ỘT S Ố PH ƯƠ NG PHÁP H ỌC MÁY KHÁC 101 TÀI LI ỆU THAM KH ẢO 104 6
7. CH ƯƠ NG 1: GI ỚI THI ỆU CHUNG 1.1. KHÁI NI ỆM TRÍ TU Ệ NHÂN T ẠO Trí tu ệ nhân t ạo là m ột l ĩnh v ực nghiên c ứu c ủa khoa h ọc máy tính và khoa h ọc tính toán nói chung. Có nhi ều quan điểm khác nhau v ề trí tu ệ nhân t ạo và do v ậy có nhi ều đị nh ngh ĩa khác nhau v ề l ĩnh v ực khoa h ọc này. Mục đích c ủa trí tu ệ nhân t ạo là xây d ựng các th ực th ể thông minh . Tuy nhiên, do r ất khó định ngh ĩa th ế nào là th ực th ể thông minh nên c ũng khó th ống nh ất đị nh ngh ĩa trí tu ệ nhân t ạo. Theo m ột tài li ệu được s ử d ụng r ộng rãi trong gi ảng dạy trí tu ệ nhân t ạo hi ện nay, các đị nh ngh ĩa có th ể nhóm thành b ốn nhóm khác nhau, theo đó, trí tu ệ nhân t ạo là l ĩnh v ực nghiên c ứu vi ệc xây dựng các h ệ th ống có đặ c điểm sau: 1) Hệ th ống hành động nh ư ng ười. 2) Hệ th ống có th ể suy ngh ĩ nh ư ng ười 3) Hệ th ống có thể suy ngh ĩ h ợp lý 4) Hệ th ống hành động h ợp lý Trong s ố các đị nh ngh ĩa trên, nhóm th ứ hai và ba quan tâm t ới quá trình suy ngh ĩ và t ư duy, trong khi nhóm th ứ nh ất và th ứ t ư quan tâm ch ủ y ếu t ới hành vi. Ngoài ra, hai nhóm định ngh ĩa đầu xác đị nh m ức độ thông minh hay m ức độ trí tu ệ b ằng cách so sánh v ới kh ả n ăng suy ngh ĩ và hành động c ủa con ng ười, trong khi hai nhóm đị nh ngh ĩa sau d ựa trên khái ni ệm suy ngh ĩ h ợp lý và hành động h ợp lý. Trong ph ần phân tích bên d ưới ta s ẽ th ầy suy ngh ĩ và hành động h ợp lý khác v ới suy ngh ĩ và hành động nh ư ng ười th ế nào. Sau đây ta s ẽ xem xét c ụ th ể các nhóm đị nh ngh ĩa trên. 1) Hành động nh ư ng ười Theo cách định ngh ĩa này, trí tu ệ nhân t ạo nh ằm t ạo ra các h ệ th ống có kh ả n ăng th ực hi ện nh ững công vi ệc đòi h ỏi có trí tu ệ c ủa con ng ười. Phép th ử Turing (Turing test): Vào n ăm 1950, Alan Turing – nhà toán h ọc ng ười Anh có nhi ều đóng góp cho khoa h ọc máy tính – đã xây d ựng th ủ t ục cho phép đị nh ngh ĩa trí tu ệ. Th ủ t ục này sau đó được g ọi là phép th ử Turing (Turing test), và được th ực hi ện nh ư sau. H ệ th ống được gọi là thông minh, hay có trí tu ệ n ếu h ệ th ống có th ể hành động t ươ ng t ự con ng ười trong các công vi ệc đòi h ỏi trí tu ệ. Trong quá trình th ử, m ột ng ười ki ểm tra s ẽ đặ t các câu h ỏi (d ưới d ạng văn b ản) và nh ận câu tr ả l ời c ũng d ưới d ạng v ăn b ản t ừ h ệ th ống. N ếu ng ười ki ểm tra không phân bi ệt được câu tr ả l ời là do ng ười th ật tr ả l ời hay do máy sinh ra thì h ệ th ống qua được phép th ử và được g ọi là có trí tu ệ. Cần l ưu ý r ằng, phép th ử Turing nguyên b ản không đòi h ỏi có s ự ti ếp xúc vật lý tr ực ti ếp gi ữa ng ười ki ểm tra và h ệ th ống b ị ki ểm tra, do vi ệc t ạo ra h ệ th ống ng ười nhân t ạo m ột cách v ật lý được coi là không liên quan t ới trí tu ệ.
8. Gi ới thi ệu chung Để qua được phép th ử Turing, h ệ th ống c ần có nh ững kh ả n ăng sau: - Xử lý ngôn ng ữ t ự nhiên : để có thể phân tích, hi ểu câu h ỏi và t ổng h ợp câu tr ả l ời trên m ột ngôn ng ữ giao ti ếp thông th ường nh ư ti ếng Vi ệt hay ti ếng Anh. - Bi ểu di ễn tri th ức: ph ục v ụ vi ệc l ưu tri th ức và thông tin trong h ệ th ống. - Suy di ễn: s ử d ụng tri th ức để tr ả l ời câu h ỏi. - Học máy : để có th ể thích nghi v ới hoàn c ảnh và h ọc nh ững m ẫu tr ả l ời. Trong l ịch s ử trí tu ệ nhân t ạo đã có nh ững h ệ th ống nh ư ELIZA được xây d ựng nh ằm m ục đích v ượt qua phép th ử Turing mà không c ần đầ y đủ t ới c ả b ốn kh ả n ăng trên. 2) Suy ngh ĩ nh ư ng ười Nh ững nghiên c ứu theo h ướng này d ựa trên vi ệc nghiên c ứu quá trình nh ận th ức và t ư duy của con ng ười, t ừ đây mô hình hóa và t ạo ra nh ững h ệ th ống có mô hình nh ận th ức, t ư duy t ươ ng tự. Vi ệc tìm hi ểu quá trình nh ận th ức, t ư duy c ủa ng ười có th ể th ực hi ện b ằng cách th ực hi ện thí nghi ệm tâm lý ho ặc theo dõi quá trình sinh ra ý ngh ĩ ở ng ười. Một h ệ th ống trí tu ệ nhân t ạo d ạng này là h ệ th ống GPS, vi ết t ắt c ủa General Problem Solver do Newell và Simon trình di ễn n ăm 1961. GPS là ch ươ ng trình máy tính cho phép gi ải quy ết các bài toán b ằng cách mô ph ỏng chu ỗi suy ngh ĩ c ủa con ng ười khi gi ải quy ết nh ững bài toán nh ư v ậy. Hi ện nay, hướng nghiên c ứu này được th ực hi ện trong khuôn kh ổ khoa h ọc nh ận th ức (cognitive science) và được quan tâm nhi ều h ơn trong khuôn kh ổ tâm lý h ọc. 3) Suy ngh ĩ h ợp lý Một cách ti ếp c ận khác là xây d ựng nh ững h ệ th ống có kh ả n ăng suy di ễn d ựa trên vi ệc s ử dụng các h ệ th ống hình th ức nh ư lô gic. Ti ền thân c ủa cách ti ếp c ận này có g ốc r ễ t ừ tri ết h ọc Hy lạp do Aristot kh ởi x ướng. C ơ s ở ch ủ y ếu là s ử d ụng lô gic để bi ểu di ễn bài toán và gi ải quy ết bằng suy di ễn lô gic. Khó kh ăn ch ủ y ếu c ủa cách ti ếp c ận này là vi ệc mô t ả hay bi ểu di ện bài toán d ưới d ạng các cấu trúc lô gic để có th ể gi ải quy ết được. Trên th ực t ế, tri th ức và thông tin v ề bài toán th ường có yếu tố không đầ y đủ , không chính xác. Ngoài ra, vi ệc suy di ễn lô gic đòi h ỏi kh ối l ượng tính toán lớn khi s ử d ụng trong th ực t ế. 4) Hành động h ợp lý Cách ti ếp c ận này t ập trung vào vi ệc xây d ựng các tác t ử (agent) có kh ả n ăng hành động hợp lý, t ức là hành động để đem l ại k ết qu ả t ốt nh ất ho ặc k ết qu ả k ỳ v ọng t ốt nh ất khi có y ếu t ố không ch ắc ch ắn. C ần l ưu ý r ằng, hành động h ợp lý có th ể khác v ới hành động gi ống con ng ười: con ng ười không ph ải lúc nào c ũng hành động h ợp lý do b ị chi ph ối b ởi các y ếu t ố ch ủ quan. Một đặ c điểm quan tr ọng c ủa hành động h ợp lý là hành động ki ểu này có th ể d ựa trên vi ệc suy ngh ĩ (suy di ễn) h ợp lý ho ặc không. Trong nhi ều tình hu ống, vi ệc hành động theo ph ản x ạ, ch ẳng h ạn khi g ặp nguy hi ểm, không đòi h ỏi suy di ễn ph ức t ạp, nh ưng l ại cho kết qu ả t ốt h ơn. 8
9. Gi ới thi ệu chung 1.2. LỊCH S Ử HÌNH THÀNH VÀ PHÁT TRI ỂN Lịch s ử hình thành và phát tri ển TTNT có th ể chia thành m ột s ố giai đoạn sau (các giai đoạn được chia theo m ức độ phát tri ển và có th ể giao nhau v ề th ời gian): a. Giai đoạn ti ền kh ởi đầ u (1943-1955) Mặc dù ch ưa có khái ni ệm v ề TTNT, giai đoạn này ghi nh ận m ột s ố k ết qu ả có liên quan tr ực ti ếp t ới nghiên c ứu v ề TTNT sau này: - Năm 1943, Warren McCulloch và Walter Pitts mô t ả mô hình m ạng n ơ ron nhân t ạo đầ u tiên, và cho th ấy m ạng n ơ ron nhân t ạo có kh ả n ăng bi ểu di ễn nhi ều hàm s ố toán h ọc. - Năm 1950, Alan Turing công b ố bài báo nh ắc t ới trí tu ệ máy, trong đó l ần đầ u tiên mô t ả khái ni ệm phép th ử Turing, h ọc máy, thu ật toán di truy ền, và h ọc t ăng c ường. - Năm 1956 được coi là n ăm chính th ức ra đờ i c ủa khái ni ệm trí tu ệ nhân t ạo. M ười nhà nghiên c ứu tr ẻ đã t ổ ch ức m ột cu ộc h ội th ảo kéo dài hai tháng t ại tr ường đạ t h ọc Dartmouth v ới m ục đích đặ t n ền móng đầ u tiên cùng v ới tên g ọi chính th ức c ủa TTNT. b. Giai đoạn kh ởi đầ u (1952-1969) Đây là giai đoạn v ới nhi ều thành tích nh ất đị nh c ủa các nghiên c ứu TTNT, được th ể hi ện qua m ột s ố ví d ụ sau: - Các ch ươ ng trình Logic Theorist và sau đó là General Problem Solver c ủa Newell và Simon, có kh ả n ăng ch ứng minh đị nh lý toán h ọc theo cách t ươ ng t ự t ư duy c ủa con ng ười. - Năm 1952, Arthur Samuel xây d ựng m ột s ố ch ươ ng trình ch ơi checkers. Ch ươ ng trình có kh ả n ăng h ọc và đánh th ắng các đố i th ủ nghi ệp d ư. - Năm 1958, John McCarthy đề xu ất ngôn ng ữ Lisp, sau này tr ở thành m ột trong hai ngôn ng ữ thông d ụng nh ất c ủa TTNT. - Mạng n ơ ron nhân tạo ti ếp t ục ti ếp t ục được phát tri ển v ới m ột s ố phát minh m ới nh ư mạng adalines (1962), Perceptron c ủa Rosenblatt (1962), cho phép gi ải quy ết nhi ểu bài toán h ọc máy. c. H ệ th ống d ựa trên trí th ức (1969-1979) Các ch ươ ng trình trí tu ệ nhân t ạo xây d ựng trong giai đoạn tr ước có m ột s ố nh ất đị nh do không có tri th ức v ề l ĩnh v ực liên quan, và do v ậy không th ể gi ải quy ết nh ững bài toán khó, đòi hỏi kh ối l ượng tính toán l ớn ho ặc nhi ều tri th ức chuyên sâu. Để kh ắc ph ục, giai đoạn này chú tr ọng t ới vi ệc s ử d ụng nhi ều tri th ức, thông tin đặ c thù cho l ĩnh v ực h ẹp c ủa v ấn đề c ần gi ải quy ết. Sau đây là m ột s ố h ệ th ống nh ư v ậy: - DENDRAL là ch ươ ng trình h ệ chuyên gia xây d ựng t ại tr ường Stanford, cho phép d ự đoán c ấu trúc phân t ử. Ch ươ ng trình làm vi ệc d ựa trên các lu ật do chuyên gia hóa cung cấp. M ột trong các tác gi ả c ủa DENDRAL, sau đó đã cùng v ới c ộng s ự xây d ựng MYCIN, h ệ chuyên gia cho phép ch ẩn đoán b ệnh nhi ễm trùng máy. V ới kho ảng 450 quy 9
10. Gi ới thi ệu chung tắc do chuyên gia cung c ấp, h ệ th ống có ch ất l ượng ch ẩn đoán t ươ ng đươ ng chuyên gia trong l ĩnh v ực này. - Vi ệc s ử d ụng tri th ức c ũng được s ử d ụng để gi ải quy ết v ấn đề hi ểu ngôn ng ữ t ự nhiên, ví dụ trong h ệ th ống d ịch t ự độ ng. d. TTNT có s ản ph ẩm th ươ ng m ại (1980 đế n nay) Sau thành công c ủa nh ững h ệ chuyên gia đầu tiên, vi ệc xây d ựng hệ chuyên gia được th ươ ng m ại hóa t ừ n ăm 1980 và đặc bi ệt phát tri ển cho t ới 1988. Sau giai đoạn này, do m ột s ố hạn ch ế c ủa h ệ chuyên gia, TTNT r ơi vào m ột giai đoạn trì tr ệ, không có nh ững b ước ti ến đáng kể. Giai đoạn này c ũng đánh d ấu s ự tr ở l ại c ủa m ạng nơ ron nhân t ạo sau m ột th ời gian không có các phát minh và ứng d ụng đáng k ể. Cho đế n hi ện này, m ạng n ơ ron nhân t ạo v ẫn được s ử dụng t ươ ng đối nhi ều cho h ọc máy và nh ư các ch ươ ng trình nh ận d ạng, phân lo ại t ự độ ng. e. TTNT chính th ức tr ở thành ngành khoa học (1987 đế n nay) Bắt đầ u t ừ giai đoạn này, TTNT đã có ph ươ ng pháp nghiên c ứu riêng c ủa mình, tuân theo các yêu c ầu chung đố i v ới ph ươ ng pháp nghiên c ứu khoa h ọc. Ch ẳng h ạn, k ết qu ả c ần ch ứng minh b ằng th ực nghi ệm, và được phân tích k ỹ l ưỡng b ằng khoa h ọc th ống kê. Nhi ều phát minh tr ước đây c ủa TTNT nh ư m ạng n ơ ron nhân t ạo được phân tích và so sánh kỹ càng v ới nh ững k ỹ thu ật khác c ủa th ống kê, nh ận d ạng, và h ọc máy, do v ậy các ph ươ ng pháp không còn mang tính kinh nghi ệm thu ần túy mà đều d ựa trên các c ơ s ở lý thuy ết rõ ràng h ơn. 1.3. CÁC L ĨNH V ỰC NGHIÊN C ỨU VÀ ỨNG D ỤNG CHÍNH 1.3.1. Các l ĩnh v ực nghiên c ứu Trí tu ệ nhân t ạo được chia thành m ột s ố l ĩnh v ực nghiên c ứu nh ỏ h ơn nh ằm gi ải quy ết nh ững v ấn đề khác nhau khi xây d ựng m ột h ệ th ống trí tu ệ nhân t ạo. Thông th ường, một h ệ th ống trí tu ệ nhân t ạo hoàn ch ỉnh, làm vi ệc trong vi ệc m ột môi tr ường nào đó c ần có kh ả n ăng: cảm nh ận (perception), suy di ễn (reasoning), và hành động (action). L ĩnh v ực nghiên c ứu c ủa trí tu ệ nhân t ạo c ũng được phân chia theo ba thành ph ần này. a. C ảm nh ận Hệ th ống c ần có c ơ ch ế thu nh ận thông tin liên quan t ới ho ạt độ ng t ừ môi tr ường bên ngoài. Đó có th ể là camera, c ảm ứng âm thanh, các c ảm bi ến khác. Đó c ũng có th ể đơn gi ản h ơn là thông tin do ng ười dùng nh ập vào ch ươ ng trình nh ập vào b ằng tay. Để bi ến đổ i thông tin nh ận được v ề d ạng có th ể hi ểu được, thông tin c ần được x ử lý nh ờ nh ững k ỹ thu ật thu ộc các l ĩnh v ực sau: - Th ị giác máy (computer vision): nghiên c ứu v ề vi ệc thu nh ận, x ử lý, nh ận d ạng thông tin hình ảnh (ch ẳng h ạn t ừ camera) thành bi ểu di ễn m ức cao h ơn nh ư các đối t ượng xung quanh để máy tính sau đó có th ể hi ểu được. 10
11. Gi ới thi ệu chung - Xử lý ngôn ng ữ t ự nhiên (natural language processing): phân tích thông tin, d ữ li ệu nh ận được d ưới d ạng âm thanh ho ặc v ăn b ản và được trình bày d ưới d ạng ngôn ng ữ t ự nhiên của con ng ười. b. Suy di ễn Là quá trình đư a ra k ết lu ận v ề hành động trên c ơ s ở c ảm nh ận và tri th ức bên trong. Thành ph ần này được xây d ựng d ựa trên k ỹ thu ật t ừ nh ững l ĩnh v ực nghiên c ứu sau: - Bi ểu di ễn tri th ức (knowledge representation): s ự ki ện, thông tin, tri th ức v ề th ế gi ới xung quanh c ần được bi ểu di ễn d ưới d ạng máy tính có th ể “hi ểu” được, ch ẳng h ạn d ưới dạng lô gic ho ặc ngôn ng ữ TTNT nào đó. - Tìm ki ếm (search): nhi ều bài toán ho ặc v ấn đề có th ể phát bi ểu và gi ải quy ết nh ư bài toán tìm ki ếm trong không gian tr ạng thái. TTNT nghiên c ứu cách tìm ki ếm khi s ố tr ạng thái trong không gian quá l ớn. - Suy di ễn (inference hay reasoning): là quá trình sinh ra k ết lu ận ho ặc s ự ki ện m ới t ừ nh ững s ự ki ện và thông tin đã có. - Học máy (machine learning): làm t ăng hi ệu qu ả gi ải quy ết v ấn đề nh ờ trên d ữ li ệu và kinh nghi ệm đã có. - Lập k ế ho ạch (planning): là quá trình sinh ra các b ước hành động c ần th ực hi ện để th ực hi ện m ột m ục tiêu nào đó d ựa trên thông tin v ề môi tr ường, v ề hi ệu qu ả t ừng hành động, về tình hu ống hi ện th ời và m ục tiêu c ần đạ t. c. Hành động Cho phép h ệ th ống tác độ ng vào môi tr ường xung quanh ho ặc đơn gi ản là đư a ra thông tin về k ết lu ận c ủa mình. Thành ph ần này được xây d ựng d ựa trên nh ững k ỹ thu ật sau: - Kỹ thu ật rôb ốt (robotics): là k ỹ thu ật xây d ựng các cơ quan ch ấp hành nh ư cánh tay ng ười máy, t ổng h ợp ti ếng nói, t ổng h ợp ngôn ng ữ t ự nhiên. 1.3.2. Một s ố ứng d ụng a. Các ch ươ ng trình trò ch ơi Vi ệc xây d ựng ch ươ ng trình có kh ả n ăng ch ơi nh ững trò ch ơi trí tu ệ là m ột l ĩnh v ực có nhi ều thành t ựu cúa TTNT. Tiêu bi ểu là ch ươ ng trình c ờ vua Deep Blue đã t ừng th ắng vô đị ch c ờ vua th ế gi ới Gary Kasparov. b. Nh ận d ạng ti ếng nói Cho phép bi ến đổ i t ừ âm thanh thu được thành các t ừ. M ột trong nh ững h ệ th ống nh ận d ạng ti ếng nói th ươ ng m ại đầ u tiên là PEGASUS được dùng t ại American Airlines cho phép nh ận thông tin đặt ch ỗ t ự độ ng qua điện tho ại. Ph ổ bi ến h ơn là nh ững ch ươ ng trình nh ận d ạng cho phép quay s ố di độ ng b ằng gi ọng nói. Nhìn chung, các h ệ th ống nh ận d ạng ti ếng nói hi ện nay có độ chính xác t ươ ng đối h ạn ch ế. c. Th ị giác máy tính 11
12. Gi ới thi ệu chung Tiêu bi ểu là các h ệ th ống nh ận d ạng ch ữ in v ới độ chính xác g ần nh ư tuy ệt đố i, h ệ th ống nh ận d ạng tròng m ắt, vân tay, m ặt ng ười. Nh ững h ệ th ống d ạng này được s ử d ụng r ộng rãi trong sản xu ất để ki ểm tra s ản ph ẩm, trong h ệ th ống camera an ninh. Nhi ều nghiên c ứu thu ộc vùng ứng dụng này đang được th ực hi ện nh ư nghiên c ứu nh ận d ạng ch ữ vi ết tay. d. H ệ chuyên gia Là các h ệ th ống làm vi ệc d ựa trên kinh nghi ệm và tri th ức c ủa chuyên gia trong m ột l ĩnh vực t ươ ng đối h ẹp nào đó để đưa ra khuy ến cáo, k ết lu ận, chu ẩn đoán m ột cách t ự độ ng. Các ví dụ g ồm: - MYCIN: h ệ chuyên gian đầu tiên ch ẩn đoán b ệnh v ề nhi ễm trùng máu và cách điều tr ị. - XCON c ủa DEC: h ỗ tr ợ ch ọn c ấu hình máy tính t ự độ ng. e. X ử lý, hi ểu ngôn ng ữ t ự nhiên Tiêu bi ểu là các h ệ th ống d ịch t ự độ ng nh ư h ệ th ống d ịch c ủa Google, các h ệ th ống tóm t ắt nội dung v ăn b ản t ự độ ng. Nh ững h ệ th ống này s ử d ụng nh ững thành ph ần đơn gi ản h ơn nh ư các phân h ệ phân tích hình thái, cú pháp, ng ữ ngh ĩa. f. L ập k ế ho ạch, l ập th ời khóa bi ểu Kỹ thu ật TTNT được s ử d ụng nhi ều trong bài toán l ập th ời khóa bi ểu cho tr ường h ọc, xí nghi ệp, các bài toán l ập k ế ho ạch khác. M ột ví d ụ l ập k ế ho ạch thành công v ới quy mô l ớn là k ế ho ạch đả m b ảo h ậu c ần cho quân độ i M ỹ trong chi ến d ịch C ơn bão sa m ạc t ại Iraq đã được th ực hi ện g ần như hoàn toàn d ựa trên k ỹ thu ật TTNT. 12
13. CH ƯƠ NG 2: GI ẢI QUY ẾT V ẤN ĐỀ B ẰNG TÌM KI ẾM 2.1. GI ẢI QUY ẾT V ẤN ĐỀ VÀ KHOA H ỌC TTNT Tại sao ph ải tìm ki ếm Tìm ki ếm là m ột trong nh ững h ướng nghiên c ứu quan tr ọng c ủa TTNT. M ục đích c ủa TTNT là tìm cách gi ải quy ết v ấn đề hay bài toán m ột cách h ợp lý, trong khi đó, m ột l ớp l ớn các bài toán có th ể phát bi ểu và gi ải quy ết dưới d ạng tìm ki ếm. Sau đây là m ột s ố ví d ụ các bài toán nh ư v ậy. - Trò ch ơi: nhi ều trò ch ơi, ví d ụ c ờ vua, th ực ch ất là quá trình tìm ki ếm n ước đi c ủa các bên trong s ố nh ững n ước mà lu ật ch ơi cho phép, để giành l ấy ưu th ế cho bên mình. - Lập th ời khóa bi ểu: l ập th ời khóa bi ểu là l ựa ch ọn th ứ t ự, th ời gian, tài nguyên (máy móc, địa điểm, con ng ười) th ỏa mãn m ột s ố tiêu chí nào đó. Nh ư v ậy, l ập th ời khóa bi ểu có th ể coi nh ư quá trình tìm ki ếm trong s ố t ổ h ợp ph ươ ng án s ắp x ếp ph ươ ng án đáp ứng yêu c ầu đề ra. - Tìm đường đi: trong s ố nh ững đường đi, l ựa ch ọn đường đi t ới đích, có th ể th ỏa mãn một s ố tiêu chí nào đó nh ư tiêu chí t ối ưu v ề độ dài, th ời gian, giá thành.v.v. - Lập k ế ho ạch: là l ựa ch ọn chu ỗi hành động c ơ s ở cho phép đạ t m ục tiêu đề ra đồ ng th ời th ỏa mãn các yêu c ầu ph ụ. Sự ph ổ bi ến c ủa các v ấn đề có tính ch ất tìm ki ếm d ẫn t ới yêu c ầu phát bi ểu bài toán tìm ki ếm m ột cách t ổng quát, đồ ng th ời xây d ựng ph ươ ng pháp gi ải bài toán tìm ki ếm sao cho hi ệu qu ả, thu ận l ợi. Do v ậy, tìm ki ếm đã được nghiên c ứu trong khuôn kh ổ toán r ời r ạc, lý thuy ết thu ật toán. Trong khuôn kh ổ TTNT, tìm ki ếm được đặ c bi ệt quan tâm t ừ khía c ạnh xây d ựng ph ươ ng pháp cho phép tìm ra k ết qu ả trong tr ường h ợp không gian tìm ki ếm có kích th ước l ớn khi ến cho nh ững ph ươ ng pháp truy ền th ống g ặp khó kh ăn. Ngoài vi ệc đứ ng độ c l ập nh ư ch ủ đề nghiên c ứu riêng, tìm ki ếm còn là c ơ s ở cho r ất nhi ều nhánh nghiên c ứu khác c ủa TTNT nh ư l ập k ế ho ạch, h ọc máy, x ử lý ngôn ng ữ t ự nhiên, suy di ễn. 2.2. BÀI TOÁN TÌM KI ẾM TRONG KHÔNG GIAN TR ẠNG THÁI 2.2.1. Phát bi ểu bài toán tìm ki ếm Một cách t ổng quát, một v ấn đề có th ể gi ải quy ết thông qua tím ki ếm b ằng cách xác đị nh tập h ợp t ất c ả các ph ươ ng án, đối t ượng, hay tr ạng thái liên quan, gọi chung là không gian tr ạng thái . Th ủ t ục tìm ki ếm sau đó s ẽ kh ảo sát không gian tr ạng thái theo m ột cách nào đó để tìm ra l ời gi ải cho v ấn đề . Tùy vào cách th ức kh ảo sát không gian tr ạng thái c ụ th ể, ta s ẽ có nh ững ph ươ ng pháp tìm ki ếm khác nhau.
14. Gi ải quy ết v ấn đề bằng tìm ki ếm Để có th ể kh ảo sát không gian tr ạng thái, thu ật toán tìm ki ếm b ắt đầ u từ m ột tr ạng thái xu ất phát nào đó, sau đó s ử d ụng nh ững phép bi ến đổ i tr ạng thái để nh ận bi ết và chuy ển sang tr ạng thái khác. Quá trình tìm ki ếm k ết thúc khi tìm ra l ời gi ải, t ức là khi đạt tới tr ạng thái đích . Bài toán tìm ki ểm c ơ b ản có th ể phát bi ểu thông qua b ốn thành ph ần chính sau: • Tập các tr ạng thái Q. Đây chính là không gian tr ạng thái c ủa bài toán. • Tập (không r ỗng) các tr ạng thái xu ất phát S (S ⊆ Q). Thu ật toán tìm ki ếm s ẽ xu ất phát t ừ một trong nh ững tr ạng thái này để kh ảo sát không gian tìm ki ếm. • Tập (không r ỗng) các tr ạng thái đích G (G ⊆ Q). Trạng thái đích có th ể được cho m ột cách t ường minh, t ức là ch ỉ ra c ụ th ể đó là tr ạng thái nào, ho ặc không t ường minh. Trong tr ường h ợp sau, thay vì tr ạng thái c ụ th ể, bài toán s ẽ quy đị nh m ột s ố điều ki ện mà tr ạng thái đích c ần th ỏa mãn. Ví d ụ, khi ch ơi c ờ vua, thay vì ch ỉ ra v ị trí c ụ th ể quân c ờ, ta ch ỉ có quy t ắc cho bi ết tr ạng thái chi ếu hết. • Các toán t ử, còn g ọi là hành động hay chuy ển độ ng . Th ực ch ất đây là m ột ánh x ạ P: Q→Q, cho phép chuy ển t ừ tr ạng thái hi ện th ời sang các tr ạng thái khác. Với m ỗi tr ạng thái n, P (n) là t ập các tr ạng thái được sinh ra khi áp d ụng toán t ử hay chuy ển độ ng P. • Giá thành c: Q x Q → R. Trong m ột s ố tr ường h ợp, quá trình tìm ki ếm c ần quan tâm t ới giá thành đường đi. Giá thành để di chuy ển t ừ nút x tới nút hàng xóm y được cho d ưới dạng số d ươ ng c (x, y). 2.2.2. Một s ố ví d ụ Các thành ph ần c ủa bài toán tìm ki ếm được minh h ọa trên m ột s ố ví d ụ sau. Đây là nh ững ví d ụ không có ứng d ụng th ực t ế nh ưng đơ n gi ản, d ễ s ử d ụng cho m ục đích minh h ọa. Bài toán đố tám ô Cho hình ch ữ nh ật được chia thành chín ô nh ư trên hình d ưới, trong đó tám ô được đánh s ố từ 1 đế n 8 và m ột ô tr ống. Có th ể thay đổ i v ị trí các s ố b ằng cách di chuy ển ô tr ống. M ỗi l ần di chuy ển, ô tr ống có th ể đổ i ch ỗ v ới m ột ô s ố ở ngay phía trên, phía d ưới, bên ph ải ho ặc bên trái. 3 1 6 1 2 5 8 3 4 5 2 7 4 6 7 8 Tr ạng thái xu ất phát Tr ạng thái đích Hình 2.1. Trò đố 8 ô 14
15. Gi ải quy ết v ấn đề bằng tìm ki ếm Yêu c ầu c ủa bài toán là th ực hi ện các di chuy ển để chuy ển t ừ m ột s ắp x ếp các ô (ví d ụ trên hình bên trái) sang m ột cách s ắp x ếp khác (hình bên ph ải). Ngoài ra có th ể có yêu c ầu ph ụ, ví d ụ cần di chuy ển sao cho s ố l ần đổ i ch ỗ ô tr ống là t ối thi ểu. Trò đố 8 ô có th ể phát bi ểu nh ư bài toán tìm ki ếm v ới các thành ph ần sau. - Tr ạng thái (state): mỗi tr ạng thái là m ột s ắp x ếp c ụ th ể vị trí các ô - Hành động (action): mỗi hành động t ươ ng ứng v ới m ột di chuy ển ô tr ống trái, ph ải, lên, xu ống - Mục tiêu và ki ểm tra (goal & test): so sánh v ới tr ạng thái đích - Giá thành (cost): b ằng t ổng số l ần dịch chuy ển ô tr ống. Bài toán n con h ậu Cho m ột bàn c ờ vua kích th ước n x n. C ần x ếp n con h ậu lên bàn c ờ sao cho không có đôi hậu nào đe d ọa nhau. Đây c ũng là bài toán tìm ki ếm v ới các thành ph ần c ụ th ể nh ư sau: - Tr ạng thái: s ắp x ếp của c ả n con h ậu trên bàn c ờ, ho ặc s ắp x ếp c ủa 0 đế n n con h ậu trên bàn c ờ. - Tr ạng thái xu ất phát: - Tr ạng thái đích: s ắp x ếp n con h ậu trên bàn c ờ sao cho không có đôi h ậu nào đe d ọa nhau. - Chuy ển độ ng: Có nhi ều cách khác nhau: đổ i ch ỗ 2 con h ậu, di chuy ển m ột con h ậu sang ô khác (cùng c ột, khác c ột). 2.2.3. Các tiêu chu ẩn đánh giá thu ật toán tìm ki ếm Với bài toán tìm ki ếm được phát bi ểu nh ư trên, nhi ều thu ật toán tìm ki ếm có th ể s ử d ụng để kh ảo sát không gian và tìm ra l ời gi ải. Thu ật toán tìm ki ếm được đánh giá theo b ốn tiêu chu ẩn sau: • Độ ph ức t ạp tính toán : được xác đị nh b ằng kh ối l ượng tính toán c ần th ực hi ện để tìm ra lời gi ải. Thông th ường, kh ối l ượng tính toán được xác đị nh b ằng s ố l ượng tr ạng thái c ần xem xét tr ước khi tìm ra l ời gi ải. • Yêu c ầu b ộ nh ớ: được xác đị nh b ằng s ố l ượng tr ạng thái c ần l ưu tr ữ đồ ng th ời trong b ộ nh ớ khi th ực hi ện thu ật toán. • Tính đầy đủ : n ếu bài toán có l ời gi ải thì thu ật toán có kh ả n ăng tìm ra l ời gi ải đó không? Nếu có, ta nói r ằng thu ật toán có tính đầ y đủ , trong tr ường h ợp ng ược l ại ta nói thu ật toán không có tính đầy đủ . 15
16. Gi ải quy ết v ấn đề bằng tìm ki ếm • Tính t ối ưu: n ếu bài toán có nhi ều l ời gi ải thì thu ật toán có cho phép tìm ra l ời gi ải t ốt nh ất không? 2.2.4. Thu ật toán tìm ki ếm tổng quát và cây tìm ki ếm Thu ật toán tổng quát d ựa trên nguyên lý chung nh ư sau: Ý t ưởng chung: xem xét tr ạng thái, s ử d ụng các hàm bi ến đổ i tr ạng thái để di chuy ển trong không gian tr ạng thái cho t ới khi đạ t đế n tr ạng thái mong mu ốn. Ý t ưởng này được th ể hi ện qua thu ật toán tìm ki ếm t ổng quát trên hình 2.2. Search( Q, S, G, P) (Q: không gian tr ạng thái, S: tr ạng thái b ắt đầ u, G: đích, P: hành động) Đầu vào: bài toán tìm ki ếm với 4 thành ph ần nh ư trên Đầu ra: tr ạng thái đích Kh ởi t ạo: O ← S (O: danh sách các nút mở, b ước này làm nhi ệm v ụ gán S cho O ) While( O ≠ Ø) do 1. ch ọn nút n ∈ O và xóa n kh ỏi O 2. If n ∈ G, return ( đường đi t ới n) 3. Thêm P(n) vào O Return: Không có l ời gi ải Hình 2.2. Thu ật toán tìm ki ếm t ổng quát Thu ật toán tìm ki ếm t ổng quát sinh ra m ột cây tìm ki ếm, trong đó mỗi tr ạng thái t ươ ng ứng với m ột nút trên cây. Tr ạng thái xu ất phát t ươ ng ứng v ới gốc cây, nh ững tr ạng thái được m ở r ộng tạo thành các nút th ế h ệ ti ếp theo. Trên hình 2.3 là ví d ụ m ột cây tìm ki ếm sinh ra cho bài toán đố 8 ô. Thu ật toán trên c ũng gi ả s ử r ằng m ỗi nút đã được duy ệt s ẽ không được duy ệt l ại l ần n ữa, do vậy không c ần l ưu tr ữ danh sách nh ững nút đã duy ệt. Trên th ực t ế, trong nhi ều tr ường h ợp, vi ệc di chuy ển trong không gian tr ạng thái s ẽ d ẫn t ới nh ững nút đã duy ệt qua và t ạo thành vòng l ặp. Trong tr ường h ợp nh ư v ậy cây tìm ki ếm có th ể là vô t ận và c ần có cách ki ểm tra để không xem xét l ại nút đã duy ệt. Sau đây là m ột s ố thu ật ng ữ s ử d ụng khi trình bày v ề thu ật toán tìm ki ếm: • Các nút mở (nút biên): là các nút đang ch ờ để được m ở r ộng ti ếp • Sau khi nút được m ở r ộng, ta xóa nó kh ỏi danh sách các nút mở và nút khi đó g ọi là nút đóng. 16
17. Gi ải quy ết v ấn đề bằng tìm ki ếm Cần l ưu ý là trong thu ật toán tìm ki ếm t ổng quát ở trên không quy định rõ nút nào trong s ố các nút biên (n ằm trong t ập O) được ch ọn để m ở r ộng. Vi ệc l ựa ch ọn nút c ụ th ể ph ụ thu ộc vào từng ph ươ ng pháp tìm ki ếm và được trình bày trong nh ững ph ần ti ếp theo. Hình 2.3. Cây tìm ki ếm cho bài toán 8 ô 2.3. TÌM KI ẾM KHÔNG CÓ THÔNG TIN (TÌM KI ẾM MÙ) Định ngh ĩa: Tìm ki ếm không có thông tin, còn g ọi là tìm ki ếm mù (blind, uninformed search) là ph ươ ng pháp duy ệt không gian tr ạng thái ch ỉ s ử d ụng các thông tin theo phát bi ểu c ủa bài toán tìm ki ếm t ổng quát trong quá trình tìm ki ếm. Tìm ki ếm không có thông tin bao g ồm m ột s ố thu ật toán khác nhau. Điểm khác nhau c ăn bản c ủa các thu ật toán là ở th ứ t ự m ở r ộng các nút biên. Sau đây ta s ẽ xem xét các thu ật toán tìm theo chi ều r ộng, tìm theo chi ều sâu, tìm ki ếm sâu d ần và m ột s ố bi ến th ể c ủa nh ững thu ật toán này. 2.3.1. Tìm ki ếm theo chi ều rộng (Breadth-first search – BFS) Nguyên t ắc của tìm ki ếm theo chi ều r ộng là trong s ố nh ững nút biên lựa ch ọn nút nông nh ất (g ần nút g ốc nh ất) để m ở r ộng. 17
18. Gi ải quy ết v ấn đề bằng tìm ki ếm Khi m ở r ộng m ột nút ta c ần s ử d ụng con tr ỏ ng ược để ghi l ại nút cha c ủa nút v ừa được m ở ra. Con tr ỏ này được s ử dụng để tìm ng ược l ại đường đi v ề tr ạng thái xu ất phát khi tìm được tr ạng thái đích. Có th ể nh ận th ấy, để th ực hi ện nguyên t ắc tìm ki ếm theo chi ều r ộng, ta c ần l ựa ch ọn nút được thêm vào s ớm h ơn trong danh sách nút biên O để m ở r ộng. Điều này có th ể th ực hi ện d ễ dàng b ằng cách dùng m ột hàng đợi để l ưu các nút biên. Thu ật toán tìm theo chi ều r ộng được th ể hi ện trên hình sau: BFS (Q, S, G, P) Đầu vào: bài toán tìm ki ếm Đầu ra: tr ạng thái đích Kh ởi t ạo: O ← S While( O không r ỗng) do 1. Chọn nút đầu tiên n từ O và xóa n kh ỏi O 2. If n ∈ G, return ( đường đi t ới n) 3. Thêm P(n) vào cu ối O Return: Không có l ời gi ải Hình 2.4. Thu ật toán tìm ki ếm theo chi ều r ộng Tính ch ất c ủa tìm theo chi ều r ộng: Đối chi ếu v ới các tiêu chu ẩn ở trên, tìm ki ếm theo chi ều r ộng có nh ững tính ch ất sau: • Thu ật toán có tính đầy đủ , t ức là n ếu bài toán có l ời gi ải, tìm ki ếm theo chi ều r ộng đả m bảo tìm ra l ời gi ải. • Có tính t ối ưu. Đảm b ảo tìm ra l ời gi ải n ằm g ần nút g ốc nh ất. Tuy nhiên, trong tr ường h ợp giá thành đường đi gi ữa các nút không b ằng nhau thì điều này ch ưa đảm b ảo tìm ra đường đi ng ắn nh ất. • Độ ph ức t ạp c ủa thu ật toán l ớn (gi ả s ử m ỗi b ước có b node được m ở r ộng trên b nhánh và có d m ức, khi đó độ ph ức t ạp c ủa thu ật toán là O( bd )). Gi ả sử rằng, m ỗi tr ạng thái khi được phát tri ển s ẽ sinh ra b tr ạng thái k ề. Ta s ẽ gọi b là nhân t ố nhánh . Gi ả sử rằng, nghi ệm c ủa bài toán là đường đi có độ dài d. B ởi nhi ều nghi ệm có th ể được tìm ra t ại m ột đỉnh b ất k ỳ ở mức d của cây tìm ki ếm, do đó s ố đỉnh c ần xem xét để tìm ra nghi ệm là: 1 + b + b 2 + + b d-1 + k 18
19. Gi ải quy ết v ấn đề bằng tìm ki ếm Trong đó k có th ể là 1, 2, , b d. Do đó s ố lớn nh ất các đỉnh c ần xem xét là: 1 + b + b 2 + + b d Nh ư v ậy, độ ph ức t ạp th ời gian c ủa thu ật toán tìm ki ếm theo b ề rộng là O(b d). Độ ph ức t ạp không gian c ũng là O(b d), b ởi vì ta c ần l ưu vào danh sách L t ất c ả các đỉnh c ủa cây tìm ki ếm ở mức d, s ố các đỉnh này là b d. 2.3.2. Tìm ki ếm theo giá thành th ống nh ất (Uniform-Cost-Search) Trong tr ường h ợp giá thành di chuy ển gi ữa hai nút là không b ằng nhau gi ữa các c ặp nút, tìm theo chi ều r ộng không cho tìm ra l ời gi ải có giá thành nh ỏ nh ất và do v ậy không t ối ưu. Để tìm ra đường đi ng ắn nh ất trong tr ường h ợp này c ần s ử d ụng m ột bi ến th ể c ủa tìm theo chi ều r ộng có tên g ọi là tìm ki ếm theo giá thành duy nh ất. Ph ươ ng pháp: ch ọn node mở r ộng có giá thành nh ỏ nh ất để m ở r ộng tr ước thay vì ch ọn nút nông nh ất nh ư trong tìm theo chi ều r ộng. Thu ật toán: được bi ến đổ i t ừ tìm ki ếm theo chi ều r ộng b ằng cách thay ba b ước trong vòng lặp While nh ư sau: 1. Chọn node n có giá thành nh ỏ nh ất thu ộc O và xóa n kh ỏi O 2. If n ∈ G, return ( đường đi t ới n) 3. Thêm P(n) và giá thành đường đi t ới n vào O Thu ật toán tìm ki ếm theo giá thành th ống nh ất còn được g ọi là thu ật toán Dijkstra 2.3.3. Tìm ki ếm theo chi ều sâu (Depth-First-Search: DFS) Nguyên t ắc của tìm ki ếm theo chi ều sâu là trong s ố nh ững nút biên l ựa ch ọn nút sâu nh ất (xa nút g ốc nh ất) để m ở r ộng. Để th ực hi ện nguyên t ắc trên, ta c ần l ựa ch ọn nút được thêm vào sau cùng trong t ập nút biên O để m ở r ộng. Điều này có th ể th ực hi ện d ễ dàng b ằng cách dùng m ột ng ăn x ếp để l ưu các nút biên, các nút được thêm vào và l ấy ra theo nguyên lý LIFO. Thu ật toán tìm ki ếm theo chi ều sâu được th ể hi ện trên hình 2.5. Tính ch ất thu ật toán tìm theo chi ều sâu: • Thu ật toán không đầ y đủ trong tr ường h ợp s ố tr ạng thái là vô h ạn (c ứ đi theo nhánh không đúng mãi mà không chuy ển sang nhánh khác được). • Thu ật toán không t ối ưu: thu ật toán có th ể m ở r ộng nh ững nhánh d ẫn t ới l ời gi ải không t ối ưu tr ước, đặ c bi ệt trong tr ường h ợp có nhi ều l ời gi ải. • Độ ph ức t ạp c ủa thu ật toán ở tr ường h ợp x ấu nh ất là O( bm ) v ới m là độ sâu t ối đa. Trên th ực t ế DFS tìm ra l ời gi ải nhanh h ơn BFS, đặc bi ệt n ếu t ồn t ại nhi ều l ời gi ải. 19
20. Gi ải quy ết v ấn đề bằng tìm ki ếm • Bộ nh ớ c ần nh ớ t ối đa b*m (m ỗi m ức ch ỉ nh ớ b node, v ới m m ức). Để đánh giá độ ph ức tạp không gian c ủa tìm ki ếm theo độ sâu ta có nh ận xét r ằng, khi ta phát tri ển m ột đỉ nh u trên cây tìm ki ếm theo độ sâu, ta ch ỉ c ần l ưu các đỉnh ch ưa được phát tri ển mà chúng là các đỉnh con c ủa các đỉ nh n ằm trên đường đi t ừ g ốc t ới đỉ nh u. Nh ư v ậy đối v ới cây tìm ki ếm có nhân t ố nhánh b và độ sâu l ớn nh ất là m, ta ch ỉ c ần l ưu ít h ơn b*m đỉnh. Ưu c ầu bộ nh ớ so v ới tìm theo chi ều r ộng là ưu điểm n ổi b ật nh ất c ủa tìm theo chi ều sâu. DFS(Q, S, G, P) Đầu vào: bài toán tìm ki ếm Đầu ra: (đường đi t ới) tr ạng thái đích Kh ởi t ạo: O ←S While(O ≠ Ø) do 1. Chọn node đầ u tiên n ∈ O và xóa n kh ỏi O 2. If n ∈ G, return ( đường đi t ới n) 3. Thêm P(n) vào đầu O Return: Không có l ời gi ải Hình 2.5. Thu ật toán tìm ki ếm theo chi ều sâu Tránh các nút l ặp: Trong nhi ều tr ường h ợp có th ể có nhi ều đường đi cùng d ẫn t ới m ột nút. Khi đó cây tìm ki ếm s ẽ tr ở thành đồ th ị tìm ki ếm, t ức là có nhi ều h ơn m ột đường đi gi ữa hai nút. Thu ật toán tìm ki ếm khi đó s ẽ m ở rộng cùng m ột nút nhi ều l ần làm t ăng kh ối l ượng tính toán không c ần thi ết. Th ậm chí có th ể d ẫn t ới vòng l ặp vô h ạn. Để tránh m ở r ộng nh ững nút đã m ở r ộng r ồi c ần ghi l ại nh ững nút đã được m ở r ộng. Đố i với tìm ki ềm theo chi ều sâu có hai cách ki ểm tra: - Ch ỉ ghi nh ớ các nút đã m ở r ộng c ủa nhánh hi ện th ời, n ếu nút chu ẩn b ị m ở r ộng đã có trong s ố này thì không c ần m ở r ộng n ữa. Ph ươ ng pháp này yêu c ầu nh ớ ít nút, th ời gian ki ểm tra c ũng nhanh, tuy nhiên ch ỉ cho phép tránh vòng l ặp vô h ạn và không cho phép gi ảm kh ối l ượng tính toán trong tr ường hợp nhi ều nhánh c ủa đồ th ị tìm ki ếm có nh ững ph ần trùng nhau. - Ghi nh ớ toàn b ộ nh ững nút đã được m ở r ộng. Nh ững nút này được l ưu trong m ột danh sách g ọi là danh sách nút đóng. Khi chu ẩn b ị m ở r ộng m ột nút, thu ật toán ki ểm tra xem nút đó đã có trong danh sách nút đóng ch ưa, n ếu ch ưa, thu ật toán s ẽ m ở r ộng sau 20
21. Gi ải quy ết v ấn đề bằng tìm ki ếm đó thêm nút vào danh sách nút đóng. Trong tr ường h ợp nút đã có trong danh sách nút đóng r ồi, nút s ẽ không được m ở r ộng l ại l ần th ứ hai. Vi ệc không m ở r ộng nh ững nút đã có trong danh sách nút đóng s ẽ ảnh h ưởng t ới tính t ối ưu c ủa l ời gi ải do thu ật toán ch ỉ xem xét m ột đường đi t ới m ột nút, trong khi đó có th ể là đường đi không t ối ưu. 3.4. Tìm ki ếm sâu d ần (Iterative Depending Search - IDS) Mặc dù có ưu điểm r ất l ớn là không yêu c ầu nhi ều b ộ nh ớ nh ư tìm theo chi ều r ộng, tìm theo chi ều sâu có th ể r ất ch ậm ho ặc b ế t ắc n ếu m ở r ộng nh ững nhánh sâu (vô t ận) không ch ứa l ời gi ải. Để kh ắc ph ục, có th ể s ử d ụng k ỹ thu ật tìm ki ếm v ới độ sâu h ữu h ạn: tìm ki ếm theo ph ươ ng pháp sâu d ần nh ưng không ti ếp t ục phát tri ển m ột nhánh khi đã đạt t ới m ột độ sâu nào đó, thay vào đó, thu ật toán chuy ển sang phát tri ển nhánh khác. Kỹ thu ật này có th ể s ử d ụng trong tr ường h ợp có th ể d ự đoán được độ sâu c ủa l ời gi ải bằng cách dựa trên đặc điểm bài toán cụ th ể. Ch ẳng h ạn, n ếu ta bi ết r ằng đi t ừ Hà n ội vào Vinh không đi qua quá 4 thành ph ố khác thì có th ể dùng 4 làm gi ới h ạn chi ều sâu khi tìm ki ếm đường đi. M ột số bài toán khác c ũng có th ể d ự đoán tr ước gi ới h ạn độ sâu nh ư v ậy. Tuy nhiên, trong tr ường h ợp chung, ta th ường không có tr ước thông tin v ề độ sâu c ủa l ời gi ải. Trong tr ường h ợp nh ư v ậy có th ể s ử d ụng ph ươ ng pháp tìm ki ếm sâu d ần. Th ực ch ất tìm ki ếm sâu d ần là tìm ki ếm v ới độ sâu h ữu h ạn, trong đó gi ới h ạn độ sâu được kh ởi đầ u b ằng m ột giá tr ị nh ỏ, sau đó t ăng d ần cho t ới khi tìm được l ời gi ải. Ph ươ ng pháp: Tìm theo DFS nh ững không bao gi ờ m ở r ộng các node có độ sâu quá m ột gi ới h ạn nào đó. Gi ới h ạn độ sâu s ẽ được t ăng d ần cho đế n khi tìm được l ời gi ải (VD: n ếu gi ới hạn là 2 mà không tìm được thì s ẽ t ăng lên 3). Thu ật toán tìm ki ếm sâu d ần th ể hi ện trên hình 2.6, trong đó tìm ki ếm sâu được l ặp l ại, t ại mỗi b ước l ặp, độ sâu được gi ới h ạn b ởi bi ến C. IDS(Q, S, G, P) Đầu vào: thu ật toán tìm ki ếm Đầu ra: tr ạng thái đích Kh ởi t ạo: O ←S ( O: danh sách các node m ở, b ước này làm nhi ệm v ụ gán S cho O ) C ← 0 (C là gi ới h ạn độ sâu tìm ki ếm) While(O ≠ Ø) do 1. Thực hi ện 3 b ước • Lấy node n đầ u tiên ra kh ỏi O • If n ∈ G, return ( đường đi t ới) n 21
22. Gi ải quy ết v ấn đề bằng tìm ki ếm • If độ sâu (n) nh ỏ h ơn ho ặc b ằng C, then thêm P(n) vào đầu O 2. C++, O ←S Return: Không có l ời gi ải Hình 2.6. Thu ật toán tìm ki ếm sâu d ần Cây tìm ki ếm trong tr ường h ợp tìm sâu d ẫn được minh h ọa trên hình 2.7. Hình 2.7. Cây tìm ki ếm theo thu ật toán tìm ki ếm sâu d ần 22
23. Gi ải quy ết v ấn đề bằng tìm ki ếm Tính ch ất: • Thu ật toán đầ y đủ • Thu ật toán t ối ưu (n ếu có nhi ều l ời gi ải, có th ể tìm ra được l ời gi ải g ần g ốc nh ất) • Yêu c ầu b ộ nh ớ nh ỏ (b*d) do t ại m ỗi b ước l ặp, thu ật toán th ực hi ện tìm ki ếm sâu d ần • Độ ph ức t ạp tính toán O( bd ).Trong tìm ki ếm sâu l ặp, ta ph ải phát tri ển l ặp l ại nhi ều l ần cùng m ột tr ạng thái. Điều đó làm cho ta có c ảm giác r ằng, tìm ki ếm sâu l ặp lãng phí nhi ều th ời gian. Th ực ra th ời gian tiêu t ốn cho phát tri ển l ặp l ại các tr ạng thái là không đáng k ể so v ới th ời gian tìm ki ếm theo b ề r ộng. Th ật v ậy, m ỗi l ần g ọi th ủ t ục tìm ki ếm sâu h ạn ch ế tới m ức d, n ếu cây tìm ki ếm có nhân t ố nhánh là b, thì s ố đỉ nh c ần phát tri ển là: 1 + b + b 2 + + b d Nếu nghi ệm ở độ sâu d, thì trong tìm ki ếm sâu l ặp, ta ph ải g ọi th ủ t ục tìm ki ếm sâu h ạn ch ế v ới độ sâu l ần l ượt là 0, 1, 2, , d. Do đó các đỉnh ở m ức 1 ph ải phát tri ển l ặp d l ần, các đỉnh ở m ức 2 l ặp d-1 l ần, , các đỉ nh ở m ức d l ặp 1 l ần. Nh ư v ậy t ổng s ố đỉ nh c ần phát tri ển trong tìm ki ếm sâu l ặp là: (d+1)1 + db + (d-1)b 2 + + 2b d-1 + 1b d Do đó th ời gian tìm ki ếm sâu d ần là O(b d). 2.3.4. Tìm theo hai h ướng (Bidirectional Search) Trong các ph ươ ng pháp tìm ki ếm ở trên, quá trình tìm ki ếm b ắt đầ u t ừ nút xu ất phát và k ết thúc khi đạt t ới nút đích. Do tính ch ất đố i x ứng c ủa đường đi, quá trình tìm ki ếm c ũng có th ể b ắt đầu t ừ nút đích và tìm t ới nút xu ất phát. Ngoài ra, quá trình tìm ki ếm có th ể xu ất phát đồ ng th ời từ c ả nút xu ất phát và nút đích, xây d ựng đồ ng th ời hai cây tìm ki ếm. Quá trình tìm ki ếm k ết thúc khi hai cây tìm ki ếm có m ột nút chung (hình 2.8). Ph ươ ng pháp: tìm ki ếm b ắt ngu ồn t ừ nút xu ất phát và nút đích. Vì v ậy, s ẽ t ồn t ại hai cây tìm ki ếm, m ột cây có g ốc là nút xu ất phát và m ột cây có g ốc là nút đích. Tìm ki ếm k ết thúc khi có lá c ủa cây này trùng v ới lá c ủa cây kia. Hình 2.8: Cây tìm ki ếm trong tr ường h ợp tìm theo hai h ướng 23
24. Gi ải quy ết v ấn đề bằng tìm ki ếm Chú ý: • Khi tìm theo hai h ướng c ần s ử d ụng tìm theo chi ều r ộng. Vi ệc tìm theo chi ều sâu có th ể không cho phép tìm ra l ời gi ải n ếu hai cây tìm ki ếm phát tri ển theo hai nhánh không g ặp nhau. • Để tìm theo hai h ướng c ần vi ết thêm m ột hàm chuy ển độ ng ng ược là P(x): t ập các node con c ủa x và D(x): t ập các node cha c ủa x. Node càng g ần node xu ất phát càng đươ c coi là t ổ tiên Tính ch ất: • Vi ệc ki ểm tra xem node lá này có trùng v ới node lá kia gây t ốn th ời gian • Độ ph ức t ạp tính toán: do g ặp nhau ở gi ữa nên chi ều sâu m ỗi cây là d/2. Theo tính toán đối v ới tìm theo chi ều r ộng, độ ph ức t ạp tính toán khi đó là O( bd / 2 ). Nh ư v ậy m ặc dù vi ệc ki ểm tra các nút trùng nhau gây t ốn th ời gian nh ưng s ố l ượng nút c ần m ở r ộng c ủa cả hai cây gi ảm đáng k ể so v ới tìm theo m ột chi ều. 6. Bài t ập áp d ụng Tìm chu trình Hamilton xu ất phát t ừ A 24
25. Gi ải quy ết v ấn đề bằng tìm ki ếm 2.4. TÌM KI ẾM CÓ THÔNG TIN (INFORMED SEARCH) Đối v ới tìm ki ếm mù, vi ệc m ở r ộng các nút thuân theo m ột quy lu ật và không d ựa vào thông tin h ỗ tr ợ c ủa bài toán. Kết qu ả c ủa vi ệc tìm ki ếm nh ư v ậy là vi ệc di chuy ển trong không gian tìm ki ếm không có đị nh h ướng, d ẫn t ới ph ải xem xét nhi ều tr ạng thái. Đố i v ới nh ững bài toán th ực t ế có không gian tr ạng thái l ớn, tìm ki ếm mù th ường không th ực t ế do có độ ph ức t ạp tính toán và yêu c ầu b ộ nh ớ l ớn. Để gi ải quy ết v ấn đề trên, chi ến l ược tìm ki ếm có thông tin s ử d ụng thêm nh ững thông tin ph ụ t ừ bài toán để đị nh h ướng tìm ki ếm, c ụ th ể là l ựa ch ọn th ứ t ự m ỏ r ộng nút theo h ướng mau dẫn t ới đích h ơn. Nguyên t ắc chung c ủa tìm ki ếm có thông tin là s ử d ụng m ột hàm f (n) để đánh giá độ “t ốt” ti ềm n ăng c ủa nút n, t ừ đó ch ọn nút n có hàm f tốt nh ất để m ở r ộng tr ước. Trên th ực t ế, vi ệc xây d ựng hàm f (n) ph ản ánh chính xác độ t ốt c ủa nút th ường không th ực hi ện được, thay vào đó ta s ử d ụng các giá tr ị ước l ượng cho f (n). Trong ph ần này ta s ẽ xem xét hai chi ến l ược tìm ki ếm có thông tin, đó là tìm ki ếm tham lam và tìm ki ếm A* . 2.4.1. Tìm ki ếm tham lam (Greedy Search) Ph ươ ng pháp: xem xét m ở r ộng nút có giá thành đường đi t ới đích nh ỏ nh ất tr ước. Trong ph ươ ng pháp này, để đánh giá độ t ốt c ủa m ột nút, ta s ử d ụng hàm đo giá thành đường đi t ừ nút đó t ới đích. Tuy nhiên, do không bi ết được chính xác giá thành đường đi t ừ m ột nút t ới đích, ta ch ỉ có th ể ước l ượng giá tr ị này. Hàm ước l ượng độ t ốt, hay giá thành đường đi t ừ một nút n t ới địch g ọi là hàm heuristic và ký hi ệu h(n). Nh ư v ậy, đố i v ới thu ật toán tham lam, ta có f(n) = h(n). Do hàm h(n) ch ỉ là hàm ước l ượng giá thành đường đi t ới đích nên có th ể nói r ằng tìm ki ếm tham lam m ở r ộng nút trông có v ẻ g ần đích nh ất tr ước các nút khác. Thu ật toán được g ọi là “tham lam” do thu ật toán ch ỉ quan tâm t ới vi ệc l ựa ch ọn nút trông có v ẻ t ốt nh ất ở m ỗi b ước mà không quan tâm t ới vi ệc trong t ươ ng lai vi ệc dùng nút đó có th ể không ph ải là t ối ưu. Điều ki ện c ủa hàm h(n): h(n) ≥0 Nh ận xét: tìm ki ếm heuristic t ươ ng t ự DFS nh ưng cho phép quay lui khi g ặp b ế t ắc Ví d ụ hàm heuristic h(n). Khi tìm đường trên b ản đồ , hàm heuristic cho m ột thành ph ố có th ể tính b ằng kho ảng cách theo đường chim bay gi ữa thành ph ố đó v ới thành ph ố đích c ần đế n. Đặc điểm: • Không có tính đầy đủ do có kh ả n ăng tạo thành vòng l ặp ở m ột s ố nút. • Độ ph ức t ạp v ề th ời gian: O( bm ) (thu ật toán nhanh h ơn BFS, và có th ể c ũng nhanh h ơn DFS n ếu t ồn t ại heuristic t ốt). Tuy nhiên trong tr ường h ợp heuristic không t ốt thì thu ật toán s ẽ đi sai h ướng và do v ậy g ần gi ống v ới tìm sâu. 25
26. Gi ải quy ết v ấn đề bằng tìm ki ếm • Độ ph ức t ạp v ề không gian l ưu tr ữ: O( bm ) (l ưu t ất c ả các nút trong b ộ nh ớ) • Thu ật toán không t ối ưu 2.4.2. Thu ật toán A* Một trong nh ững nh ược điểm c ủa tìm ki ếm tham lam là không cho l ời gi ải ng ắn nh ất. Lý do tìm ki ếm tham lam không đả m b ảo tìm ra đường đi ng ắn nh ất là do thu ật toán ch ỉ quan tâm t ới kho ảng cách ước l ượng t ừ m ột nút t ới đích mà không quan tâm t ới đường đi t ừ nút xu ất phát t ới nút đó. Trong tr ường h ợp kho ảng cách từ nút xu ất phát t ới nút đang xét l ớn s ẽ làm t ổng độ dài đường đi t ừ xu ất phát t ới đích qua nút hi ện th ời l ớn lên. Để kh ắc ph ục nh ược điểm này, thu ật toán A* s ử d ụng hàm đánh giá f(n) v ới hai thành ph ần, thành ph ần th ứ nh ất là đường đi t ừ nút đang xét t ới nút xu ất phát, thành ph ần th ứ hai là kho ảng cách ước l ượng t ới đích. Ph ươ ng pháp: kh ắc ph ục nh ược điểm c ủa thu ật toán tham lam, thu ật toán A* s ẽ tính f(n) = g(n) + h(n). Trong đó: • g(n) là giá thành đường đi t ừ nút xu ất phát đế n nút n • h(n) là giá thành ước lượng đường đi t ừ nút n đế n nút đích, h(n) là hàm heuristic. Thu ật toán A* yêu c ầu hàm h(n) là hàm ch ấp nh ận được (admissible). Định ngh ĩa: Hàm h(n) được g ọi là ch ấp nh ận được n ếu h(n) không l ớn h ơn kho ảng cách th ực t ế từ n t ới nút đích. Thu ật toán: A*( Q, S, G, P, c, h) • Đầu vào: bài toán tìm ki ếm, hàm heuristic h • Đầu ra: đường đi ng ắn nh ất từ nút xu ất phát đế n nút đích • Kh ởi t ạo: t ập các nút biên (nút m ở) O ← S While( O không r ỗng) do 1. Lấy nút n có f(n) nh ỏ nh ất ra kh ỏi O 2. Nếu n thu ộc G, return( đường đi t ới n) 3. Với m ọi m ∈ P(n) i. g(m) = g(n) + c(m, n) ii. f(m) = g(m) + h(m) iii. Thêm m vào O cùng giá tr ị f(m) Return: không tìm được đường đi Hình 2.9. Thu ật toán A* 26
27. Gi ải quy ết v ấn đề bằng tìm ki ếm Nh ận xét: • Thu ật toán cho k ết qu ả t ối ưu n ếu hàm heuristic h là hàm ch ấp nh ận được. • Thu ật toán đầ y đủ tr ừ tr ường h ợp có vô s ố các node v ới hàm f có giá tr ị r ất nh ỏ n ằm gi ữa node xu ất phát và node đích. • Th ời gian: O( bm ) • Trong t ất c ả các thu ật toán tìm ki ếm t ối ưu thì thu ật toán A* hi ệu qu ả nh ất v ới độ ph ức tạp c ủa thu ật toán là nh ỏ nh ất 2.4.3. Các hàm heuristic Các hàm heuristic h(n) được xây d ựng tùy thu ộc vào bài toán c ụ th ể. Cùng m ột lo ại bài toán chúng ta có th ể có r ất nhi ều hàm heuristic khác nhau. Ch ất l ượng hàm heuristic ảnh h ưởng rất nhi ều đế n quá trình tìm ki ếm. Hàm heuristic h(n) được g ọi là ch ấp nh ận được khi: h(n) ≤ h*(n) trong đó h*(n) là giá thành đường đi th ực t ế t ừ n đế n node đích. Lưu ý r ằng hàm h(n)=0 v ới mọi n, là hàm ch ấp nh ận được. Ví d ụ: Đường chim bay nh ư nh ắc t ới ở trên là m ột ví d ụ c ủa hàm heuristic ch ấp nh ận được. Ngoài ra, ta s ẽ xem xét m ột s ố hàm heuristic cho bài toán trò đố 8 ô. 3 1 6 1 2 5 4 3 4 5 2 7 8 6 7 8 Ta có th ể s ử d ụng hai hàm heuristic sau. - h1( n ) : s ố ô đặ t sai ch ỗ. Ch ẳng h ạn n ếu hình bên ph ải là tr ạng thái đích và hình bên trái là tr ạng thái u thì tr ạng thái bên trái có h1(u) = 5 do có 5 ô là các ô 3, 6, 4, 5, 2 n ằm sai vị trí. Có th ể nh ận th ấy h1 là hàm ch ấp nh ận được do mu ốn di chuy ển t ừ tr ạng thái bên trái sang tr ạng thái đích ta ph ải chuy ển v ị trí t ất c ả nh ững ô đứ ng sai, trong khi để di chuy ển m ỗi ô sai, ta c ần ít nh ất m ột n ước đi. Nh ư v ậy độ dài đường đi luôn l ớn h ơn ho ặc b ằng h1. - h2 ( n ) : tổng kho ảng cách Manhattan gi ữa v ị trí hi ện th ời c ủa m ỗi ô t ới v ị trí đúng c ủa ô đó. Kho ảng cách Manhattan được tính b ằng s ố ít nh ất các d ịch chuy ển theo hàng ho ặc 27
28. Gi ải quy ết v ấn đề bằng tìm ki ếm cột để đưa m ột quân t ới v ị trí c ủa nó trong tr ạng thái đích. Ví d ụ, để đưa quân 2 t ới v ị trí đích ta c ần 4 d ịch chuy ển và do v ậy kho ảng cách Manhattan c ủa 2 t ới đích là 4. Giá tr ị h2 của tr ạng thái u trên hình bên trái s ẽ b ằng h2(u) = 1 + 4 + 1 + 2 + 1. Hàm h2 cũng là hàm ch ấp nh ận được. Th ật v ậy, để di chuy ển m ột ô t ới v ị trí đích, ta c ần ít nh ất s ố n ước đi b ằng kho ảng cách Manhattan t ừ ô đó t ới đích. Nh ư v ậy, số n ước để di chuy ển toàn b ộ các ô đứng sai s ẽ l ớn h ơn ho ặc b ằng t ổng kho ảng cách Manhattan nh ư cách tính h2. Hàm heuristic tr ội Ví d ụ trên cho th ấy, v ới cùng m ột bài toán, ta có th ể xây d ựng đồ ng th ời nhi ều hàm heuristic ch ấp nh ận được. Vấn đề đặ t ra khi đó là nên dùng hàm nào trong thu ật toán tìm ki ếm, hàm được ch ọn ph ải là hàm t ốt h ơn, t ức là hàm nhanh dẫn t ới k ết qu ả hơn. Gi ả s ử có hai hàm heuristic ch ấp nh ận được h1(n) và h2(n). Nếu h1(n) ≤ h2(n) với m ọi n thì ta nói r ằng h2 ( n ) trội h ơn so v ới h1( n ) . Rõ ràng hàm h2 ( n ) mang nhi ều thông tin h ơn và do v ậy là hàm t ốt h ơn do d ẫn t ới kết qu ả nhanh h ơn. Trong tr ường h ợp trong hai hàm h1(n) và h2(n) không có hàm tr ội h ơn thì ta có th ể t ạo ra hàm h’( n) = max ( h1(n) , h2(n)) v ới m ọi n. Rõ ràng, h’( n) là hàm tr ội h ơn hai hàm ban đầu. Cách xây d ựng hàm heuristic Vi ệc l ựa ch ọn hàm heuristic ph ụ thu ộc vào bài toán c ụ th ể. Nguyên t ắc chung để xây d ựng hàm heuristic cho m ột bài toán là nới l ỏng các ràng buộc c ủa bài toán đó. Ví d ụ, đối v ới hàm h1( n ) trong trò đố 8 ô, ta đã bỏ ràng bu ộc về vi ệc các ô ph ải di chuy ển t ừng b ước để đế n được v ị trí đích. Hay đối v ới heuristic đường chim bay, ta đã n ới r ỏng ràng bu ộc v ề vi ệc di chuy ển trên đường b ộ và gi ả s ử có th ể di chuy ển th ẳng t ừ m ột điểm t ới đích. 2.4.4. Thu ật toán IDA* (thu ật toán A* sâu d ần) Thu ật toán A* có nh ững ưu điểm quan tr ọng nh ư tính t ối ưu và tính đầy đủ . Tuy nhiên, n ếu hàm heuristic không t ốt, thu ật toán s ẽ ph ải xem xét nhi ều tr ạng thái và có yêu c ầu b ộ nh ớ trong tr ường h ợp x ấu nh ất là O( bm). Yêu c ầu b ộ nh ớ theo hàm m ũ nh ư v ậy làm gi ảm kh ả n ăng s ử d ụng A*. Để gi ải quy ết v ấn đề này có th ể s ử d ụng phiên b ản c ủa A* được g ọi là A* sâu dần (Iterative Deepening A*) có yêu c ầu b ộ nh ớ t ỷ l ệ tuy ến tính v ới độ sâu. Ph ươ ng pháp: Nguyên tắc c ủa A* sâu d ần là l ặp l ại vi ệc tìm ki ếm theo chi ều sâu trên các cây tìm ki ếm con có giá tr ị hàm f(n) không l ớn h ơn các ng ưỡng 0, α, 2 α, 3 α, .v.v Cụ th ể: 1. Tìm ki ếm sâu d ần (DFS), không m ở r ộng nút có hàm f > 0, n ếu tìm được đích thì d ứng l ại. 2. Tìm ki ếm sâu d ần (DFS), không m ở r ộng nút có hàm f > α, n ếu tìm được đích thì d ứng l ại. 2. Tìm ki ếm sâu d ần , không m ở r ộng nút có hàm f > 2 α, n ếu tìm được đích thì d ứng l ại. 28
29. Gi ải quy ết v ấn đề bằng tìm ki ếm Ở đây, α là giá tr ị được thêm vào ng ưỡng sau m ỗi vòng l ặp. Để m ỗi vòng l ặp có th ể xét thêm các nút m ới α cần có giá tr ị l ớn h ơn ho ặc b ằng giá thành nh ỏ nh ất để di chuy ển gi ữa hai tr ạng thái trong không gian tìm ki ếm. Ở đây c ần l ưu ý cách ch ọn α. N ếu α nh ỏ, sau m ỗi l ần t ăng ng ưỡng, cây tìm ki ếm m ới s ẽ thêm được ít nút do v ới cây tìm ki ếm c ũ và do v ậy c ần l ặp l ại quá trình tìm sâu nhi ều l ần, d ẫn t ới t ăng độ ph ức t ạp tính toán. Ví d ụ, trong tr ường h ợp đặ c bi ệt, khi giá tr ị c ủa f(n) trên m ọi nút đề u khác nhau, m ỗi b ước l ặp s ẽ ch ỉ xem xét thêm được m ột nút so với b ước tr ước. Khi đó, n ếu A* c ần m ở r ộng N nút, thì A* sâu d ần s ẽ ph ải m ở r ộng 1+2+ +N = O(N 2). Gi ải pháp cho v ấn đề độ ph ức t ạp tính toán là s ử d ụng m ức độ t ăng ng ưỡng β > α, sao cho tại m ỗi b ước l ặp s ẽ m ở r ộng cây tìm ki ếm thêm m ột s ố nút m ới. Giá tr ị β nh ư v ậy cho phép gi ảm th ời gian tìm ki ếm, tuy nhiên ch ỉ tr ả l ại l ời gi ải β-tối ưu trong tr ường h ợp x ấu nh ất, t ức là n ếu thu ật toán tìm được l ời gi ải m* thì ta có g(m*) < g* + β. Thu ật toán A* sâu d ần chi ti ết được th ể hi ện trên hình d ưới đây: Thu ật toán: A*(Q, S, G, P, c, h) • Đầu vào: bài toán tìm ki ếm, hàm heuristic h • Đầu ra: đường đi ng ắn nh ất t ừ nút xu ất phát đế n nút đích • Kh ởi t ạo: danh sách các nút biên (nút m ở) O ← S giá tr ị i = 0 là ng ưỡng cho hàm f While(1) do 1. while (O không r ỗng) do a) Lấy nút n từ đầ u O b) Nếu n thu ộc G, return( đường đi t ới n) c) Với m ọi m ∈ P(n) i. g(m) = g(n) + c(m, n) ii. f(m) = g(m) + h(m) iii. If f(m) ≤ i then Thêm m vào đầu O 2. i ← i + β, O ← S Hình 2.10. Thu ật toán A* sâu d ần Tính ch ất: • Thu ật toán đầ y đủ và β-tối ưu 29
30. Gi ải quy ết v ấn đề bằng tìm ki ếm • Yêu c ầu b ộ nh ớ tuy ến tính (ch ỉ nh ớ nhánh, t ươ ng đươ ng sâu d ần) • Độ ph ức t ạp tính toán l ớn h ơn c ủa thu ật toán A* • Không ph ụ thu ộc vào h(n) (sau m ỗi l ần t ăng l ại làm l ại t ừ đầ u → không s ử d ụng h(n) để thu h ẹp nhánh c ần tìm). 2.5. TÌM KI ẾM C ỤC B Ộ Các thu ật toán tìm ki ếm ở trên đều d ựa trên vi ệc kh ảo sát không gian tìm ki ếm m ột cách h ệ th ống b ằng cách ghi l ại nh ững đường đi đã qua cùng v ới thông tin v ề ph ươ ng án đã ho ặc ch ưa được xem xét t ại m ỗi tr ạng thái trên đường đi. Vấn đề c ủa thu ật toán nh ư v ậy là vi ệc sử d ụng đường đi để kh ảo sát không gian tìm ki ếm m ột cách h ệ th ống làm t ăng s ố l ượng tr ạng thái c ần xem xét đồng th ời đòi h ỏi ghi nh ớ nhi ều tr ạng thái và do v ậy không thích h ợp v ới bài toán có không gian tr ạng thái l ớn Trong ph ần này ta s ẽ xem xét các thu ật toán tìm ki ếm c ục b ộ (local search), còn được g ọi là tìm ki ếm cải thi ện d ần (iterative improvement). Tìm ki ếm c ục b ộ th ường được s ử d ụng cho nh ững bài toán t ối ưu hóa t ổ h ợp ho ặc t ối ưu hóa r ời r ạc, t ức là nh ững bài toán trong đó c ần tìm tr ạng thái t ối ưu ho ặc t ổ h ợp t ối ưu trong không gian r ời r ạc các tr ạng thái, và không quan tâm t ới đường đi d ẫn t ới tr ạng thái đó. Bài toán t ối ưu hóa t ổ h ợp (t ối ưu hóa r ời r ạc) có nh ững đặ c điểm sau. • Tìm tr ạng thái t ối ưu c ực đạ i hóa ho ặc c ực ti ểu hóa hàm m ục tiêu. Không quan tâm t ới đường đi. • Không gian tr ạng thái rất lớn. • Không th ể s ử d ụng các ph ươ ng pháp tìm ki ếm tr ước để xem xét t ất c ả không gian tr ạng thái • Thu ật toán cho phép tìm l ời gi ải t ốt nh ất v ới độ ph ức t ạp tính toán nh ỏ. Thu ật toán c ũng ch ấp nh ận l ời gi ải t ươ ng đối t ốt. Ví d ụ: tối ưu hóa t ổ h ợp là l ớp bài toán có nhi ều ứng d ụng trên th ực t ế. Có th ể k ể ra m ột s ố ví d ụ sau: bài toán l ập l ịch, b ảng bi ểu, thi ết k ế transitor, tri ệu con h ậu, Tìm ki ếm c ục b ộ được thi ết k ế cho bài toán tìm ki ếm với không gian tr ạng thái r ất l ớn và cho phép tìm ki ếm tr ạng thái t ươ ng đối t ốt v ới th ời gian tìm ki ếm ch ấp nh ận được. Ý t ưởng: nguyên t ắc chung c ủa tìm ki ếm c ục b ộ • Ch ỉ quan tâm đế n tr ạng thái đích, không quan tâm đế n đường đi. • Mỗi tr ạng thái t ươ ng ứng v ới m ột l ời gi ải (ch ưa t ối ưu) → c ải thi ện d ần b ằng cách ch ỉ quan tâm t ới m ột tr ạng thái hi ện th ời, sau đó xem xét để để chuy ển sang tr ạng thái hàm xóm c ủa tr ạng thái hi ện th ời (th ường là tr ạng thái có hàm m ục tiêu t ốt h ơn). 30
31. Gi ải quy ết v ấn đề bằng tìm ki ếm • Thay đổi tr ạng thái b ằng cách th ực hi ện các chuy ển độ ng (tr ạng thái nh ận được t ừ tr ạng thái n b ằng cách th ực hi ện các chuy ển độ ng được g ọi là hàng xóm c ủa n). Do tìm ki ếm c ục b ộ ch ỉ quan tâm t ới tr ạng thái hi ện th ời và hàng xóm nên c ần ít b ộ nh ớ hơn nhi ều so v ới các ph ươ ng pháp tìm ki ếm h ệ th ống ở trên. Tìm ki ếm c ục b ộ th ường cho phép tìm được l ời gi ải ch ấp nh ận được k ể c ả khi bài toán l ớn đế n m ức không dùng được nh ững ph ươ ng pháp tìm ki ếm h ệ th ống. Phát bi ểu bài toán: Bài toán tìm ki ếm c ục b ộ được cho b ởi nh ững thành ph ần sau: • Không gian tr ạng thái X • Tập chuy ển độ ng để sinh ra hàng xóm • Hàm m ục tiêu Obj: X → R • Yêu c ầu: Tìm tr ạng thái X* sao cho Obj(X*) là min ho ặc max. Có th ể minh h ọa bài toán tìm ki ếm c ục b ộ bằng cách xem xét hình 2.11. Tr ục hoành trên hình v ẽ th ể hi ện không gian các tr ạng thái ( để cho đơn gi ản, không gian tr ạng thái ở đây được th ể hi ện trong không gian m ột chi ều d ưới d ạng các điểm trên tr ục hoành), tr ục tung là độ l ớn c ủa hàm m ục tiêu. Yêu c ầu bài toán t ối ưu hóa t ổ h ợp là tìm được tr ạng thái ( điểm trên tr ục hoành) có hàm mục tiêu l ớn nh ất. L ưu ý, hình v ẽ minh h ọa tr ường h ợp cần tìm tr ạng thái v ới hàm m ục tiêu lớn nh ất, tuy nhiên trong bài toán khác có th ể yêu c ầu tìm tr ạng thái v ới hàm m ục tiêu nh ỏ nh ất. Hình 2.11. Bài toán tìm ki ếm c ục b ộ v ới không gian tr ạng thái và hàm m ục tiêu 2.5.1. Thu ật toán leo đồ i (Hill climbing) Leo đồi là tên chung để ch ỉ một h ọ các thu ật toán. Thu ật toán th ực hi ện b ằng cách t ạo ra hàng xóm cho tr ạng thái hi ện th ời và di chuy ển sang hàng xóm có hàm m ục tiêu t ốt h ơn, t ức là di chuy ển lên cao đối v ới tr ường h ợp c ần c ực đạ i hóa hàm m ục tiêu. Thu ật toán d ừng l ại khi đạ t t ới 31
32. Gi ải quy ết v ấn đề bằng tìm ki ếm một đỉ nh c ủa đồ th ị hàm m ục tiêu, t ươ ng ứng v ới tr ạng thái không có hàng xóm nào t ốt h ơn. Đỉnh này có th ể là đỉnh cao nh ất, ho ặc c ũng là nh ững đỉ nh th ấp h ơn (hình 2.11). Trong tr ường hợp th ứ nh ất, thu ật toán tìm được giá tr ị c ực tr ị, trong tr ường h ợp th ứ hai thu ật toán ch ỉ tìm được c ực tr ị địa ph ươ ng. Thu ật toán leo đồ i không l ưu l ại nh ững tr ạng thái đã qua, đồng th ời không nhìn xa hơn hàng xóm c ủa tr ạng thái hi ện th ời. a) Di chuy ển sang tr ạng thái t ốt nh ất Có nhi ều phiên b ản khác nhau c ủa thu ật toán leo đồ i. M ột trong nh ững phiên b ản thông dụng nh ất có tên là leo đồi di chuy ển sang tr ạng thái t ốt nh ất (best-improvement hill climbing). Phiên b ản này c ủa leo đồ i l ựa ch ọn trong s ố hàng xóm hi ện th ời hàng xóm có hàm m ục tiêu t ốt nh ất. N ếu hàng xóm đó t ốt h ơn tr ạng thái hi ện th ời thì di chuy ển sang hàm xóm đó. N ếu ng ược lại thì k ết thúc và tr ả v ề tr ạng thái hi ện th ời. Thu ật toán đầ y đủ được th ể hi ện trên hình 2.12. Đầu vào: bài toán t ối ưu tổ h ợp Đầu ra: tr ạng thái v ới hàm m ục tiêu l ớn nh ất (ho ặc c ực đạ i đị a ph ươ ng) 1. Ch ọn ng ẫu nhiên tr ạng thái x 2. Gọi Y là t ập các tr ạng thái hàng xóm c ủa x 3. Nếu ∀yi ∈Y: Obj ( yi ) < Obj ( x) thì Kết thúc và tr ả l ại x là k ết qu ả 1. x ← yi , trong đó i = argmax i (Obj ( yi )) 2. Go to 2 Hình 2.12. Thu ật toán leo đồ i di chuy ển sang tr ạng thái t ốt nh ất Đặc điểm của leo đồ i - Đơ n gi ản,d ễ l ập trình, không t ốn b ộ nh ớ do không ph ải l ưu l ại b ất k ỳ th ứ gì, ch ỉ l ưu lại tr ạng thái t ạm th ời và các hàng xóm. - Dễ b ị l ời gi ải t ối ưu c ục b ộ (c ực tr ị đị a ph ươ ng) tươ ng ứng v ới đỉ nh các “ đồ i” th ấp trong hình 2.11. Để kh ắc ph ục ph ần nào v ấn đề này, thu ật toán được th ực hi ện nhi ều lần, m ỗi l ần s ử d ụng m ột tr ạng thái xu ất phát sinh ng ẫu nhiên khác v ới tr ạng thái xu ất phát trong nh ững l ần tr ước đó. Khi thi ết k ế thu ật toán leo đồ i, việc l ựa ch ọn chuy ển độ ng r ất quan tr ọng. N ếu nhi ều chuy ển độ ng s ẽ sinh ra nhi ều hàng xóm, do v ậy vi ệc ch ọn ra hàng xóm t ốt nh ất đòi h ỏi nhi ều th ời gian do ph ải tính hàm m ục tiêu cho t ất c ả hàng xóm. Ng ược l ại, n ếu sinh ra tập hàng xóm nh ỏ sẽ dễ d ẫn t ới c ực tr ị đị a ph ươ ng do không v ượt qua được nh ững “h ố” nh ỏ trên đường đi. 32
33. Gi ải quy ết v ấn đề bằng tìm ki ếm b) Leo đồi ng ẫu nhiên Leo đồi ng ẫu nhiên (stochastic hill climbing) là m ột phiên b ản khác c ủa leo đồ i. Thay vì tìm ra hàng xóm t ốt nh ất, phiên b ản này l ựa ch ọn ng ẫu nhiên m ột hàng xóm. N ếu hàng xóm đó tốt h ơn tr ạng thái hi ện th ời, hàng xóm đó s ẽ được ch ọn làm tr ạng thái hi ện th ời và thu ật toán l ặp lại. Ng ược l ại, n ếu hàng xóm được ch ọn không t ốt h ơn, thu ật toán s ẽ ch ọn ng ẫu nhiên m ột hàng xóm khác và so sánh. Thu ật toán k ết thúc và tr ả l ại tr ạng thái hi ện th ời khi đã h ết “kiên nh ẫn”. Thông th ường, kiên nh ẫn được cho b ằng s ố l ượng t ối đa hàng xóm mà thu ật toán xem xét trong mỗi b ước l ặp ho ặc trong toàn b ộ thu ật toán. Thu ật toán leo đồ i ng ẫu nhiên được th ể hiện trên hình 2.13. Đầu vào: bài toán t ối ưu t ổ h ợp Đầu ra: tr ạng thái v ới hàm m ục tiêu l ớn nh ất (ho ặc c ực đạ i đị a ph ươ ng) 1. Ch ọn ng ẫu nhiên tr ạng thái x 2. Gọi Y là t ập các tr ạng thái hàng xóm c ủa x 3. Ch ọn ng ẫu nhiên yi∈Y 4. Nếu Obj ( yi ) > Obj ( x) thì x ← yi 5. Go to 2 n ếu ch ưa h ết kiên nh ẫn Hình 2.13. Thu ật toán leo đồ i ng ẫu nhiên Các nghiên c ứu cho th ấy, trong m ột s ố tr ường h ợp, leo đồ i ng ẫu nhiên cho k ết qu ả nhanh hơn và có th ể tránh được m ột s ố c ực tr ị đị a ph ươ ng. 2.5.2. Thu ật toán tôi thép (Simulated Annealing) Một v ấn đề l ớn với leo đồ i là thu ật toán không có kh ả n ăng “ đi xu ống” và do v ậy không thoát kh ỏi được cực tr ị đị a ph ươ ng khi đã r ơi vào. Ng ược l ại, cách di chuy ển hoàn toàn ng ẫu nhiên (random walk) có th ể kh ảo sát toàn b ộ không gian tr ạng thái nh ưng không hi ệu qu ả. Thu ật toán tôi thép (simulated annealing) là m ột ph ươ ng pháp tìm ki ếm c ục b ộ cho phép gi ải quy ết ph ần nào v ấn đề cực tr ị đị a ph ươ ng m ột cách tươ ng đối hi ệu qu ả. Có th ể coi tôi thép là phiên b ản c ủa thu ật toán leo đồ i ng ẫu nhiên, trong đó thu ật toán ch ấp nh ận cả nh ững tr ạng thái kém h ơn tr ạng thái hi ện th ời với m ột xác su ất p nào đó. Cụ th ể là khi lựa ch ọn ng ẫu nhiên m ột hàng xóm, n ếu hàng xóm đó kém h ơn tr ạng thái hi ện th ời, thu ật toán có th ể quy ết đị nh di chuy ển sang đó v ới m ột xác su ất p. 33
34. Gi ải quy ết v ấn đề bằng tìm ki ếm Vấn đề quan tr ọng đố i v ới thu ật toán là l ựa ch ọn xác su ất p th ế nào. Nguyên t ắc chung là không ch ọn p cố đị nh, giá tr ị p được xác đị nh d ựa trên hai y ếu t ố sau. - Nếu tr ạng thái m ới kém h ơn nhi ều so v ới tr ạng thái hi ện th ời thì p ph ải gi ảm đi. Có ngh ĩa là xác su ất ch ấp nh ận tr ạng thái t ỷ l ệ ngh ịch v ới độ kém c ủa tr ạng thái đó. G ọi ∆(x,y) = Obj(x) – Obj(y) trong đó x là tr ạng thái hi ện th ời, ta c ần ch ọn p t ỷ l ệ ngh ịch với ∆(x,y). - Theo th ời gian, giá tr ị c ủa p ph ải gi ảm d ần. Ý ngh ĩa c ủa vi ệc gi ảm p theo th ời gian là do khi m ới b ắt đầ u, thu ật toán ch ưa ở vào vùng tr ạng thái t ốt và do v ậy ch ấp nh ận thay đổi l ớn. Theo th ời gian, thu ật toán s ẽ chuy ển sang vùng tr ạng thái t ốt h ơn và do vậy c ần h ạn ch ế thay đổ i. Thu ật toán tôi thép được th ể hi ện trên hình 2.14. SA(X, Obj, N, m, x, C) //Obj càng nh ỏ càng t ốt Đầu vào: số b ước l ặp m tr ạng thái b ắt đầ u x (ch ọn ng ẫu nhiên) sơ đồ làm l ạnh C Đầu ra: tr ạng thái t ốt nh ất x* Kh ởi t ạo: x* = x For i = 1 to m 1. ch ọn ng ẫu nhiên y ∈ N(x) a) tính ∆(x,y) = Obj(y) – Obj(x) b) if ∆(x,y) < 0 then p = 1 c) else p = e - ∆(x,y)/T d) if rand[0,1] < p then x ← y if Obj(x) < Obj(x*) then x* ← x 2. gi ảm T theo s ơ đồ C return x* //x* là tr ạng thái t ốt nh ất trong s ố nh ững tr ạng thái đã xem xét Hình 2.14. Thu ật toán tôi thép Thu ật toán tôi thép v ừa trình bày d ựa trên m ột hi ện t ượng c ơ h ọc là quá trình làm l ạnh kim lo ại để t ạo ra c ấu trúc tinh th ể b ền v ững. Hàm m ục tiêu khi đó được đo b ằng độ v ững ch ắc c ủa 34
35. Gi ải quy ết v ấn đề bằng tìm ki ếm cấu trúc tinh th ể. Khi còn nóng, m ức n ăng l ượng trong kim lo ại cao, các nguyên t ử kim lo ại có kh ả n ăng di chuy ển linh độ ng h ơn. Khi nhi ệt độ gi ảm xu ống, tinh th ể d ần chuy ển t ới tr ạng thái ổn định và t ạo ra m ạng tinh th ể. B ằng cách thay đổ i nhi ệt độ h ợp lý, có th ể t ạo ra nh ững m ạng tinh th ể r ất r ắn ch ắc. Chính vì s ự t ươ ng t ự v ới cách tôi kim lo ại nh ư v ậy nên trong thu ật toán, xác su ất p gi ảm theo th ời gian d ựa vào m ột công th ức g ọi là s ơ đồ làm l ạnh C. Có nhi ều d ạng s ơ đồ làm l ạnh khác nhau. Sau đây là ví d ụ m ột s ơ đồ làm l ạnh. Sơ đồ làm l ạnh C: t* k Tt+1= T 0 *α Trong đó: T0 > 0, α thu ộc (0,1), 1 < k < m t càng t ăng → α càng nh ỏ → T càng nh ỏ Khi T → ∞: p = 1 v ới m ọi ∆(x, y) → t ươ ng đươ ng v ới chuy ển độ ng ng ẫu nhiên Khi T → 0: p = 0 v ới m ọi ∆(x, y) → đưa v ề tr ường h ợp leo đồ i ng ẫu nhiên Vi ệc l ựa ch ọn các tham s ố cho s ơ đồ làm l ạnh th ường được th ực hi ện b ằng cách th ực nghi ệm v ới t ừng bài toán c ụ th ể. Thu ật toán tôi thép được dùng nhi ều trong vi ệc thi ết k ế vi m ạch có độ tích h ợp l ớn c ũng nh ư gi ải quy ết nh ững bài toán t ối ưu hóa t ổ h ợp có kích th ước l ớn trên th ực t ế. 2.5.3. Một s ố thu ật toán tìm ki ếm c ục b ộ khác Ngoài ph ươ ng pháp leo đồi và tôi thép, nhi ều thu ật toán tìm ki ếm c ục b ộ khác được đề xu ất và s ử d ụng trong th ực t ế, trong đó ph ải k ể đế n nh ững thu ật toán sau: Tabu search . Thu ật toán lưu m ột danh sách nh ững tr ạng thái đã đi qua g ọi là tabu list (t ạm dịch là danh sách c ấm). Khi duy ệt t ập hàng xóm, nh ững tr ạng thái thu ộc danh sách này s ẽ b ị lo ại không được xem xét. Gi ải thu ật di truy ền (genetic algorithm). Gi ải thu ật di truy ền có th ể xem nh ư m ột phiên bản leo đồ i ng ẫu nhiên được th ực hi ện song song. Thu ật toán mã hóa các tr ạng thái d ưới d ạng các chu ỗi gen, sau đó th ực hi ện ba thao tác bi ến đổ i chính là: ch ọn l ọc, lai gi ống và đột bi ến để sinh ra trạng thái m ới. Quá trình đi t ới tr ạng thái t ốt được th ực hi ện d ựa trên s ự t ươ ng t ự v ới quá trình ch ọn l ọc cá th ể t ốt theo thuy ết ti ến hóa c ủa Đác Uyn. 35
36. CH ƯƠ NG 3: BI ỂU DI ỄN TRI TH ỨC VÀ SUY DI ỄN LOGIC 3.1. SỰ C ẦN THI ẾT S Ử D ỤNG TRI TH ỨC TRONG GI ẢI QUY ẾT V ẤN ĐỀ Sự c ần thiết c ủa tri th ức và suy di ễn Một yêu c ầu quan tr ọng đố i v ới h ệ th ống thông minh là ph ải có kh ả n ăng s ử d ụng tri th ức và suy di ễn. R ất khó để đạ t được nh ững hành vi thông minh và m ềm d ẻo mà không có tri th ức v ề th ế gi ới xung quanh và kh ả n ăng suy di ễn v ới tri th ức đó. S ử d ụng tri th ức và suy di ễn đem l ại nh ững l ợi ích sau. - Hệ th ống d ựa trên tri th ức có tính m ềm d ẻo cao. Vi ệc k ết h ợp tri th ức và suy di ễn cho phép t ạo ra tri th ức khác, giúp h ệ th ống đạ t được nh ững m ục tiêu khác nhau, đồng th ời có kh ả n ăng suy di ễn v ề b ản thân m ục tiêu. Ch ươ ng tr ước đã đề c ập t ới kỹ thu ật gi ải quy ết v ấn đề b ằng cách tìm ki ếm. Nh ững h ệ th ống tìm ki ếm ch ỉ s ử dụng tri th ức h ạn ch ế, th ể hi ện trong vi ệc bi ểu di ễn bài toán và các heuristic. H ệ th ống nh ư v ậy không có kh ả n ăng t ự thay đổi m ục đích c ũng nh ư không có kh ả năng hành động m ột cách m ềm d ẻo, ngoài nh ững gì ch ứa trong gi ải thu ật và mô t ả bài toán. Vì v ậy k ỹ thu ật tìm ki ếm là ch ưa đủ để t ạo ra h ệ th ống thông minh. - Sử d ụng tri th ức và suy di ễn cho phép h ệ th ống ho ạt độ ng c ả trong tr ường h ợp thông tin quan sát v ề môi tr ường là không đầy đủ . H ệ th ống có th ể k ết h ợp tri th ức chung đã có để b ổ sung cho thông tin quan sát được khi c ần ra quy ết đị nh. Ví d ụ, khi giao ti ếp b ằng ngôn ng ữ t ự nhiên, có th ể hi ểu m ột câu ng ắn g ọn nh ờ s ử d ụng tri th ức đã có v ề ng ữ c ảnh giao ti ếp và n ội dung liên quan t ới ch ủ đề . - Vi ệc s ử d ụng tri th ức thu ận l ợi cho vi ệc xây d ựng h ệ th ống. Thay vì l ập trình l ại hoàn toàn h ệ th ống, có th ể thay đổ i tri th ức trang b ị cho h ệ th ống và mô t ả m ục đích cần đạ t được, đồ ng thời gi ữ nguyên th ủ t ục suy di ễn. Biểu di ễn tri th ức Để có th ể s ử d ụng tri th ức, tri th ức c ần được bi ểu di ễn d ưới d ạng thu ận ti ện cho vi ệc mô t ả và suy di ễn. Nhi ều ngôn ng ữ và mô hình bi ểu di ễn tri th ức đã được thi ết k ế để ph ục v ụ m ục đích này. Ngôn ng ữ bi ểu di ễn tri th ức ph ải là ngôn ng ữ hình th ức để tránh tình tr ạng nh ập nh ằng nh ư th ường g ặp trong ngôn ng ữ t ự nhiên. M ột ngôn ng ữ bi ểu di ễn tri th ức t ốt ph ải có nh ững tính ch ất sau: - Ngôn ng ữ ph ải có kh ả n ăng bi ểu di ễn t ốt, t ức là cho phép bi ểu di ễn m ọi tri th ức c ần thi ết cho bài toán. - Cần đơn gi ản và hi ệu qu ả, t ức là cho phép bi ểu di ễn ng ắn g ọn tri th ức, đồ ng th ời cho phép đi đến k ết lu ận v ới kh ối l ượng tính toán th ấp. - Gần v ới ngôn ng ữ t ự nhiên để thu ận l ợi cho ng ười s ử d ụng trong vi ệc mô t ả tri th ức.
37. Bi ểu di ễn tri th ức và suy di ễn logic Sau khi đã có ngôn ng ữ bi ểu di ễn tri th ức, tri th ức v ề th ế gi ới c ủa bài toán được bi ểu di ễn dưới d ạng t ập h ợp các câu và t ạo thành c ơ s ở tri th ức (ký hi ệu KB trong các ph ần sau). Th ủ t ục suy di ễn được s ử d ụng để t ạo ra nh ững câu m ới nh ằm tr ả l ời cho các v ấn đề c ủa bài toán. Thay vì tr ực ti ếp hành động trong th ế gi ới th ực c ủa bài toán, h ệ th ống có th ể suy di ễn d ựa trên c ơ s ở tri th ức được t ạo ra. Logic Trong ch ươ ng này, ta s ẽ xem xét lô gic v ới vai trò là ph ươ ng ti ện để bi ểu di ễn tri th ức và suy di ễn. Dạng bi ểu di ễn tri th ức c ổ điển nh ất trong máy tính là logic, v ới hai d ạng ph ổ bi ến là logic mệnh đề và logic v ị t ừ. Logic là m ột ngôn ng ữ bi ểu di ễn tri th ức trong đó các câu nh ận hai giá tr ị đúng (True) ho ặc sai (False) 1 được xác đị nh bởi 3 thành ph ần sau:
    Cú pháp bao gồm các ký hi ệu và các quy t ắc liên k ết các ký hi ệu để t ạo thành câu hay bi ểu th ức logic. M ột ví d ụ cú pháp là các ký hi ệu và quy t ắc xây d ựng bi ểu th ức trong s ố học và đại s ố.
    Ng ữ ngh ĩa c ủa ngôn ng ữ cho phép ta xác đị nh ý ngh ĩa c ủa các câu trong m ột mi ền nào đó c ủa th ế gi ới hi ện th ực, xác đị nh các s ự ki ện ho ặc s ự v ật ph ản ánh th ế gi ới th ực c ủa câu mệnh đề . Đối v ới logic, ng ữ ngh ĩa cho phép xác đị nh câu là đúng hay sai trong th ế gi ới của bài toán đang xét.
    Th ủ t ục suy di ễn là phươ ng pháp cho phép sinh ra các câu m ới t ừ các câu đã có ho ặc ki ểm tra li ệu các câu có ph ải là h ệ qu ả logic c ủa nhau. Logic đã cung c ấp cho các nhà nghiên c ứu m ột công c ụ hình th ức để bi ểu di ễn và suy lu ận tri th ức. Các bài sau s ẽ trình bày v ề hai d ạng logic m ệnh đề và logic v ị t ừ trong bi ểu di ễn tri th ức. 3.2. LOGIC M ỆNH ĐỀ 3.2.1. Cú pháp Logic m ệnh đề là logic rất đơn gi ản, tuy kh ả n ăng bi ểu di ễn c ủa nó còn m ột s ố h ạn ch ế nh ưng thu ận ti ện cho ta đưa vào nhi ều khái ni ệm quan tr ọng trong logic. Cú pháp c ủa logic m ệnh đề bao g ồm t ập các ký hi ệu và t ập các quy t ắc k ết h ợp các ký hi ệu tạo thành công th ức. a) Các ký hi ệu Các ký hi ệu được dùng trong logic m ệnh đề bao g ồm: o Các ký hi ệu chân lý: True (ký hi ệu T) và False (ký hi ệu F). o Các ký hi ệu m ệnh đề (còn được g ọi là các bi ến m ệnh đề và th ường được ký hi ệu bằng các ch ữ cái): P, Q, 1 Mt s h th ng logic đưc phát tri n v sau s d ng nhi u giá tr h ơn nh ư logic đa tr , logic m 37
38. Bi ểu di ễn tri th ức và suy di ễn logic o Các k ết n ối logic ∧, ∨, ¬, ⇒, ⇔. o Các d ấu ngo ặc. b) Các câu hay công th ức Mọi ký hi ệu chân lý và ký hi ệu m ệnh đề là câu. Ví d ụ: True, P Thêm ngo ặc ra ngoài m ột câu s ẽ được m ột câu. Kết h ợp các câu b ằng phép n ối logic s ẽ t ạo ra câu m ới. C ụ th ể là: Nếu A và B là câu thì: (A ∧B) ( đọc “A h ội B” ho ặc “A và B”) (A ∨B) ( đọc “A tuy ển B” ho ặc “A ho ặc B”) (¬ A) ( đọc “ph ủ đị nh A”) (A ⇒B) ( đọc “A kéo theo B” ho ặc “n ếu A thì B”). Phép kéo theo còn được g ọi là quy t ắc “n ếu – thì” (A ⇔B) ( đọc “A và B kéo theo nhau”) là các câu. Để cho ng ắn g ọn các công th ức được b ỏ đi các c ặp d ấu ngo ặc không c ần thi ết. Ch ẳng h ạn, thay cho ((A ∨B) ∧C) ta s ẽ vi ết là (A ∨B) ∧C. Trong tr ường h ợp m ột câu ch ứa nhi ều phép n ối, các phép n ối s ẽ được th ực hi ện theo th ứ t ự sau: ¬, ∧∧∧, ∨∨∨, ⇒, ⇔ Các câu là các ký hi ệu m ệnh đề s ẽ được g ọi là các câu đơ n ho ặc câu nguyên tử. Các câu không ph ải là câu đơ n được g ọi là câu ph ức h ợp. N ếu P là ký hi ệu m ệnh đề thì P và ¬ P được g ọi là literal, P là literal d ươ ng, còn ¬ P là literal âm . Câu ph ức h ợp có d ạng A 1∨ ∨Am trong đó A i là các literal s ẽ được g ọi là câu tuy ển (clause) . 3.2.2. Ng ữ ngh ĩa Ng ữ ngh ĩa c ủa logic m ệnh đề cho phép xác định m ột câu (công th ức) logic là đúng hay sai trong th ế gi ới c ủa bài toán đang xét, t ức là cách di ễn gi ải c ủa các ký hi ệu m ệnh đề , ký hi ệu chân lý và phép n ối logic trong th ế gi ới đó. Trong logic m ệnh đề , ng ười s ử d ụng xác đị nh giá tr ị đúng hay sai cho ký hi ệu m ệnh đề . Mỗi ký hi ệu m ệnh đề có th ể t ươ ng ứng v ới m ột phát bi ểu (m ệnh đề ), ví d ụ ký hi ệu m ệnh đề A có th ể t ươ ng ứng v ới phát bi ểu: “Hà N ội là th ủ đô c ủa Vi ệt Nam” hoặc b ất kì m ột phát bi ểu nào khác. M ột phát bi ểu ch ỉ có th ể đúng (True) ho ặc sai (False). Ch ẳng h ạn, phát bi ểu “Hà N ội là th ủ đô c ủa Vi ệt Nam ” là đúng còn phát bi ểu “ L ợn là gia c ầm ” là sai. 38
39. Bi ểu di ễn tri th ức và suy di ễn logic Một minh h ọa là m ột cách gán cho m ỗi bi ến m ệnh đề m ột giá tr ị chân lý True ho ặc False. Nếu bi ến m ệnh đề A được gán giá tr ị chân lý True/False (A B A B False False True False False True True False True True False True True False True False False False True False False True True False True True True True Sử d ụng b ảng chân lý, ta có th ể tính được giá tr ị b ất c ứ câu ph ức nào b ằng cách th ực hi ện đệ quy nh ững k ết n ối thành ph ần. Các công th ức t ươ ng đươ ng Các phép bi ến đổ i t ươ ng đươ ng giúp đư a các công th ức v ề d ạng thu ận l ợi cho vi ệc lập lu ận và suy di ễn. Hai công th ức A và B được xem là tươ ng đươ ng nếu chúng có cùng m ột giá tr ị chân lý trong m ọi minh h ọa. Ký hi ệu: Để ch ỉ A t ươ ng đươ ng v ới B ta vi ết A ≡ B. Bằng ph ươ ng pháp b ảng chân lý, d ễ dàng ch ứng minh được s ự t ươ ng đươ ng c ủa các công th ức sau đây : o A=>B ≡ ¬ A ∨ B o A B ≡ (A=>B) ∧ (B=>A) o ¬ (¬ A) ≡ A Luật De Morgan o ¬ (A ∨ B) ≡¬ A ∧ ¬ B o ¬ (A ∧ B) ≡ ¬ A ∨ ¬ B Lu ật giao hoán o A v B ≡ B v A 39
40. Bi ểu di ễn tri th ức và suy di ễn logic o A ∧ B ≡ B ∧ A Lu ật k ết h ợp o (A ∨ B) ∨ C ≡ A∨ ( B ∨ C) o (A ∧ B) ∧ C ≡ A ∧ ( B ∧ C) Lu ật phân ph ối o A ∧ (B ∨ C) ≡ (A ∧ B ) ∨ (A ∧ C) o A ∨ (B ∧ C) ≡ (A v B ) ∧ (A ∨ C) 3.3. SUY DI ỄN V ỚI LOGIC M ỆNH ĐỀ 3.3.1. Suy di ễn logic Một công th ức H được xem là hệ qu ả logic của m ột t ập công th ức G ={G 1, ,G m} n ếu trong b ất k ỳ minh h ọa nào mà {G 1, ,G m} đúng thì H c ũng đúng. Khi có m ột c ơ s ở tri th ức dưới d ạng t ập h ợp các câu logic, ta mu ốn s ử d ụng các tri th ức trong c ơ s ở này để suy ra tri th ức m ới mà nó là h ệ qu ả logic c ủa các công th ức trong c ơ s ở tri th ức. Điều đó được th ực hi ện b ằng các th ực hi ện suy di ễn. Suy di ễn hay suy lý th ường dùng ch ỉ quá trình cho phép rút ra k ết lu ận. Để th ực hi ện suy di ễn ta s ử d ụng lu ật suy di ễn. M ột lu ật suy di ễn g ồm hai ph ần : m ột t ập các điều ki ện và m ột k ết lu ận. Định ngh ĩa. Th ủ t ục suy di ễn được g ọi là đúng đắn (sound) n ếu k ết qu ả suy di ễn là h ệ qu ả logic c ủa điều ki ện. Th ủ t ục suy di ễn được g ọi là đầy đủ (complete) n ếu cho phép tìm ra m ọi h ệ qu ả logic c ủa điều ki ện. Ta s ẽ s ử d ụng nh ững kí hi ệu sau: KB: kí hi ệu t ập các câu đã có hay c ơ s ở tri th ức (Knowledge Base) KB ╞ α : Khi các câu trong KB là đúng (True) thì α là đúng (True), hay α là h ệ qu ả logic của KB. 3.3.2. Suy di ễn s ử d ụng b ảng chân lý Bằng cách s ử d ụng b ảng chân lý ta có th ể xác đị nh được m ột công th ức có ph ải là h ệ qu ả logic c ủa các công th ức trong c ơ s ở tri th ức hay không. Ví d ụ: cho KB: A ∨∨∨ C , B ∨∨∨¬∨ C và α = A ∨∨∨ B Để ki ểm tra α có ph ải h ệ qu ả logic c ủa KB không, ta xây d ựng b ảng sau (b ảng 3.2): 40
41. Bi ểu di ễn tri th ức và suy di ễn logic Kết qu ả xây d ựng b ảng cho th ấy, α là h ệ qu ả logic c ủa KB, hay nói cách khác t ừ KB suy ra được α. Bảng 3.2. B ảng chân lý A B C A ∨∨∨ C B ∨∨∨¬∨ C (A ∨∨∨ C) ∧∧∧ (B ∨∨∨¬∨ C) A ∨∨∨ B KB ╞ α T T T T T T T √ T T F T T T T √ T F T T F F T T F F T T T T √ F T T T T T T √ F T F F T F T F F T T F F F F F F F T F F Suy di ễn v ới logic m ệnh đề s ử d ụng b ảng chân lý là th ủ t ục suy di ễn đầ y đủ và đúng đắn. Tính đúng đắn là hi ển nhiên do b ảng chân lý s ử d ụng đúng ng ữ ngh ĩa được quy đị nh v ới k ết n ối logic. Tính đầy đủ là do s ố l ượng các t ổ h ợp giá tr ị đố i v ới logic m ệnh đề là h ữu h ạn và do v ậy có th ể li ệt kê đầy đủ tr ường h ợp KB có giá tr ị đúng. Tuy nhiên, c ần l ưu ý r ằng, m ột công thức ch ứa n bi ến m ệnh đề , thì s ố các minh h ọa c ủa nó là 2 n , t ức là b ảng chân lý có 2 n dòng. Nh ư v ậy vi ệc ki ểm tra m ột công th ức có ph ải là m ột h ệ qu ả lôgic hay không b ằng ph ươ ng pháp b ảng chân lý có độ ph ức t ạp tính toán l ớn do đòi h ỏi th ời gian theo hàm mũ. Cook (1971) đã ch ứng minh r ằng, ph ươ ng pháp ch ứng minh thu ật suy di ễn là vấn đề NP-đầy đủ . 3.3.3. Sử d ụng các quy t ắc suy di ễn Do vi ệc suy di ễn s ử d ụng b ảng nh ư trên có độ ph ức t ạp l ớn nên c ần có nh ững thu ật toán suy di ễn hi ệu qu ả h ơn cho logic m ệnh đề . Các th ủ t ục suy di ễn đề u d ựa trên m ột s ố khái ni ệm nh ư công th ức t ươ ng được và các quy t ắc suy di ễn. Sau đây là m ột s ố lu ật suy di ễn quan tr ọng trong logic m ệnh đề . Trong các lu ật này α, αi , β, γ là các câu. Ph ần ti ền đề hay ph ần điều ki ện được vi ết d ưới dạng t ử s ố, ph ần h ệ qu ả được vi ết d ưới d ạng m ẫu s ố. 1. Lu ật Modus Ponens α=>β,α β 41
42. Bi ểu di ễn tri th ức và suy di ễn logic Từ m ột kéo theo và gi ả thi ết c ủa kéo theo, ta suy ra k ết lu ận c ủa nó. 2. Lu ật Modus Tollens α=>β,¬ β ¬ α Từ m ột kéo theo và ph ủ đị nh k ết lu ận c ủa nó, ta suy ra ph ủ đị nh gi ả thi ết c ủa kéo theo. 3.Lu ật lo ại tr ừ và α1∧∧∧ ∧∧∧αi∧∧∧ ∧∧∧αm αi Từ m ột công th ức và ta đư a ra m ột nhân t ử b ất k ỳ c ủa công th ức đó . 4. Lu ật nh ập đề và α1, , αi, αm α1∧∧∧ ∧∧∧αi∧∧∧ ∧∧∧αm Từ m ột danh sách các công th ức, ta suy ra phép và c ủa chúng. 5. Lu ật nh ập đề ho ặc αi α1v v αi.v v αm Từ m ột công th ức, ta suy ra m ột phép ho ặc mà m ột trong các h ạng t ử c ủa phép ho ặc là công th ức đó. 6. Lu ật lo ại tr ừ ph ủ đị nh kép ¬ (¬ α) α Phép ph ủ đị nh c ủa ph ủ đị nh m ột công th ức, ta suy ra chính công th ức đó. 7. Lu ật b ắc c ầu α => β, β => γ α=> γ Từ hai kéo theo, mà k ết lu ận c ủa nó là c ủa kéo theo th ứ nh ất trùng v ới gi ả thi ết c ủa kéo theo th ứ hai, ta suy ra kéo theo m ới mà gi ả thi ết c ủa nó là gi ả thi ết c ủa kéo theo th ứ nh ất, còn k ết lu ận c ủa nó là k ết lu ận c ủa kéo theo th ứ hai. 8. Phép gi ải đơn v ị α v β, ¬ β 42
43. Bi ểu di ễn tri th ức và suy di ễn logic α Từ m ột phép ho ặc, m ột h ạng t ử đố i l ập v ới m ột h ạng t ử trong tuy ển kia, ta suy ra h ạng t ử còn l ại. 9. Phép gi ải α v β,¬ β v γ α v γ Từ hai phép ho ặc, m ột phép ho ặc ch ứa m ột h ạng t ử đố i l ập v ới m ột h ạng t ử trong phép ho ặc kia, ta suy ra phép ho ặc c ủa các h ạng t ử còn l ại. Một lu ật suy di ễn được xem là tin c ậy n ếu b ất k ỳ m ột mô hình nào c ủa gi ả thi ết c ủa lu ật cũng là mô hình k ết lu ận c ủa lu ật. Chúng ta ch ỉ quan tâm đế n các lu ật suy di ễn tin c ậy. Với các quy t ắc suy di ễn v ừa trình bày, vi ệc suy di ễn trên logic m ệnh đề được th ực hi ện nh ờ m ột s ố th ủ t ục nh ất đị nh, trong đó thông d ụng nh ất là suy di ễn b ằng phép gi ải (resolution) và ph ản ch ứng (refutation). Tuy nhiên trong ph ần này chúng ta không đi sâu vào các th ủ t ục này mà sẽ xem xét các th ủ t ục ch ứng minh trong ph ần trình bày v ề logic v ị t ừ. Bài t ập 1. KB = (A v B) ∧∧∧ (¬ C v ¬ D v E ) Các câu nào sau đây sinh ra t ừ KB? 1- A v B 2- (A v B v C) ∧∧∧ ( (B ∧∧∧ C ∧∧∧ D) = > E ) 1. Cho KB: Red Blue = > Silver ¬ Pink v Blue Pink = > Tan Tan ∨ Orange Silver ¬ Pink ¬ (Violet ∨ White) Pink => Red Blue => Orange Suy ra: a- ¬ Orange b- Silver ∧ Red c- Silver ∨ White 43
44. Bi ểu di ễn tri th ức và suy di ễn logic 3.4. LOGIC V Ị T Ừ (LOGIC B ẬC 1) Trong ph ần tr ước ta đã xem xét logic m ệnh đề và cách s ử d ụng logic m ệnh để bi ểu di ễn tri th ức. Bên c ạnh ưu điểm là đơ n gi ản, logic m ệnh đề có m ột nh ược điểm l ớn là kh ả n ăng bi ểu di ễn hạn ch ế, không th ể s ử d ụng để bi ểu di ễn tri th ức m ột cách ng ắn g ọn cho nh ững bài toán có độ ph ức t ạp l ớn. C ụ th ể là logic m ệnh để thu ật l ợi cho bi ểu di ễn s ự ki ện, s ự ki ện đơn gi ản được bi ểu di ễn b ằng câu nguyên t ử, s ự ki ện ph ức t ạp được bi ểu di ễn b ằng cách s ử d ụng k ết n ối logic để k ết hợp câu nguyên t ử. Logic m ệnh để không cho phép bi ểu di ễn m ột cách ng ắn g ọn môi tr ường v ới nhi ều đố i t ượng. Ch ẳng h ạn để th ể hi ện nh ận xét “sinh viên trong l ớp nào đó ch ăm h ọc” ta ph ải sử d ụng các câu riêng r ẽ để th ể hi ện t ừng sinh viên c ụ th ể trong l ớp ch ăm h ọc. Trong ph ần này ta s ẽ xem xét logic v ị t ừ - một h ệ th ống logic có kh ả n ăng th ể bi ểu di ễn mạnh h ơn, đồng th ời xem xét chi ti ết th ủ t ục suy di ễn v ới logic v ị t ừ. 3.4.1. Đặc điểm Đặc điểm quan tr ọng nh ất c ủa logic v ị t ừ cho phép bi ểu di ễn th ế gi ới xung quanh d ưới d ạng các đối t ượng, tính ch ất đố i t ượng, và quan h ệ gi ữa các đố i t ượng đó. Vi ệc s ử d ụng đố i t ượng là rất t ự nhiên trong th ế gi ới th ực và trong ngôn ng ữ t ự nhiên, v ới danh t ừ bi ểu di ễn đố i t ượng, tính từ bi ểu di ễn tính ch ất và động t ừ bi ểu di ễn quan h ệ gi ữa các đố i t ượng. Có th ể k ể ra r ất nhi ều ví dụ v ề đố i t ượng, tính ch ất và quan h ệ: o Đối t ượng : m ột cái bàn, m ột cái nhà, m ột cái cây, m ột con ng ười, m ột sinh viên, m ột con số. o Tính ch ất : Cái bàn có th ể có tính ch ất : có b ốn chân, làm b ằng g ỗ, không có ng ăn kéo, sinh viên có th ể có tính ch ất là thông minh, cao, g ầy o Quan h ệ : cha con, anh em, bè b ạn (gi ữa con ng ười ); l ớn h ơn nh ỏ h ơn, b ằng nhau ( gi ữa các con s ố ) ; bên trong, bên ngoài n ằm trên n ằm d ưới (gi ữa các đồ v ật ) o Hàm : M ột tr ường h ợp riêng c ủa quan h ệ là quan h ệ hàm, trong đó v ới m ỗi đầ u vào ta có một giá tr ị hàm duy nh ất Ví d ụ: tay trái c ủa ai đó, b ố c ủa ai đó, b ội s ố chung nh ỏ nh ất c ủa hai s ố. Logic v ị t ừ có cú pháp và ng ữ ngh ĩa được xây d ựng d ựa trên khái ni ệm đố i t ượng. H ệ th ống logic này đóng vai trò quan tr ọng trong vi ệc bi ểu di ễn tri th ức do có kh ả n ăng bi ểu di ễn phong phú và t ự nhiên, đồng th ời là c ơ s ở cho nhi ều h ệ th ống logic khác. 3.4.2. Cú pháp và ng ữ ngh ĩa Trong ph ần này ta s ẽ xem xét cú pháp, t ức là quy t ắc t ạo ra nh ững câu hay bi ểu th ức logic, của logic v ị t ừ cùng v ới ng ữ ngh ĩa c ủa nh ững c ấu trúc đó. Các ký hi ệu và ý ngh ĩa Logic v ị t ừ sử d ụng nh ững d ạng ký hi ệu sau. o Các ký hi ệu h ằng: Nam, 3, V ịnh H ạ long, o Các ký hi ệu bi ến: x, y, z, 44
45. Bi ểu di ễn tri th ức và suy di ễn logic o Các ký hi ệu v ị t ừ: Thích (Nam, B ắc), Làm_t ừ_g ỗ (t ủ), Anh_em (An, Ba, Út) Ký hi ệu v ị t ừ th ể hi ện quan h ệ gi ữa các đố i t ượng. M ỗi v ị t ừ có th ể có n tham s ố ( n≥0). Ví d ụ Thích là v ị t ừ c ủa hai tham s ố, Làm_t ừ_g ỗ là v ị t ừ m ột tham s ố. Các ký hi ệu v ị t ừ không tham s ố là các ký hi ệu m ệnh đề. o Các ký hi ệu hàm: Mẹ_c ủa(An), min(3,4,9), Ký hi ệu hàm th ể hi ện quan h ệ hàm. Mỗi hàm có th ể có n tham s ố ( n ≥1). o Các ký hi ệu k ết n ối logic: ∧ ( h ội), ∨ (tuy ển), ¬ ( ph ủ đị nh), ⇒(kéo theo), ⇔ ( t ươ ng đươ ng ). o Các ký hi ệu l ượng t ử: ∀ ( v ới m ọi), ∃ ( t ồn t ại). o Các ký hi ệu ng ăn cách: d ấu ph ẩy, d ấu m ở ngo ặc và d ấu đóng ngo ặc. Tươ ng t ự nh ư v ới logic m ệnh đề , ng ữ ngh ĩa cho phép liên k ết bi ểu th ức logic v ới th ế gi ới của bài toán để xác đị nh tính đúng ho ặc sai c ủa bi ểu th ức. M ột liên k ết c ụ th ể nh ư v ậy được g ọi là một minh h ọa. Minh h ọa xác đị nh c ụ th ể đố i t ượng, quan h ệ và hàm mà các ký hi ệu h ằng, v ị t ừ, và ký hi ệu hàm th ể hi ện. Để xác đị nh m ột minh ho ạ, tr ước h ết ta c ần xác đị nh m ột mi ền đố i t ượng (nó bao g ồm t ất cả các đố i t ượng trong th ế gi ới hi ện th ực mà ta quan tâm). Cũng có th ể xác đị nh mi ền đối t ượng cho t ừng tham s ố c ủa m ột v ị t ừ ho ặc m ột hàm nào đó. Ví d ụ trong v ị t ừ Thích(x,y), mi ền c ủa x là tất c ả m ọi ng ười, mi ền c ủa y là các lo ại độ ng v ật. S ố đố i t ượng có th ể là vô h ạn, ch ẳng h ạn trong tr ường h ợp mi ền đố i t ượng là toàn b ộ s ố th ực. Vi ệc l ựa ch ọn tên cho h ằng, bi ến, v ị t ừ, và hàm hoàn toàn do ng ười dùng quy ết đị nh. Có th ể có nhi ều minh h ọa khác nhau cho cùng m ột th ế gi ới th ực. Vi ệc suy di ễn, tính đúng đắ n c ủa bi ểu th ức được xác đị nh d ựa trên toàn b ộ minh h ọa. Hạng th ức (term) Hạng th ức (term) là bi ểu th ức logic có k ết qu ả là đối t ượng. Hạng th ức được xác đị nh đệ quy nh ư sau. o Các ký hi ệu h ằng và các ký hi ệu bi ến là h ạng th ức. o Nếu t 1, t 2, t 3, , t n là n h ạng th ức và f là m ột ký hi ệu hàm n tham s ố thì f(t1, t 2, , tn) là h ạng th ức. M ột h ạng th ức không ch ứa bi ến được g ọi là m ột hạng th ức c ụ th ể (ground term). Ch ẳng h ạn, An là ký hi ệu h ằng, M ẹ_c ủa là ký hi ệu hàm, thì Mẹ_c ủa(An) là m ột h ạng th ức cụ th ể. Ng ữ ngh ĩa c ủa h ạng th ức nh ư sau: các h ằng, bi ến, tham s ố t ươ ng ứng v ới đố i t ượng trong mi ền đối t ượng; ký hi ệu hàm t ươ ng ứng v ới quan h ệ hàm trong th ế gi ới th ực; h ạng th ức t ươ ng ứng v ới đố i t ượng là giá tr ị c ủa hàm khi nh ận tham s ố. Ký hi ệu “=” Hai h ạng th ức b ằng nhau và được ký hi ệu “=” n ếu cùng t ươ ng ứng v ới m ột đố i t ượng. 45
46. Bi ểu di ễn tri th ức và suy di ễn logic Ví d ụ: Mẹ_c ủa(Vua_T ự_Đứ c) = Bà_T ừ_D ũ Tính đúng đắn c ủa quan h ệ b ằng được xác đị nh b ằng cách ki ểm tra hai v ế c ủa ký t ự “=”. Câu nguyên t ử Các câu nguyên t ử, còn g ọi là câu đơ n, được xác đị nh nh ư sau: o Vị t ừ có tham s ố là h ạng th ức là câu nguyên t ử. o Hạng th ức 1 = h ạng th ức 2 là câu nguyên t ử. Ví d ụ : Yêu ( Hoa, Mẹ_c ủa( Hoa)) Mẹ_c ủa(Vua_T ự_Đứ c) = Bà_T ừ_D ũ Câu nguyên t ử nh ận giá tr ị đúng (true) trong m ột minh h ọa nào đó n ếu quan h ệ được bi ểu di ễn b ới ký hi ệu v ị t ừ là đúng đối v ới các đố i t ượng được bi ểu di ễn b ới các h ạng th ức đóng vai trò thông s ố. Nh ư v ậy, câu nguyên t ử th ể hi ện nh ững s ự ki ện ( đơn gi ản) trong th ế gi ới c ủa bài toán. Câu Từ các câu nguyên t ử, s ử d ụng các k ết n ối logic và các l ượng t ử, ta xây d ựng nên các câu. Câu được đị nh ngh ĩa đệ quy nh ư sau: o Câu nguyên t ử là câu. o Nếu G và H là các câu nguyên t ử, thì các bi ểu th ức (G ∧ H), (G ∨ H), ( ¬ G), (G ⇒H), (G ⇔H) là câu o Nếu G là m ột câu nguyên t ử và x là bi ến thì các bi ểu th ức ( ∀ x G), ( ∃ x G) là câu Các câu không ph ải là câu nguyên t ử s ẽ được g ọi là các câu ph ức h ợp. Các câu không ch ứa bi ến được g ọi là câu c ụ th ể. Khi vi ết các công th ức ta s ẽ b ỏ đi các d ấu ngo ặc không c ần thi ết, ch ẳng h ạn các d ấu ngo ặc ngoài cùng. Ng ữ ngh ĩa c ủa câu ph ức h ợp được xác đị nh b ằng ng ữ ngh ĩa các câu đơn và các phép n ối tươ ng t ự trong logic m ệnh đề . Các l ượng t ử Logic m ệnh đề s ử d ụng hai l ượng t ử: v ới m ọi và t ồn tại. Lượng t ử v ới m ọi ( ∀ ) cho phép mô t ả tính ch ất c ủa c ả m ột l ớp các đố i t ượng, ch ứ không ph ải c ủa m ột đố i t ượng, mà không c ần ph ải li ệt kê ra t ất c ả các đố i t ượng trong l ớp. Ví d ụ ta s ử dụng v ị t ừ Elephant(x) ( đố i t ượng x là con voi ) và v ị t ừ Color(x, Gray) ( đố i t ượng x có màu xám) thì câu “ t ất c ả các con voi đề u có màu xám” có th ể bi ểu di ễn b ởi công th ức ∀x (Elephant(x) ⇒ Color(x, Gray)). Nh ư v ậy câu ∀ x P có ngh ĩa là câu P đúng v ới m ọi đố i t ượng x thu ộc mi ền giá tr ị đã được quy định c ủa th ế gi ới bài toán. L ượng t ự v ới m ọi có th ể coi nh ư h ội c ủa nhi ều câu. Lưu ý: l ượng t ử v ới m ọi được dùng v ới kéo theo ch ứ không dùng v ới “và”. Ch ẳng hạn, để nói r ằng m ọi sinh viên đều ch ăm h ọc thì câu 46
47. Bi ểu di ễn tri th ức và suy di ễn logic ∀x Sinh_viên(x) ⇒ Ch ăm_h ọc(x) là đúng trong khi ∀x Sinh_viên(x) ∧ Ch ăm_h ọc(x) là sai do câu này s ẽ có ý ngh ĩa t ất c ả m ọi ng ười đề u là sinh viên và đểu ch ăm h ọc. Lượng t ử t ồn t ại ( ∃ ) cho phép ta t ạo ra các câu nói đế n m ột đố i t ượng nào đó trong m ột lớp đố i t ượng mà nó có m ột tính ch ất ho ặc tho ả mãn m ột quan h ệ nào đó. Ví d ụ ta s ử d ụng các câu nguyên t ử Student(x) (x là sinh viên) và Inside(x, P308), (x ở trong phòng 308), ta có th ể bi ểu di ễn câu “ Có m ột sinh viên ở phòng 308” b ởi bi ểu th ức ∃x (Student(x) ∧ Inside(x,P301). Ng ữ ngh ĩa c ủa công th ức ∃x P được xác đị nh nh ư là ng ữ ngh ĩa c ủa công th ức là tuy ển c ủa tất c ả các công th ức nh ận được t ừ P b ằng cách thay x b ởi m ột đố i t ượng trong mi ền đố i t ượng. Lưu ý: L ượng t ử t ồn t ại được dùng v ới “và” ch ứ không dùng v ới “kéo theo”. Ch ẳng h ạn để nói r ằng có m ột s ố sinh viên ch ăm h ọc thì câu: ∃x Sinh_viên(x) ∧ Ch ăm_h ọc(x) là đúng trong khi ∃x Sinh_viên(x) ⇒ Ch ăm_h ọc(x) là sai. Th ật v ậy, do phép kéo theo đúng khi ti ền đề là sai nên câu trên đúng khi có m ột ng ười x nào đó không ph ải là sinh viên, trong khi đây không ph ải là ý mà ta mu ốn kh ẳng đị nh. Quan h ệ gi ữa l ượng t ử v ới m ọi và l ượng t ử t ồn t ại: l ượng t ử này có th ể bi ểu di ễn b ằng lượng t ử kia b ằng cách s ử d ụng phép ph ủ đị nh. Ví d ụ: ∀x Thích (x, Kem) t ươ ng đươ ng v ới ¬∃x ¬Thích(x, Kem) ∃y Thích (x, Kem) t ươ ng đươ ng v ới ¬∀x ¬Thích (x, Kem) Các l ượng t ử l ồng nhau Có th ể s ử d ụng đồ ng th ời nhi ều l ượng t ử trong m ột câu ph ức t ạp. Vùng ảnh h ưởng c ủa lượng t ử có th ể bao hàm l ượng t ử khác và khi đó ta nói l ượng t ử l ồng nhau. Ví d ụ: ∀x∀y Anh_em(x, y) ⇒ Họ_hàng(x, y) ∀x ∃y Yêu (x, y) Nhi ều l ượng t ử cùng lo ại có th ể được vi ết g ọn b ằng m ột ký hi ệu l ượng t ử, ví d ụ câu th ứ nh ất có th ể vi ết g ọn thành ∀x, y Anh_em(x, y) ⇒ Họ_hàng(x, y) Trong tr ường h ợp l ượng t ử v ới m ọi được s ử d ụng cùng l ượng t ử t ồn t ại thì th ứ t ự l ượng t ử ảnh h ưởng t ới ng ữ ngh ĩa c ủa câu và không được phép thay đổi. Ch ẳng h ạn câu ∀x ∃y Yêu (x, y) có ngh ĩa là m ọi ng ười đề u có ai đấ y để yêu, trong khi câu 47
48. Bi ểu di ễn tri th ức và suy di ễn logic ∃y ∀x Yêu (x, y) có ngh ĩa là có ai đó mà t ất c ả đề u yêu. Trong tr ường h ợp nhi ều l ượng t ử khác nhau cùng s ử d ụng m ột tên bi ến thì có th ể gây nh ầm lẫn vì v ậy c ần s ử d ụng tên bi ến khác nhau cho ký hi ệu l ượng t ử khác nhau. Một câu là câu nguyên t ử ho ặc là ph ủ đị nh c ủa câu nguyên t ử được g ọi là literal. Ch ẳng hạn, Play(x, Football), ¬ Like( Lan, Rose) là các literal. M ột công th ức là tuy ển c ủa các literal sẽ được g ọi là câu tuy ển. Ch ẳng h ạn, Male(x) ∨ ¬ Like(x, Foodball) là câu tuy ển. Các công th ức t ươ ng đươ ng Cũng nh ư trong logic m ệnh đề , ta nói hai công th ức G và H t ươ ng đươ ng ( vi ết là G ≡ H ) nếu chúng cùng đúng ho ặc cùng sai trong m ột minh ho ạ. Ngoài các t ươ ng đươ ng đã bi ết trong logic m ệnh đề , trong logic v ị t ừ c ấp m ột còn có các t ươ ng đươ ng khác liên quan t ới các l ượng t ử. Sau đây là các t ương đươ ng c ủa logic v ị t ừ ∀x G(x) ≡ ∀y G(y) ∃x G(x) ≡ ∃y G(y) Đặt tên l ại bi ến đi sau l ượng t ử t ồn t ại, ta nh ận được công th ức t ươ ng đươ ng . ¬ (∀x G(x)) ≡ ∃x ( ¬ G(x)) ¬ ( ∃x G(x)) ≡ ∀x ( ¬ G(x)) 3. ∀x (G(x) ∧ H(x)) ≡ ∀x G(x) ∧ ∀x H(x) ∃x (G(x) ∨ H(x)) ≡ ∃x G(x) ∨ ∃x H(x) Ví d ụ : ∀x Love(x, mother(x)) ≡ ∀y Love(y, mother(y)). Bài t ập 1. Vi ết các câu sau d ưới d ạng logic v ị t ừ: 1 - Mọi nhà nông thích m ặt tr ời 2 - Lúc nào c ũng có ng ười b ị l ừa 3 - Nấm có màu đỏ là n ấm độ c 4 - An không cao 5 - Ch ỉ có 2 sinh viên con nhà giàu h ọc l ớp D07 6 - Trên tr ời có muôn vàn vì sao 48
49. Bi ểu di ễn tri th ức và suy di ễn logic 3.5. SUY DI ỄN V ỚI LOGIC V Ị T Ừ 3.5.1. Quy t ắc suy di ễn Mọi quy t ắc suy di ễn cho logic m ệnh đề c ũng đúng v ới logic v ị t ừ. Ngoài ra, logic v ị t ừ còn có thêm m ột s ố quy t ắc suy di ễn khác, ch ủ y ếu được dùng v ới câu có ch ứa l ượng t ử, cho phép bi ến đổ i nh ững câu này thành câu không có l ượng t ử. Phép th ế (substitution) Tr ước khi đi xem xét quy t ắc suy diên, ta định ngh ĩa khái ni ệm phép th ế, c ần thi ết cho nh ững câu có ch ứa bi ến. Ký hi ệu là SUBST( θ, α ) Phép th ế giá tr ị θ vào câu α Ví d ụ: SUBST ({x/Nam, y/An} Thích(x,y)) = Thích(Nam, An) Phép lo ại tr ừ v ới m ọi (universal elimination) ∀ x α SUBST( {x/g}, α ) Ví d ụ: ∀ x Thích(x, Kem) {x/Nam} Thích (Nam, Kem) Lo ại tr ừ t ồn t ại (existential elimination) ∃ x α k là kí hi ệu h ằng ch ưa xu ất hi ện trong KB SUBST( {x/k}, α ) Ví d ụ: ∃ x Học_gi ỏi(x) {x/Nam) Học_gi ỏi (Nam) k được g ọi là h ằng Skolem và ta có th ể đặ t tên cho h ằng này. Yêu cầu v ới h ằng Skolem là hàm này ch ưa được phép xu ất hi ện trong c ơ s ở tri th ức tr ước đó. Nh ập đề t ồn t ại (existential introduction) Với câu α, bi ến x không thu ộc câu α và h ạng th ức c ơ s ở g thu ộc câu α Ta có: α ∃ x SUBST( {g/x}, α ) Thích(Nam, Kem) {Nam/x} ∃ x Thích (x, Kem) 49
50. Bi ểu di ễn tri th ức và suy di ễn logic Ví d ụ suy di ễn: Bob là trâu trâu (Bob) (1) Pat là l ợn lợn (Pat) (2) Trâu to h ơn l ợn ∀ x , y trâu (x) ∧ lợn (y) => to_h ơn (x,y) (3) Bob to h ơn Pat ? to_h ơn (Bob, Pat) ? Nh ập đề và, (1) (2) trâu (Bob) ∧ lợn(Pat) (4) Lo ại tr ừ với m ọi, (3) trâu(Bob) ∧ lợn (Pat) => to_h ơn (Bob,Pat) (5) Modus Ponens, (4) (5) to_h ơn (Bob, Pat) 1, 2, 3 1, 2, 3, 4 1, 2, 3, 4, 5 6 Suy di ễn t ự độ ng trên logic v ị t ừ khó h ơn r ất nhi ều so v ới logic m ệnh đề do các bi ến có th ể nh ận vô s ố các giá tr ị khác nhau. Ta c ũng không th ể s ử d ụng b ảng chân lý do kích th ước c ủa b ảng có th ể là vô h ạn. Phép h ợp nh ất (Unification) Hợp nh ất là th ủ t ục xác đị nh phép th ế c ần thi ết để làm cho 2 câu gi ống nhau và được ký hi ệu nh ư sau: UNIFY (p,q) = ( θ) SUBST( θ,p) = SUBST ( θ,q) θ được g ọi là h ợp t ử (ph ần t ử h ợp nh ất) Ví d ụ: p q θ Bi ết (Nam, x) Bi ết (Nam, B ắc) {x/B ắc} 50
51. Bi ểu di ễn tri th ức và suy di ễn logic Bi ết (Nam, x) Bi ết (y, M ẹ (y)) {y/Nam, x/ M ẹ (Nam)} Bi ết (Nam, x) Bi ết (y, z) {y/Nam, x/z} {y/Nam, x/Nam, z/Nam} Trong tr ường h ợp có nhi ều h ợp t ử thì ta s ử d ụng h ợp t ử t ổng quát nh ất t ức là h ợp t ử s ử dụng ít phép th ế cho bi ến nh ất MGU: most general unifier Phép h ợp nh ất có th ể th ực hi ện t ự độ ng b ằng thu ật toán có độ ph ức t ạp t ỉ l ệ tuy ến tính v ới số l ượng bi ến Modus Ponent t ổng quát (GMP) ’ ’ Gi ả s ử ta có các câu c ơ s ở, p i, pi , q và t ồn t ại phép th ế θ sao cho UNIFY (p i, pi ) = θ v ới m ọi i Khi đó ta có: p1’ , p 2’ , p 3’ , p n’ , (p 1 ∧ p2 ∧ ∧ pn=>q) SUBST( θ, q) Th ủ t ục suy di ễn v ới GMP là không đầy đủ v ới logic v ị t ừ nói chung. Suy di ễn b ằng GMP là đầy đủ trong tr ường h ợp KB ch ỉ ch ứa các câu horn (horn clause) – là các câu nguyên t ử, ho ặc là các phép kéo theo có v ế trái là tuy ển c ủa các câu c ơ s ở , v ế ph ải là câu nguyên t ử 3.5.2. Suy di ễn ti ến và suy di ễn lùi Sử d ụng quy t ắc Modus Ponens t ổng quát cho phép xây d ựng thu ật toán suy di ễn t ự độ ng, cụ th ể là ph ươ ng pháp suy di ễn ti ến và suy di ễn lùi. Suy di ễn ti ến (forward chaining) Th ủ t ục suy di ễn ti ến được th ực hi ện nh ư sau:  Khi câu p mới được thêm vào KB: – với m ỗi quy t ắc q mà p h ợp nh ất được v ới m ột ph ần v ế trái: • Nếu các ph ần còn l ại c ủa v ế trái đã có thì thêm v ế ph ải vào KB và suy di ễn ti ếp Hình 3.2. Th ủ t ục suy di ễn ti ến Ví d ụ: KB g ồm 51