🔙 Quay lại trang tải sách pdf ebook Giáo trình Nhập môn trí tuệ nhân tạo Ebooks Nhóm Zalo HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG ---------------------------- TỪ MINH PHƯƠNG GIÁO TRÌNH Nhập môn trí tuệ nhân tạo Hà nội 2014 1 CuuDuongThanCong.com https://fb.com/tailieudientucntt LỜI NÓI ĐẦU Trí tuệ nhân tạo là một lĩnh vực 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ả ứ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ư 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 kỹ thuật có nhiều ứ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. Trong khuôn khổ có hạn của tài liệu với tính chất là giáo trình, 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 đó, người đọc đượ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. Một số nội dung như giải thuật di truyền có thể bỏ qua trong phần nhập môn và dùng để tham khảo do tương đối phức tạp so với các kỹ thuật khác. Chương 3 tóm tắt về vấn đề sử dụng, biểu diễn tri thức và lập luận, trước khi đi sâu trình bày về biểu diễn tri thức và lập luận sử dụng 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. 2 CuuDuongThanCong.com https://fb.com/tailieudientucntt Chương 4 là mở rộng của biểu diễn tri thức và lập luậ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 không rõ ràng cùng với nguyên tắc lập luậ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à lập luận. Chương 5 là chương nhập môn về học máy. Trong chương này, người đọc đượ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 bốn 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, phân loại dựa trên ví dụ và hồi quy logistic, cùng với một số kỹ thuật đánh giá mô hình và lựa chọn đặc trưng. Đây là những phương pháp đơn giản, dễ giới thiệu, thuận tiện để trình bày với tính chất nhập môn. Đồng thời, đây cũng là những phương pháp có tính đại diện trong học máy, cần thiết cho người nghiên cứu về lĩnh vực này. Do ưu điểm và sự phổ biến của Support Vector Machines, phương pháp phân loại này cũng được giới thiệu, nhưng ở mức tóm tắt, không đi vào chi tiết để phù hợp với trình độ 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 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 12/2014 Tác giả 3 CuuDuongThanCong.com https://fb.com/tailieudientucntt 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 .....................................14 1.3.1. Các lĩnh vực nghiên cứu............................................................................................ 14 1.3.2. Một số ứng dụng và thành tựu................................................................................... 18 1.3.3. Những vấn đề chưa được giải quyết.......................................................................... 20 CHƯƠNG 2: GIẢI QUYẾT VẤN ĐỀ BẰNG TÌM KIẾM..................................................22 2.1. GIẢI QUYẾT VẤN ĐỀ VÀ KHOA HỌC TRÍ TUỆ NHÂN TẠO.............................22 2.2. BÀI TOÁN TÌM KIẾM TRONG KHÔNG GIAN TRẠNG THÁI .............................23 2.2.1. Phát biểu bài toán tìm kiếm....................................................................................... 23 2.2.2. Một số ví dụ............................................................................................................... 24 2.2.3. Thuật toán tìm kiếm tổng quát và cây tìm kiếm........................................................ 27 2.2.4. Các tiêu chuẩn đánh giá thuật toán tìm kiếm............................................................. 30 2.3. TÌM KIẾM KHÔNG CÓ THÔNG TIN (TÌM KIẾM MÙ)..........................................31 2.3.1. Tìm kiếm theo chiều rộng.......................................................................................... 31 2.3.2. Tìm kiếm theo giá thành thống nhất.......................................................................... 35 2.3.3. Tìm kiếm theo chiều sâu............................................................................................ 36 2.3.4. Tìm kiếm sâu dần ...................................................................................................... 38 2.3.5. Tìm theo hai hướng ................................................................................................... 42 2.4. TÌM KIẾM CÓ THÔNG TIN.......................................................................................43 2.4.1. Tìm kiếm tham lam.................................................................................................... 44 2.4.2. Thuật toán A* ............................................................................................................ 46 2.4.3. Các hàm heuristic ...................................................................................................... 48 2.4.4. Thuật toán IDA* (thuật toán A* sâu dần) ................................................................. 50 2.5. TÌM KIẾM CỤC BỘ ....................................................................................................52 2.5.1. Thuật toán leo đồi...................................................................................................... 54 2.5.2. Thuật toán tôi thép..................................................................................................... 59 2.5.3. Giải thuật di truyền.................................................................................................... 61 2.5.4. Một số thuật toán tìm kiếm cục bộ khác.................................................................... 68 2.6. ỨNG DỤNG MINH HOẠ............................................................................................69 2.7. CÂU HỎI VÀ BÀI TẬP CHƯƠNG ............................................................................73 CHƯƠNG 3: BIỂU DIỄN TRI THỨC VÀ LẬP LUẬN LOGIC.........................................76 3.1. SỰ CẦN THIẾT SỬ DỤNG TRI THỨC TRONG GIẢI QUYẾT VẤN ĐỀ..............76 3.2. LOGIC MỆNH ĐỀ .......................................................................................................77 3.2.1. Cú pháp...................................................................................................................... 77 3.2.2. Ngữ nghĩa .................................................................................................................. 79 3.3. SUY DIỄN VỚI LOGIC MỆNH ĐỀ ...........................................................................80 3.3.1. Suy diễn logic ............................................................................................................ 80 3.3.2. Suy diễn sử dụng bảng chân lý.................................................................................. 81 4 CuuDuongThanCong.com https://fb.com/tailieudientucntt 3.3.3. Sử dụng các quy tắc suy diễn .................................................................................... 82 3.4. LOGIC VỊ TỪ (LOGIC BẬC 1) ..................................................................................84 3.4.1. Đặc điểm.................................................................................................................... 84 3.4.2. Cú pháp và ngữ nghĩa................................................................................................ 84 3.5. SUY DIỄN VỚI LOGIC VỊ TỪ...................................................................................90 3.5.1. Quy tắc suy diễn ........................................................................................................ 90 3.5.2. Suy diễn tiến và suy diễn lùi...................................................................................... 95 3.5.3. Suy diễn sử dụng phép giải....................................................................................... 98 3.5.4. Hệ thống suy diễn tự động: lập trình logic .............................................................. 104 3.6. CÂU HỎI VÀ BÀI TẬP CHƯƠNG ..........................................................................104 CHƯƠNG 4: LẬP LUẬN XÁC SUẤT ..............................................................................108 4.1. VẤN ĐỀ THÔNG TIN KHÔNG CHẮC CHẮN KHI LẬP LUẬN ..........................108 4.2. NGUYÊN TẮC LẬP LUẬN XÁC SUẤT.................................................................109 4.3. MỘT SỐ KHÁI NIỆM VỀ XÁC SUẤT....................................................................110 4.3.1. Các tiên đề xác suất ................................................................................................. 110 4.3.2. Xác suất đồng thời................................................................................................... 112 4.3.3. Xác suất điều kiện.................................................................................................... 114 4.3.4. Tính độc lập xác suất............................................................................................... 116 4.3.5. Quy tắc Bayes.......................................................................................................... 117 4.4. MẠNG BAYES ..........................................................................................................119 4.4.1. Khái niệm mạng Bayes............................................................................................ 119 4.4.2. Tính độc lập xác suất trong mạng Bayes................................................................. 121 4.4.3. Cách xây dựng mạng Bayes .................................................................................... 122 4.4.4. Tính độc lập xác suất tổng quát: khái niệm d-phân cách......................................... 125 4.5. SUY DIỄN VỚI MẠNG BAYES ..............................................................................127 4.5.1. Suy diễn dựa trên xác suất đồng thời....................................................................... 128 4.5.2. Độ phức tạp của suy diễn trên mạng Bayes............................................................. 129 4.5.3. Suy diễn cho trường hợp riêng đơn giản ................................................................. 130 4.5.4. Suy diễn bằng phương pháp lấy mẫu ...................................................................... 131 4.5.5. Phương pháp loại trừ biến ....................................................................................... 136 4.6. ỨNG DỤNG SUY DIỄN XÁC SUẤT.......................................................................143 4.7. CÂU HỎI VÀ BÀI TẬP CHƯƠNG ..........................................................................147 CHƯƠNG 5: HỌC MÁY....................................................................................................150 5.1. KHÁI NIỆM HỌC MÁY ...........................................................................................150 5.1.1. Học máy là gì........................................................................................................... 150 5.1.2. Ứng dụng của học máy............................................................................................ 151 5.1.3. Các dạng học máy.................................................................................................... 152 5.1.4. Học có giám sát ....................................................................................................... 153 5.2. HỌC CÂY QUYẾT ĐỊNH.........................................................................................156 5.2.1. Khái niệm cây quyết định........................................................................................ 156 5.2.2. Thuật toán học cây quyết định................................................................................. 158 5.2.3. Các đặc điểm thuật toán học cây quyết định ........................................................... 163 5.2.4. Vấn đề quá vừa dữ liệu............................................................................................ 164 5 CuuDuongThanCong.com https://fb.com/tailieudientucntt 5.2.5. Sử dụng thuộc tính có giá trị liên tục....................................................................... 165 5.2.6. Sử dụng cách đánh giá thuộc tính khác ................................................................... 166 5.3. PHÂN LOẠI BAYES ĐƠN GIẢN ............................................................................166 5.3.1. Phương pháp phân loại Bayes đơn giản .................................................................. 167 5.3.2. Vấn đề tính xác suất trên thực tế ............................................................................. 169 5.3.3. Ứng dụng trong phân loại văn bản tự động ............................................................. 170 5.4. HỌC DỰA TRÊN VÍ DỤ: THUẬT TOÁN K LÁNG GIỀNG GẦN NHẤT............171 5.4.1. Nguyên tắc chung .................................................................................................... 171 5.4.2. Phương pháp k-láng giềng gần nhất ........................................................................ 172 5.4.3. Một số lưu ý với thuật toán k-NN ........................................................................... 174 5.5. HỒI QUY TUYẾN TÍNH VÀ HỒI QUY LOGISTIC...............................................175 5.5.1. Hồi quy tuyến tính ................................................................................................... 175 5.5.2. Hồi quy logistic ....................................................................................................... 180 5.5.3. Hồi quy logistic cho phân loại đa lớp...................................................................... 183 5.6. SUPPORT VECTOR MACHINES............................................................................185 5.6.1. Phân loại tuyến tính với lề cực đại .......................................................................... 185 5.6.2. Kỹ thuật hàm nhân và SVM tổng quát .................................................................... 189 5.6.3. Sử dụng trên thực tế................................................................................................. 192 5.7. ĐÁNH GIÁ VÀ LỰA CHỌN MÔ HÌNH..................................................................193 5.7.1. Các độ đo sử dụng trong đánh giá ........................................................................... 193 5.7.2. Đánh giá mô hình bằng kiểm tra chéo..................................................................... 194 5.7.3. Lựa chọn đặc trưng.................................................................................................. 196 5.8. SƠ LƯỢC VỀ MỘT SỐ PHƯƠNG PHÁP HỌC MÁY KHÁC................................198 5.9. CÂU HỎI VÀ BÀI TẬP CHƯƠNG ..........................................................................200 TÀI LIỆU THAM KHẢO......................................................................................................202 6 CuuDuongThanCong.com https://fb.com/tailieudientucntt 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 (TTNT) 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 máy tính 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 Do con người được coi là động vật có trí tuệ, nên một cách rất tự nhiên là lấy con người làm thước đo khi đánh giá mức độ thông minh của máy tính. 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ó hành vi hay hành động tương tự con người, đặc biệt trong những hoạt động có liên quan tới trí tuệ. Để xác định thế nào là hành động như người, có thể sử dụng phép thử Turing. 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, tương tự khi ta chat hay nhắn tin. 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ệ. CuuDuongThanCong.com https://fb.com/tailieudientucntt 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. Mặc dù không nhiều người coi mục đích chính của trí tuệ nhân tạo là vượt qua phép thử Turing, một số hệ thống đã xây dựng chuyên cho mục đích này. Gần đây nhất, vào tháng 6 năm 2014, một hệ thống chat tự động có tên là Eugene Goostman do một nhóm nghiên cứu người Nga xây dựng đã giành giải nhất trong cuộc thi phép thử Turing. Sau khi thực hiện một đoạn hội thoại dài 5 phút với hệ thống, 33% giám khảo cho rằng đó là người thực. Một số ý kiến cho rằng Eugene Goostman là hệ thống máy tính đầu tiên vượt qua phép thử Turing. 2) Suy nghĩ như người Theo nhóm định nghĩa này, hành động thông minh chỉ đạt được nếu được dẫn dắt bởi quá trình suy nghĩ tương tự quá trình suy nghĩ của con 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 theo một số phương pháp như: 1) thực nghiệm về hành vi con người khi suy nghĩ hoặc giải quyết vấn đề; 2) chụp ảnh sóng não, đo tín hiệu điện từ hoặc các tín hiệu khác của não trong quá trình thực hiện các công việc khác nhau; 3) sử dụng các phương pháp nơ ron sinh học khác như kích thích não, giải phẫu não v.v. 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). Đây là lính vực khoa học liên ngành, kết hợp các mô hình máy tính với phương pháp thực nghiệm tâm lý. Nhiều kết quả nghiên cứu về nhận thức đã được áp dụng trong các mô hình tính toán. Ví dụ, nhiều nghiên cứu về quá trình tiếp nhận tín hiệu ảnh và nhận dạng đối tượng đã được áp dụng trong lĩnh vực thị giác máy. Hay, gần đây, một số nghiên cứu về việc thiết kế các vi mạch có cấu trúc dựa trên hệ thần kinh của người (neuromorphic chips) đã cho kết quả tốt trong các bài toán học máy hoặc xử lý lượng khối lượng dữ liệu lớn. 3) Suy nghĩ hợp lý Thực tế cho thấy con người bị chi phối bởi tâm lý, cảm xúc. Do vậy, không phải lúc nào con người cũng suy nghĩ và hành động theo hướng đạt tới kết quả tốt. Từ đây xuất hiện cách tiếp cận theo hướng xây dựng các hệ thống cho phép đạt tới kết quả tốt mà không cần học 8 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giới thiệu chung theo con người. Cách tiếp cận này được gọi là suy nghĩ hợp lý và hành động hợp lý. Trước hết là suy nghĩ hợp lý. Một cách tiếp cận tiêu biểu của suy nghĩ hợp lý là xây dựng những hệ thống có khả năng lập luận dựa trên việc sử dụng các hệ thống hình thức như logic. 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 logic để biểu diễn bài toán và giải quyết bằng suy diễn logic. Một số hệ thống logic cho phép biểu diễn mọi loại đối tượng và quan hệ giữa các đối tượng đó. Sau khi đã biểu diễn dưới dạng logic, có thể xây dựng chương trình để giải quyết các bài toán về suy diễn và lập luận. 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 logic để 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 logic đòi hỏi khối lượng tính toán lớn khi sử dụng trong thực tế và rất khó để triển khai cho các bài toán thực. 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 luận) hợp lý hoặc không. Trong một số trường hợp, để quyết định hành động thế nào, cần dựa trên việc suy luận hợp lý. Tuy nhiên, 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. Các hệ thống hành động hợp lý có thể sử dụng cả hai cách tiếp cận dựa trên suy diễn và dựa trên phản xạ để đạt được kết quả tốt. Hệ thống có khả năng hành động hợp lý có thể bao gồm suy diễn hoặc không, có thể dựa trên cách suy nghĩ giống người hoặc không, có thể bao gồm cả các kỹ thuật dùng để vượt qua phép thử Turing. Do vậy, cách tiếp cận này được coi là tổng quát và bao gồm các cách tiếp cận khác. Hiện có nhiều ý kiến coi hệ thống trí tuệ nhân tạo là các hệ thống dạng này. Tóm tắt Các phân tích ở trên cho thấy một số cách tiếp cận chính trong định nghĩa trí tuệ nhân tạo: - Lấy con người làm tiêu chuẩn, nghiên cứu tâm lý và thần kinh học để mô phỏng nhận thức con người, dựa trên đó xây dựng hệ thống trí tuệ nhân tạo. - Lấy kết quả làm tiêu chuẩn, không nhất thiết phải xây dựng hệ thống mô phỏng người. - Lấy hành vi và hành động làm mục đích, có thể có quá trình lập luận để hướng dẫn hành động hoặc không. 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 trí tuệ nhân tạo 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): 9 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giới thiệu chung a. Giai đoạn tiền khởi đầu (1943-1955) Mặc dù chưa có khái niệm chính thức về trí tuệ nhân tạo, 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ề trí tuệ nhân tạo 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 trí tuệ nhân tạo: “artificial intelligence”. Đa số những người tham gia hội thảo này, bao gồm John McCarthy, Marvin Minsky, Allen Newell, và Herbert Simon, sau đó đã trở thành những chuyên gia tiên phong trong các nghiên cứu về trí tuệ nhân tạo. Điểm quan trọng nhất của hội thảo này là đưa ra một số đề xuất và hình dung về trí tuệ nhân tạo. Các đề xuất này vượt ra ngoài khuôn khổ các lĩnh vực nghiên cứu đã hình thành trước đó như lý thuyết điều khiển, vận trù học, lý thuyết ra quyết định. Chính các đề xuất mới này đã đưa trí tuệ nhân tạo thành một lĩnh vực khoa học mới với đối tượng và phương pháp nghiên cứu riêng của mình. 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 trí tuệ nhân tạo, đượ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 (GPS) 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. Chẳng hạn, trong lớp bài toán mà GPS có thể giải quyết, việc chia bài toán thành các bài toán con và thứ tự các bước giải được tiến hành tương tự với con người khi giải quyết cùng bài toán. Chương trình Logic Theorist đã chứng minh được 38 trong số 52 định lý từ một sách giáo khoa toán, trong đó có định lý về tam giác cân được chứng minh theo cách ngắn hơn cách truyền thống. - Năm 1952, Arthur Samuel xây dựng một số chương trình chơi cờ đam (checkers). Chương trình có khả năng học và đánh thắng các đối thủ là người chơi cờ đam nghiệp dư. Điểm đặc biệt của chương trình này là khả năng tự học từ kinh nghiệm. Nhờ khả năng học, chương trình có thể thắng cả người đã tạo ra nó. - 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 trí tuệ nhân tạo. - Cũng trong những năm này, Minsky khởi xướng việc giải quyết những vấn đề có miền giới hạn hẹp và cần tới tri thức khi giải quyết. Các bài toán có miền hẹp như vậy được gọi là thế giới nhỏ (microworld). Chẳng hạn, trong lĩnh vực hẹp về giải tích, chương trình SAINT do James Slagle viết năm 1963 có thể giải các bài toán tích phân ở mức độ sinh viên năm thứ nhất đại học. 10 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giới thiệu chung - 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 của Bernie Widrow (1962), Perceptron của Rosenblatt (1962), cho phép giải quyết nhiểu bài toán học máy. Trong năm 1962, các nghiên cứu đã chứng minh khả năng học của mạng nơ ron, theo đó có thể thay đổi trọng số kết nối của các nơ ron để phù hợp với bất cứ thong tin đầu vào nào. - Năm 1965, John Alan Robinson phát minh ra cách chứng minh và suy diễn bằng cách sử dụng phép giải cho logic vị từ. Đây là phương pháp quan trọng, cho phép chương trình máy tính thực hiện lập luận và suy diễn tự động một cách hiệu quả trong trường hợp tri thức được biểu diễn bằng logic. c. Một số khó khăn và giai đoạn trầm lắng Sau một số thành công ban đầu, đã có những dự báo lạc quan về khả năng xây dựng các hệ thống thông minh trong tương lai gần. Một số nhà khoa học dự báo về khả năng tạo ra các hệ thống thông minh trong vòng 10 tới vài chục năm. Tuy nhiên, sau giai đoạn phát triển mạnh lúc đầu, vào đầu những năm bẩy mươi, các nhà khoa học bắt đầu nhận ra một số khó khăn, đòi hỏi cách tiếp cận thực tế hơn khi nghiên cứu trí tuệ nhân tạo. Thứ nhất, cách tiếp cận thời kỳ đầu thường sử dụng các biến đổi cú pháp đơn giản và không quan tâm tới tri thức về bài toán cần giải quyết. Ví dụ, khi xây dựng các hệ thống dịch máy, nhiều người kỳ vọng có nếu có từ điển và biết cách lắp ghép các từ để tạo thành câu là có thể dịch tự động. Trong khi đó trên thực tế, để dịch được, người dịch cần có hiểu biết nhất định về lĩnh vực được đề cập đến để thể hiện lại nội dung cần dịch trên ngôn ngữ đích. Các dự án dịch tự động từ tiếng Nga sang tiếng Anh do Bộ quốc phòng Mỹ tài trợ đã thất bại do cách tiếp cận đơn giản lúc đầu. Thứ hai, nhiều hệ thống trí tuệ nhân tạo thời kỳ đầu sử dụng việc tìm kiếm các hành động dẫn tới lời giải. Với bài toán kích thước nhỏ, các kỹ thuật tìm kiếm đơn giản cho kết quả tốt. Tuy nhiên, khi kích thước bài toán tăng lên, số tổ hợp cần xem xét tăng nhanh, vượt khả năng xử lý của máy tính. Hiệu ứng này được gọi là sự “bùng nổ tổ hợp” và chỉ được quan tâm đúng mức sau khi lý thuyết về độ phức tạp tính toán ra đời. Do các khó khăn nói trên, một số báo cáo bi quan về triển vọng trí tuệ nhân tạo đã được trình lên chính phủ các nước như Mỹ, Anh, dẫn tới việc các chính phủ ngừng cấp kinh phí nghiên cứu cho lĩnh vực này. Đây cũng là giai đoạn khó khăn trong lịch sử phát triển trí tuệ nhân tạo, kéo dài trong khoảng 1974 – 1980. Giai đoạn này được gọi là mùa đông trí tuệ nhân tạo (AI winter), lấy nguyên mẫu từ khái niệm mùa đông hạt nhân, là kết quả mô phỏng khí hậu trái đất lạnh lẽo sau khi xẩy ra chiến tranh hạt nhân. Một giai đoạn thứ hai cũng được gọi là mùa đông trí tuệ nhân tạo là giai đoạn 1987- 1993. Giai đoạn trì trệ này gắn với sự đi xuống của thị trường các hệ chuyên gia và thất bại của dự án máy tính thế hệ năm do chính phủ Nhật Bản tài trợ. d. Hệ thống dựa trên tri 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ố hạn chế 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. Điển hình của hệ thống dựa trên tri thức là các hệ chuyên gia (expert systems). 11 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giới thiệu chung Hệ chuyên gia là các hệ thống có khả năng ra quyết định tương tự chuyên gia trong lĩnh vực hẹp của mình. Hệ thống loại này được xây dựng để giải quyết những vấn đề phức tạp bằng cách lập luận trên tri thức nhận được từ các chuyên gia. Chẳng hạn, một bác sĩ chuyên khoa giỏi có thể mô tả các quy tắc chẩn đoán bệnh trong chuyên khoa của mình. Các quy tắc đó chính là tri thức cần thiết khi chẩn đoán bệnh. Thông thường, tri thức được biểu diễn dưới dạng các luật “Nếu…Thì…”. Hệ chuyên gia thường gồm cơ sở tri thức chứa các luật như vậy và mô tơ suy diễn giúp tìm ra lời giải từ tri thức và thông tin về trường hợp đang có. Sau đây là ví dụ một số hệ thống như vậy: - DENDRAL (năm 1967) 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ử hữu cơ. Chương trình làm việc dựa trên các luật do chuyên gia trong lĩnh vực hóa học và vật lý 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 (1974), hệ chuyên gia cho phép chẩn đoán bệnh nhiễm trùng máu. Với khoảng 450 luật do chuyên gia cung cấp, hệ thống có chất lượng chẩn đoán tương đương bác sĩ giỏi 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. Hệ chuyên gia cho phép giải quyết một phần hạn chế của các hệ thống đơn giản không dựa trên tri thức trước đó. Một số hệ chuyên gia đã được thương mại hoá và đem lại doanh thu cho lĩnh vực trí tuệ nhân tạo. Cũng trong giai đoạn này, vào năm 1972 Alain Colmerauer đã phát triển ngôn ngữ Prolog (viết tắt của logic programming tức là lập trình logic) phục vụ việc biểu diễn tri thức dưới dạng tương tự logic vị từ và lập luận trên tri thức đó. Prolog cùng với Lisp trở thành hai ngôn ngữ được dùng nhiều nhất trong trí tuệ nhân tạo. e. Trí tuệ nhân tạo 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, trí tuệ nhân tạo rơi vào một giai đoạn trì trệ, không có những bước tiến đáng kể (mùa đông trí tuệ nhân tạo thứ hai). 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 nay, 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. Đặc biệt, trong khoảng gần 10 năm gần đây, các mạng nơ ron nhân tạo nhiều lớp được gọi là mạng sâu (deep network) đang được đặc biệt quan tâm do có độ chính xác rất tốt trong các ứng dụng nhận dạng âm thanh, hình ảnh, xử lý ngôn ngữ tự nhiên. Vào năm 1981, chính phủ Nhật Bản khởi động chương trình xây dựng máy tính thế hệ 5. Mục đích của chương trình là xây dựng các máy tính thông minh chạy trên ngôn ngữ Prolog. Chính phủ Mỹ và Anh cũng có những dự án tương tự nhưng quy mô nhỏ hơn. Mặc dù các chương trình này đều không đạt được mục tiêu đề ra những đã giúp chấm dứt mùa đông trí tuệ nhân tạo lần thứ nhất. f. Trí tuệ nhân tạo chính thức trở thành ngành khoa học (1987 đến nay) 12 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giới thiệu chung Trong giai đoạn trước, chủ đề nghiên cứu chủ yếu có tính thăm dò và tìm kiếm định hướng. Các phương pháp nghiên cứu về trí tuệ nhân tạo cũng không bị giới hạn nhiều trong các lý thuyết có sẵn. Nhiều chủ đề nghiên cứu được đề xuất hoàn toàn mới và phương pháp giải quyết cũng tương đối tự do, không dựa trên các lý thuyết hay kết quả khoa học đã có. Mục tiêu của trí tuệ nhân tạo giai đoạn đầu là vượt ra ngoài khuôn khổ các lĩnh vực nghiên cứu đã có như lý thuyết điều khiển hay thống kê, do vậy nhiều nghiên cứu không đòi hỏi phải dựa trên cơ sở lý thuyết đã phát triển trong các lĩnh vực này. Bắt đầu từ giai đoạn này (1987), trí tuệ nhân tạo đã 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ê. Các vấn đề nghiên cứu cũng gắn nhiều với ứng dụng và đời sống, thay vì những ví dụ mang tính minh hoạ như trong các giai đoạn trước. Nhiều phát minh trước đây của trí tuệ nhân tạo 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. Nhờ 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. Tương tự như vậy, một ví dụ khác là cách tiếp cận với bài toán nhận dạng tiếng nói. Trong giai đoạn đầu, bài toán này được tiếp cận theo một số cách tương đối tự do, hướng vào việc giải quyết một số trường hợp riêng với phạm vi hạn chế, và không dựa trên các lý thuyết đã có. Hiện nay, đa số giải pháp nhận dạng tiếng nói được xây dựng trên các mô hình thống kê như mô hình Markov ẩn (Hidden Markov Models), hay các mạng nơ ron nhiều lớp. Hiệu quả của các giải pháp này có thể giải thích dựa trên lý thuyết thống kê, học máy và các phương pháp tối ưu đã tồn tại và được kiểm chứng từ lâu. g. Cách tiếp cận dựa trên dữ liệu, sử dụng khối lượng dữ liệu lớn (2001 đến nay) Trong các giai đoạn trước, việc phát triển trí tuệ nhân tạo chủ yếu tập trung vào xây dựng thuật toán và các hệ thống dựa trên tri thức chuyên gia. Gần đây, do sự xuất hiện của Internet, thương mại điện tử, và một số lĩnh vực khoa học như sinh học phân tử, lượng dữ liệu số hóa được tạo ra tăng rất nhanh. Nhiều nghiên cứu cũng cho thấy việc sử dụng dữ liệu hợp lý quan trọng hơn việc xây dựng các thuật toán phức tạp. Một trong những ví dụ là tiến bộ của hệ thống dịch tự động của Google, được xây dựng dựa trên việc thống kê số lượng lớn các văn bản đơn ngữ và song ngữ, thay vì sử dụng luật và quy tắc ngữ pháp như trước đây. Trong vài năm gần đây, xu hướng sử dụng dữ liệu lớn (big data), tức là các kỹ thuật ra quyết định dựa trên việc phân tích lượng lớn dữ liệu với bản chất đa dạng và thay đổi nhanh theo thời gian đang được coi là một trong những xu hướng có ảnh hưởng quan trọng tới sự phát triển và ứng dụng của trí tuệ nhân tạo. Nhiều ứng dụng quan trọng dựa trên dữ liệu lớn như các hệ thống hỗ trợ khuyến nghị của Amazon, ứng dụng trợ giúp Siri của Apple, chương trình dịch tự động và nhận dạng giọng nó của Google, chương trình trò chơi Watson của IBM là những ví dụ thành công điển hình của xu hướng này. Thành công của việc sử dụng dữ liệu lớn cho thấy có thể giải quyết một vấn đề quan trọng của trí tuệ nhân tạo: đó là việc thu thập đủ lượng tri thức cần thiết cho hệ thống. Thay vì thu thập bằng tay như trước đây, tri thức có thể được tổng hợp, hay “học” từ dữ liệu. Đây cũng là hứa hẹn cho một giai đoạn phát triển mạnh các ứng dụng của trí tuệ nhân tạo. 13 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giới thiệu chung 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 và chuyên sâu 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. Một số lĩnh vực chuyên sâu được hình thành để giải quyết một lớp bài toán. Một số lĩnh vực chuyên sâu khác tập trung vào các hướng tiếp cận hay các kỹ thuật. Một số lĩnh vực nghiên cứu lại xoay quanh các ứng dụng cụ thể. Trong khi nhiều lĩnh vực nghiên cứu nhỏ có liên quan mật thiết đến nhau thì có nhiều lĩnh vực khác rất xa nhau, cả về mục tiêu, phương pháp và cộng đồng nghiên cứu. 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), lập luận (reasoning), và hành động (action). Dưới đây là một số lĩnh vực nghiên cứu của trí tuệ nhân tạo đượ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 biến âm thanh (microphone), cảm biến siêu âm, radar, cảm biến gia tốc, 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 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 được nghiên cứu và trong khuôn khổ các lĩnh vực sau. Thị giác máy (computer vision) Đây là lĩnh vực thuộc trí tuệ nhân tạo có mục đích nghiên cứu về việc thu nhận, xử lý, phân tích, nhận dạng thông tin hình ảnh thu được từ các cảm biến hình ảnh như camera. Mục đích của thị giác máy là biến thông tin thu được thành biểu diễn mức cao hơn để máy tính sau đó có thể hiểu được, chẳng hạn từ ảnh chụp văn bản cần trả về mã UNICODE của các chữ in trên văn bản đó. Biểu diễn ở mức cao hơn của thông tin từ cảm biến hình ảnh sau đó có thể sử dụng để phục vụ quá trình ra quyết định. Thị giác máy tính bao gồm một số bài toán chính sau: nhận dạng mẫu (pattern recognition), phân tích chuyển động (motion analysis), tạo lập khung cảnh 3D (scene reconstruction), nâng cao chất lượng ảnh (image restoration). Nhận dạng mẫu là lĩnh vực nghiên cứu lớn nhất trong phạm vi thị giác máy. Bản thân nhận dạng mẫu được chia thành nhiều bài toán nhỏ và đặc thù hơn như bài toán nhận dạng đối tượng nói chung, nhận dạng các lớp đối tượng cụ thể như nhận dạng mặt người, nhận dạng vân tay, nhận dạng chữ viết tay hoặc chữ in. Nhận dạng đối tượng là phát hiện ra đối tượng trong ảnh hoặc video và xác định đó là đối tượng nào. Trong khi con người có thể thực hiện việc này tương đối đơn giản thì việc nhận dạng tự động thường khó hơn nhiều. Hiện máy tính chỉ có khả năng nhận dạng một số lớp đối tượng nhất định như chữ in, mặt người nhìn thẳng, với độ chính xác gần với con người. Xử lý ngôn ngữ tự nhiên (natural language processing) Đây là lĩnh vực nghiên cứu với có mục đích 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. Chẳng hạn, thay vì gõ các lệnh quy ước, ta có thể ra lệnh bằng cách nói với máy tính như với 14 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giới thiệu chung người thường. Do đối tượng giao tiếp của hệ thống trị tuệ nhân tạo thường là con người, khả năng tiếp nhận thông tin và phản hồi dưới dạng lời nói hoặc văn bản theo cách diễn đạt của người sẽ rất có ích trong những trường hợp như vậy. Xử lý ngôn ngữ tự nhiên bao gồm ba giai đoạn chính: nhận dạng tiếng nói (speech recognition), xử lý thông tin đã được biểu diễn dưới dạng văn bản, và biến đổi từ văn bản thành tiếng nói (text to speech). Nhận dạng tiếng nói là quá trình biến đổi từ tín hiệu âm thanh của lời nói thành văn bản. Nhận dạng tiếng nói còn có các tên gọi như nhận dạng tiếng nói tự động (automatic speech recognition) hay nhận dạng tiếng nói bằng máy tính, hay biến đổi tiếng nói thành văn bản (speech to text – STT). Nhận dạng tiếng nói được thực hiện bằng cách kết hợp kỹ thuật xử lý tín hiệu âm thanh với kỹ thuật nhận dạng mẫu, chẳng hạn bằng cách sử dụng các mô hình thống kê và học máy. Xử lý thông tin văn bản được diễn đạt bằng ngôn ngữ tự nhiên như tiếng Việt hay tiếng Anh bao gồm một số bài toán và ứng dụng chính sau: - Phân tích từ loại, ngữ pháp. Nhận đầu vào là một câu, trả về từ loại (động từ, tính từ v.v.) của các từ trong câu; xây dựng cây cú pháp của câu đó tức là xác định các thành phần như chủ ngữ, vị ngữ và quan hệ giữa các thành phần. Do ngôn ngữ tự nhiên thường có tính nhập nhằng nên từ một câu có thể có nhiều cách phân tích. Đây là bài toán cơ sở cho các bài toán xử lý ngô ngữ tự nhiên khác. - Hiểu ngôn ngữ tự nhiên hay phân tích ngữ nghĩa. Biến đổi các câu trên ngôn ngữ tự nhiên thành các biểu diễn như biểu thức trên logic vị từ sao cho máy tính có thể thực hiện biến đổi hoặc lập luận trên đó. Các biểu diễn này cần tương ứng với ngữ nghĩa trong thế giới thực của bài toán. - Dịch tự động hay dịch máy. Tự động biến đổi các văn bản trên ngôn ngữ tự nhiên này sang ngôn ngữ tự nhiên khác, ví dụ từ tiếng Việt sang tiếng Anh và ngược lại. Đây là bài toán có tính ứng dụng cao nhưng là bài toán khó do đòi hỏi khả năng thực hiện các bài toán xử lý ngôn ngữ tự nhiên khác cộng với khả năng sử dụng tri thức về các lĩnh vực liên quan tới nội dung văn bản cần dịch. - Trả lời tự động (question answering). Tự động sinh ra câu trả lời cho các câu hỏi của con người. Ví dụ hệ thống dạng này là chương trình Watson của IBM cho phép trả lời các câu hỏi trong trò chơi Jeopardy tương tự trò Ai là triệu phú, hay trợ lý ảo Siri của iPhone. Hệ thống dạng này thường đòi hỏi khả năng hiểu câu hỏi, cơ sở tri thức liên quan, và tổng hợp câu trả lời. - Tách thông tin (information extraction). Tách thông tin có ngữ nghĩa từ văn bản, chẳng hạn tên riêng, thời gian, quan hệ giữa các thực thể, các thông tin có ý nghĩa khác và lưu các thông tin này dưới dạng thuận tiện cho việc xử lý bằng máy tính. Bài toán xác định và tách tên riêng được gọi là nhận dạng thực thể có tên (Named Entity Recognition). Kết quả tách thông tin được sử dụng trong nhiều bài toán khác, chẳng hạn để xây dựng cơ sở tri thức cho các hệ thống trả lời tự động. - Tổng hợp ngôn ngữ tự nhiên. Biến đổi từ các thông tin tiện dùng cho máy tính, chẳng hạn thông tin trong cơ sở dữ liệu, thành các câu trên ngôn ngữ tự nhiên của người với mục đích giúp việc giao tiếp của máy tính với người được tự nhiên và thuận lợi hơn. 15 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giới thiệu chung Đây là bài toán ngược với bài toán hiểu nhận dạng tiếng nói và hiểu ngôn ngữ tự nhiên. b) Lập luận và suy diễn Sau khi cảm nhận được thông tin về môi trường xung quanh, hệ thống cần có cơ chế để đưa ra được quyết định phù hợp. Quá trình ra quyết định thường dựa trên việc kết hợp thông tin cảm nhận được với tri thức có sẵn về thế giới xung quanh. Việc ra quyết định dựa trên tri thức được thực hiện nhờ lập luận hay suy diễn. Cũng có những trường hợp hệ thống không thực hiện suy diễn mà dựa trên những kỹ thuật khác như tìm kiếm hay tập hợp các phản xạ hoặc hành vi đơn giản. Thành phần lập luận và ra quyết định đượ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) Nhiều bài toán của trí tuệ nhân tạo đòi hỏi lập luận dựa trên hình dung về thế giới xung quanh. Để lập luận được, 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 logic hoặc ngôn ngữ trí tuệ nhân tạo nào đó. Thông thường, hệ thống cần có tri thức về: đối tượng hoặc thực thể, tính chất của chúng, phân loại và quan hệ giữa các đối tượng, tình huống, sự kiện, trạng thái, thời gian, nguyên nhân và hiệu quả, tri thức về tri thức (chúng ta biết về tri thức mà người khác có) v.v. Trong phạm vi nghiên cứu về biểu diễn tri thức, một số phương pháp biểu diễn đã được phát triển và được áp dụng như: logic, mạng ngữ nghĩa, Frame, các luật (chẳng hạn luật Nếu…Thì …), bản thể học (ontology). Biểu diễn tri thức dùng trong máy tính thường gặp một số khó khăn sau. Thứ nhất, lượng tri thức mà mỗi người bình thường có về thế giới xung quanh là rất lớn. Việc xây dựng và biểu diễn lượng tri thức lớn như vậy đòi hỏi nhiều công sức. Hiện nay đang xuất hiện hướng tự động thu thập và xây dựng cơ sở tri thức tự động từ lượng dữ liệu lớn, thay vì thu thập bằng tay. Cách xây dựng tri thức như vậy được nghiên cứu nhiều trong khuôn khổ khai phá dữ liệu (data mining) hay hiện nay được gọi là dữ liệu lớn (big data) Điển hình của cách tiếp cận này là hệ thống Watson của IBM (sẽ được nhắc tới ở bên dưới). Thứ hai, tri thức trong thế giới thực ít khi đầy đủ, chính xác và nhất quán. Con người có thể sử dụng hiệu quả các tri thức như vậy, trong khi các hệ thống biểu diễn tri thức như logic gặp nhiều khó khăn. Thứ ba, một số tri thức khó biểu diễn dưới dạng biểu tượng mà tồn tại như các trực giác của con người. 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. Chẳng hạn các bài toán tìm đường đi, bài toán tìm trạng thái thoả mãn ràng buộc. Nhiều bài toán khác của trí tuệ nhân tạo cũng có thể giải quyết bằng tìm kiếm. Chẳng hạn, lập luận logic có thể tiến hành bằng cách tìm các đường đi cho phép dẫn từ các tiền đề tới các kết luận. Trí tuệ nhân tạo nghiên cứu cách tìm kiếm khi số trạng thái trong không gian quá lớn và không thể thực hiện tìm kiếm bằng cách vét cạn. Trong khuôn khổ trí tuệ nhân tạo đã phát triển một số phương pháp tìm kiếm riêng như tìm kiếm heuristic, tìm kiếm cục bộ, bao gồm các thuật toán tìm kiếm tiến hoá. 16 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giới thiệu chung Lập luận, suy diễn (reasoning hay inference) Lập luận là quá trình sinh ra kết luận hoặc tri thức mới từ những tri thức, sự kiện và thông tin đã có. Trong giai đoạn đầu, nhiều kỹ thuật lập luận tự động dựa trên việc mô phỏng hoặc học tập quá trình lập luận của con người. Các nghiên cứu về sau đã phát triển nhiều kỹ thuật suy diễn hiệu quả, không dựa trên cách lập luận của người. Điển hình là các kỹ thuật chứng minh định lý và suy diễn logic. Lập luận tự động thường dựa trên tìm kiếm cho phép tìm ra các liên kết giữa tiên đề và kết quả. Việc suy diễn tự động thường gặp phải một số khó khăn sau. Thứ nhất, với bài toán kích thước lớn, số tổ hợp cần tìm kiếm khi lập luận rất lớn. Vấn đề này được gọi là “bùng nổ tổ hợp” và đòi hỏi có phát triển các kỹ thuật với độ phức tạp chấp nhận được. Thứ hai, lập luận và biểu diễn tri thức thường gặp vấn đề thông tin và tri thức không rõ ràng, không chắc chắn. Hiện nay, một trong những cách giải quyết vấn đề này là sử dụng lập luận xác suất, sẽ được trình bầy trong chương 4 của giáo trình. Thứ ba, trong nhiều tình huống, con người có thể ra quyết định rất nhanh và hiệu quả thay vì lập luận từng bước, chẳng hạn co tay lại khi chạm phải nước sôi. Hệ thống trí tuệ nhân tạo cần có cách tiếp cận khác với lập luận truyền thống cho những trường hợp như vậy. Học máy (machine learning) Học máy hay học tự động là khả năng của hệ thống máy tính tự cải thiện mình nhờ sử dụng dữ liệu và kinh nghiệm thu thập được. Học là khả năng quan trọng trong việc tạo ra tri thức của người. Do vậy, đây là vấn đề được quan tâm nghiên cứu ngay từ khi hình thành trí tuệ nhân tạo. Hiện nay, đây là một trong những lĩnh vực được quan tâm nghiên cứu nhiều nhất với rất nhiều kết quả và ứng dụng. Học máy bao gồm các dạng chính là học có giám sát, học không giám sát, và học tăng cường. Trong học có giám sát, hệ thống được cung cấp đầu vào, đầu ra và cần tìm quy tắc để ánh xạ đầu vào thành đầu ra. Trong học không giám sát, hệ thống không được cung cấp đầu ra và cần tìm các mẫu hay quy luật từ thông tin đầu vào. Trong học tăng cường, hệ thống chỉ biết đầu ra cuối cùng của cả quá trình thay vì đầu ra cho từng bước cụ thể. Chi tiết về ba dạng học này được trình bầy trong chương 5. Học máy được phát triển trong khuôn khổ cả khoa học máy tính và thống kê. Rất nhiều kỹ thuật học máy có nguồn gốc từ thống kê nhưng được thay đổi để trở thành các thuật toán có thể thực hiện hiệu quả trên máy tính. Học máy hiện là kỹ thuật chính được sử dụng trong thị giác máy, xử lý ngôn ngữ tự nhiên, khai phá dữ liệu và phân tích dữ liệu lớn. Lập kế hoạch (planning) Lập kế hoạch và thời khoá biểu tự động, hay đơn giản là lập kế hoạch, 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. Lấy ví dụ một rô bốt nhận nhiệm vụ di chuyển một vật tới một vị trí khác. Kế hoạch thực hiện bao gồm xác định các bước để tiếp cận vật cần di chuyển, nhấc vật lên, xác định quỹ đạo và các bước di chuyển theo quỹ đạo, đặt vật xuống. 17 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giới thiệu chung Khác với lý thuyết điều khiển truyền thống, bài toán lập kế hoạch thường phức tạp, lời giải phải tối ưu theo nhiều tiêu chí. Việc lập kế hoạch có thể thực hiện trước đối với môi trường không thay đổi, hoặc thực hiện theo thời gian với môi trường động. Lập kế hoạch sử dụng các kỹ thuật tìm kiếm và tối ưu, các phương pháp quy hoạch động để tìm ra lời giải. Một số dạng biểu diễn và ngôn ngữ riêng cũng được phát triển để thuận lợi cho việc mô tả yêu cầu và lời giải. 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. Tổng hợp ngôn ngữ tự nhiên và tiếng nói. Các kỹ thuật này đã được nhắc tới trong phần xử lý ngôn ngữ tự nhiên ở trên. 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. Đây là lĩnh vực nghiên cứu giao thoa giữa cơ khí, điện tử, và trí tuệ nhân tạo. Bên cạnh kỹ thuật cơ khí để tạo ra các cơ chế vật lý, chuyển động, cần có thuật toán và chương trình điểu khiển hoạt động và chuyển động cho các cơ chế đó. Chẳng hạn, với cánh tay máy, cần tính toán quỹ đạo và điều khiển cụ thể các khớp nối cơ khí khi muốn di chuyển tay tới vị trí xác định và thực hiện hành động nào đó. Đây là những thành phần của kỹ thuật rô bốt mà trí tuệ nhân tạo có đóng góp chính. Ngoài ra, việc xây dựng những rô bốt thông minh chính là xây dựng các hệ thống trí tuệ nhân tạo hoàn chỉnh. 1.3.2. Một số ứng dụng và thành tựu a. Các chương trình trò chơi Xây dựng chương trình có khả năng chơi những trò chơi trí tuệ là lĩnh vực có nhiều thành tựu của trí tuệ nhân tạo. Với những trò chơi tương đối đơn giản như cờ ca rô hay cờ thỏ cáo, máy tính đã thắng người từ cách đây vài thập kỷ. Đối với những trò chơi phức tạp hơn, các hệ thống trí tuệ nhân tạo cũng dần đuổi kịp và vượt qua con người. Sự kiện quan trọng thường được nhắc tới là vào tháng 5 năm 1997 chương trình cờ vua Deep Blue của IBM đã thắng vô địch cờ vua thế giới lúc đó là Gary Kasparov. Trong vòng đấu kéo dài 6 ván, Deep Blue thắng Kasparov với điểm số 3.5 : 2.5. Đây là lần đầu tiên máy tính thắng đương kim vô địch cờ vua thế giới. Một trường hợp tiêu biểu khác là hệ thống trả lời tự động Watson cũng của IBM đã chiến thắng hai quán quân của Jeopardy trong trò chơi này vào năm 2011. Jeopardy là trò chơi hỏi đáp trên truyền hình Mỹ, tương tự “Ai là triệu phú” trên truyền hình Việt Nam nhưng trong đó ba người chơi phải thi với nhau không những trả lời đúng mà còn phải nhanh. Watson là hệ thống hỏi đáp do IBM xây dựng dựa trên việc thu thập và phân tích thông tin từ khoảng 200 triệu trang Web, trong đó có toàn bộ Wikipedia. Trong một cuộc đấu với hai cựu quán quân Jeopardy, Watson đã giành thắng lợi và phần thưởng 1 triệu USD. Các kỹ thuật sử dụng trong Watson như thu thập thông tin, phát hiện tri thức, hiểu ngôn ngữ tự nhiên, tìm kiếm, đã được IBM thương mại hóa và có thể sử dụng trong nhiều ứng dụng. b. Nhận dạng tiếng nói 18 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giới thiệu chung Nhận dạng tiếng nói là biến đổi từ âm thanh tiếng nói thành các văn bản. Hiện người dùng công cụ tìm kiếm Google có thể đọc vào câu truy vấn thay cho việc gõ từ khóa như trước. Các điện thoại di động thông minh cũng có khả năng nhận dạng giọng nói và trả lời các câu hỏi. Ví dụ điển hình là chương trình trợ giúp Siri trên điện thoại thông minh của Apple (sử dụng công nghệ nhận dạng tiếng nói của hãng Nuance) hay hệ thống Google Now. Chất lượng nhận dạng giọng nói đang được cải thiện và tiến bộ rất nhanh trong vài năm gần đây. Các hệ thống nhận dạng tiếng nói hiện tại cho phép nhận dạng tới vài chục ngôn ngữ khác nhau và không phụ thuộc vào người nói (ở một mức độ nhất định). c. Thị giác máy tính Mặc dù nhiều ứng dụng của thị giác máy tính vẫn chưa đạt tới độ chính xác như người, nhưng trong một số bài toán, thị giác máy tính cho độ chính xác tương đương hoặc gần với khả năng của người. Tiêu biểu phải kể đến 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. Ứng dụng nhận dạng mặt người trên Facebook được dùng để xác định những người quen xuất hiện trong ảnh và gán nhãn tên cho người đó. Các ứng dụng nhận dạng hiện nay đang được cải thiện nhiều nhờ sử dụng kỹ thuật học sâu (deep learning), trong đó các mạng nơ ron có nhiều lớp được kết nối với nhau được sử dụng để phát hiện các đặc trưng của đối tượng ở mức từ đơn giản tới phức tạp. d. Các thiết bị tự lái Các thiết bị tự lái bao gồm máy bay, ô tô, tầu thủy, thiết bị thám hiểm vũ trụ có thể tự di chuyển mà không có sự điều khiển của người (cả điều khiển trực tiếp và điều khiển từ xa). Hiện ô tô tự lái đang được một số hãng công nghệ và các tổ chức khác nghiên cứu và phát triển, trong đó có những dự án nổi tiếng như xe tự lái của Google. Mặc dù tại thời điểm viết sách này mới chỉ có một mẫu xe duy nhất được thương mại hóa dùng cho các khu đi bộ và chỉ có thể chạy với tốc độ khoảng 20 km/giờ nhưng các dự báo cho thấy xe tự lái sẽ được thương mại hóa thành công trong vòng vài năm tới. Các thiết bị tự lái khác bao gồm cả các xem thám hiểm vũ trụ và hành tinh khác như xe thám hiểm sao Hỏa của NASA. e. 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ị với khả năng tương đương một bác sĩ giỏi trong lĩnh vực này. - XCON của DEC: hỗ trợ chọn cấu hình máy tính tự động. f. 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. Hệ thống dịch tự động của Google sử dụng các mô hình thống kê xây dựng từ các văn bản song ngữ và các văn bản đơn ngữ. Hệ thống này có khả năng dịch qua lại giữa vài chục ngôn ngữ. 19 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giới thiệu chung Các hệ thống hỏi đáp được đề cập tới trong phần về trò chơi và nhận dạng tiếng nói cũng thuộc loại ứng dụng xử lý ngôn ngữ tự nhiên. 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. Nhiều kỹ thuật xử lý ngôn ngữ tự nhiên đã được ứng dụng trong các ứng dụng rất thiết thực như các bộ lọc thư rác. Dịch vụ thư điện tử của Google, Microsoft, Yahoo đều có các bộ lọc thư rác với cơ chế học tự động và thích nghi với thay đổi của người phát tán. Khả năng phát hiện thư rác của các hệ thống này là rất cao, gần như tuyệt đối trong một số trường hợp. g. Lập kế hoạch, lập thời khóa biểu Kỹ thuật trí tuệ nhân tạo đượ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 trí tuệ nhân tạo. Đây là một kế hoạch lớn, liên quan tới khoảng 50000 thiết bị vận tải và người tại cùng một thời điểm. Kế hoạch bao gồm điểm xuất phát, điểm tới, thời gian, phương tiện và người tham gia sao cho không mâu thuẫn và tối ưu theo các tiêu chí. h. Rô bốt Một số rô bốt được xây dựng sao cho có hình dạng tương tự con người và khả năng toàn diện như thị giác máy, giao tiếp bằng ngôn ngữ tự nhiên, khả năng lập luận nhất định, khả năng di chuyển và thực hiện các hành động như nhẩy múa. Các rô bốt này chủ yếu được tạo ra để chứng minh khả năng của kỹ thuật rô bốt thay vì hướng vào ứng dụng cụ thể. Trong số này có thể kể tới rô bốt Asimo, rô bốt Nao. Bên cạnh đó, một số rô bốt không mô phỏng người nhưng được sử dụng trong đời sống hàng ngày hoặc các ứng dụng thực tế. Ví dụ, rô bốt Roomba của hãng iRobot có khả năng tự động di chuyển trong phòng, tránh vật cản, chui vào các ngóc ngách để lau sạch toàn bộ sàn. Số lượng rô bốt Roomba đã bán lên tới vài triệu bản. 1.3.3. Những vấn đề chưa được giải quyết Mặc dù đạt được nhiều thành tựu và có nhiều ứng dụng đáng kể, các hệ thống trí tuệ nhân tạo hiện nay chưa đạt được mức độ trí tuệ nhân tạo mạnh (strong AI) hay trí tuệ nhân tạo tổng quát (Artificial General Intelligence). Đây cũng được coi là vấn đề khó nhất và chưa được giải quyết. Trí tuệ nhân tạo mạnh là khái niệm để chỉ khả năng của máy tính thực hiện bất cứ công việc trí tuệ nào mà con người có thể thực hiện. Khái niệm trí tuệ mạnh được sử dụng để phân biệt với trí tuệ nhân tạo yếu (weak AI) hay trí tuệ nhân tạo ứng dụng (applied AI), tức là dùng máy tính để giải quyết từng bài toán ra quyết định hay lập luận đơn lẻ. Như vậy, trí tuệ nhân tạo mạnh đòi hỏi giải quyết đầy đủ các công việc trí tuệ như người trong khi trí tuệ nhân tạo yếu giải quyết bài toán cụ thể. Các khó khăn để đạt được trí tuệ nhân tạo tổng quát bao gồm khả năng thị giác máy, xử lý ngôn ngữ tự nhiên, khả năng xử lý các tình hướng mới, tình huống không ngờ tới khi giải quyết các bài toán thực tế. Đây là những lĩnh vực mà máy tính còn thua kém con người. Các hệ thống trí tuệ nhân tạo hiện nay có thể giải quyết tốt bài toán đặt ra trong một phạm vi hẹp. Tuy nhiên, khi gặp vấn đề thực tế ở phạm vi rộng hơn, hệ thống trí tuệ nhân tạo thường không thể xử lý được các tình huống mới, vượt ra ngoài ngữ cảnh ban đầu của bài toán. Ngược lại, 20 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giới thiệu chung con người có khả năng xử lý tốt hơn nhiều những trường hợp như vậy do có hiểu biết rộng về thế giới xung quanh. Việc trang bị cho máy tính lượng tri thức như con người hiện vẫn là vấn đề chưa được giải quyết. Để đánh giá hệ thống trí tuệ nhân tạo, có thể so sánh các hệ thống này với con người khi thực hiện từng bài toán trí tuệ cụ thể. Kết quả so sánh được chia thành các mức sau: - Tối ưu: hệ thống cho kết quả tối ưu, không thể tốt hơn nữa. - Tốt hơn người: hệ thống cho kết quả tốt hơn bất cứ người nào. - Tương đương người giỏi: hệ thống cho kết quả tương đương những người giỏi (nhất) và hơn đa số người còn lại. - Tương đương người: hệ thống cho kết quả tương đương đa số người. - Kém hơn người. Những bài toán trí tuệ trong đó hệ thống máy tính thực hiện kém hơn người là những bài toán cần tiếp tục giải quyết. Dưới đây là một số bài toán và mức độ so sánh giữa máy tính và người. - Rubik, cờ ca rô 3 ô: tối ưu. - Cờ vua: gần đạt mức tốt hơn người. Hệ thống Deep Blue đã thắng đương kim vô địch cờ vua thế giới Gary Kasparov. - Trả lời câu hỏi tự động: gần đạt mức tốt hơn người. Hệ thống IBM Watson đã thắng người trong trò chơi truyền hình Jeopardy. - Lái xe tự động: tương đương người. Một ví dụ là hệ thống lái xem tự động của Google có kết quả lái an toàn và êm ái hơn so với người. Tuy vậy, kết quả này mới chỉ trong các thử nghiệm tại Mỹ, nơi có hệ thống giao thông tốt. Chưa rõ hệ thống cho kết quả thế nào trong các điều kiện khác, ví dụ trong điều kiện giao thông tại Việt Nam. - Nhận dạng chữ in (theo chuẩn ISO 1073-1:1976, tức là các phông chữ đơn nét và không quá phức tạp): tương đương người. Các hệ thống OCR hiện nay có độ chính xác 99% hoặc hơn trên văn bản in bằng máy in la de. - Nhận dạng chữ viết tay: kém người. Mặc dù có nhiều tiến bộ, các hệ thống nhận dạng chữ viết tay tự động vẫn có độ chính xác kém hơn người với khoảng cách tương đối lớn. - Nhận dạng đối tượng: kém người. Trừ một số trường hợp đặc biệt như nhận dạng vân tay, tròng mắt, mặt người, khả năng nhận dạng đối tượng nói chung của máy tính hiện vẫn kém khá xa khả năng của người. - Dịch tự động: kém người. Mặc dù hiện nay, khả năng dịch tự động của máy kém con người trên từng cặp ngôn ngữ cụ thể nhưng những hệ thống dịch tự động như Google translate lại vượt từng người cụ thể về số lượng ngôn ngữ có thể dịch. - Nhận dạng tiếng nói: kém người. Trong vài năm gần đây, khả năng nhận dạng tiếng nói bằng máy tính đã có rất nhiều tiến bộ và được ứng dụng rộng rãi như các hệ thống Google Voice, hay Siri (dùng phần nhận dạng của hãng Nuance). Tuy nhiên, khả năng nhận dạng tự động vẫn kém khả năng con người. - Phân biệt nhập nhằng trong nghĩa từ và một số bài toán xử lý ngôn ngữ tự nhiên khá 21 CuuDuongThanCong.com https://fb.com/tailieudientucntt CHƯƠNG 2: GIẢI QUYẾT VẤN ĐỀ BẰNG TÌM KIẾM Chương này sẽ trình bầy về kỹ thuật giải quyết vấn đề bằng tìm kiếm, còn được gọi là tìm kiếm trong không gian trạng thái. Đây là các phương pháp được dùng phổ biến trong một lớp lớn các bài toán và là lớp kỹ thuật giải quyết vấn đề quan trọng, được nghiên cứu và ứng dụng nhiều của trí tuệ nhân tạo. Trong phạm vi chương, ta sẽ xem xét cách phát biểu một vấn đề dưới dạng bài toán tìm kiếm, trước khi chuyển sang các giải thuật đã được phát triển để giải quyết bài toán này. Các giải thuật tìm kiếm được chia thành ba nhóm lớn: tìm kiếm mù (không có thông tin), tìm kiếm heuristics (có thông tin), và tìm kiếm cục bộ. Giải thuật thuộc nhóm hai và nhóm ba, đặc biệt là nhóm ba, được sử dụng cho các bài toán thực tế với kích thước lớn. 2.1. GIẢI QUYẾT VẤN ĐỀ VÀ KHOA HỌC TRÍ TUỆ NHÂN TẠO Tại sao phải tìm kiếm Khi quan sát các bài toán trên thực tế, có thể nhận thấy một lớp lớn bài toán có thể phát biểu và giải quyết dưới dạng tìm kiếm, trong đó yêu cầu có thể là tìm những trạng thái, tính chất thỏa mãn một số điều kiện nào đó, hoặc tìm chuỗi hành động cho phép đạt tới trạng thái mong muốn. 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 lịch, hay thời khóa biểu: lập lịch 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 lịch 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: cần tìm đường đi từ điểm xuất phát tới đích, có thể thỏa mãn thêm 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. Các bài toán tìm kiếm mới có thể đưa về dạng bài toán tìm kiếm tổng quát và áp dụng thuật giải đã được xây dựng. Do tính quan trọng của lớp bài toán này, tìm kiếm đã được nghiên cứu từ rất sớm trong khuôn khổ toán rời rạc và lý thuyết giải thuật. Trong khuôn khổ trí tuệ nhân tạo, 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. Rất nhiều thuật toán tìm kiếm được phát triển trong khuôn khổ trí tuệ nhân tạo được phát triển dựa trên việc tìm hiểu quá trình giải quyết vấn đề của con người, hay CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm dựa trên sự tương tự với một số quá trình xẩy ra trong tự nhiên như quá trình tiến hóa, quá trình hình thành mạng tinh thể, cách thức di chuyển của một số loại côn trùng. 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 trí tuệ nhân tạo như lập kế hoạch, học máy, xử lý ngôn ngữ tự nhiên, suy diễn. Chẳng hạn, bài toán suy diễn có thể phát biểu như quá trình tìm ra chuỗi các luật suy diễn cho phép biến đổi từ quan sát ban đầu tới đích của quá trình suy diễn. Nhiều phương pháp học máy cũng coi quá trình học như quá trình tìm kiếm mô hình cho phép biểu diễn dữ liệu huấn luyện được dùng trong quá trình học. Lưu ý: cần phân biệt bài toán tìm kiếm được trình bầy trong chương này, còn được gọi là tìm kiếm trong không gian trạng thái, với bài toán tìm kiếm và thu hồi thông tin (information retrieval) được giải quyết trong các máy tìm kiếm (search engine) như Google, Yahoo, hay Bing. Trong bài toán thu hồi thông tin, các máy tìm kiếm cần tìm các văn bản, hình ảnh, tài liệu đa phương tiện thỏa mãn nhu cầu thông tin của người dùng. Việc này được thực hiện bằng các kỹ thuật khác với các kỹ thuật sẽ được trình bầy trong các phần dưới đây. Ngoài ra, cũng cần phân biệt bài toán tìm kiếm trong không gian trạng thái với các bài toán như tìm kiếm xâu tương tự, tìm kiếm k láng giềng gần nhất. Mặc dù cùng có tên là tìm kiếm nhưng những bài toán này có mục tiêu, tính chất và cách giải quyết khác với tìm kiếm trong không gian trạng thái được trình bầy ở chương này. 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 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 đề. Trong một số trường hợp, thủ tục tìm kiếm sẽ khảo sát và tìm ra chuỗi các hành động cho phép đạt tới trạng thái mong muốn và bản thân chuỗi hành động này là lời giải của bài toán, như trong bài toán tìm đường. 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. Để 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 năm 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 23 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm 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ể của 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 hay hàm chuyển tiếp. 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 cho trạng thái đó. Các trạng thái này được gọi là trạng thái hàng xóm hay láng giềng của n. • 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ố không âm c (x, y). Giá thành cụ thể được chọn tùy vào từng trường hợp và thể hiện mối quan tâm chính trong bài toán. Ví dụ, với cùng bài toán tìm đường đi, giá thành có thể tính bằng độ dài quãng đường, hay thời gian cần để di chuyển, hay giá thành nhiên liệu tiêu thụ. Giá trị c (x, y) được gọi là giá thành bước, từ giá thành bước có thể tính ra giá thành toàn bộ đường đi bằng cách lấy tổng các bước đi đã thực hiện. Với bài toán phát biểu như trên, lời giải là chuỗi chuyển động cho phép di chuyển từ trạng thái xuất phát tới trạng thái đích. Chất lượng lời giải được tính bằng giá thành đường đi, tức là tổng giá thành cần để thực hiện chuỗi chuyển động này, giá thành càng thấp thì lời giải càng tốt. Cũng có những trường hợp ta không quan tâm tới chuỗi chuyển động mà chỉ quan tâm tới trạng thái đích, ví dụ trong bài toán lập lịch. Trong trường hợp đó, thuật toán tìm kiếm cần trả về lời giải là trạng thái đích, thay về trả về chuỗi chuyển động. Cần lưu ý rằng, không gian trạng thái có thể cho một cách tường minh, bằng cách liệt kê các trạng thái như trong trường hợp bài toán tìm đường với mỗi địa điểm là một trạng thái. Tuy nhiên, trong nhiều trường hợp, không gian trạng thái được cho một cách không tường minh thông qua trạng thái xuất phát và các chuyển động: khi đó không gian trạng thái là tập hợp tất cả các trạng thái có thể đạt tới từ trạng thái xuất phát bằng cách áp dụng mọi tổ hợp chuyển động. Trong trường hợp này, không gian trạng thái có thể là hữu hạn hoặc vô hạn. 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 những ví dụ sau. Một số 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. Một số khác là những bài toán thực tế, có nhiều ứng dụng. 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. 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. 24 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm 3 1 6 5 8 2 7 4 1 2 3 4 5 6 7 8 Trạng thái xuất phát Trạng thái đích Hình 2.1. Trò đố 8 ô 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: mỗi trạng thái là một sắp xếp cụ thể vị trí các ô - Hành động: 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 - Trạng thái xuất phát: được cho trước (trạng thái bên trái trong hình 2.1) - Trạng thái đích: được cho một cách tường minh (trạng thái bên phải trong hình 2.1) - Giá thành: bằng tổng số lần dịch chuyển ô trống. Nói cách khác, mỗi chuyển động có giá thành bằng 1. Lời giải trong trường hợp này là chuỗi các hành động cho phép di chuyển từ trạng thái xuất phát tới đích. Lời giải cần ít hành động hơn là lời giải tốt hơn. 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. Trường hợp riêng của bài toán này là trường hợp n = 8, khi đó bàn cờ là bàn cờ vua truyền thống kích thước 8 x 8. Đâ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: ở đây có hai cách xác định trạng thái. Theo cách thứ nhất, trên bàn cờ luôn có n con hậu, khi đó mỗi trạng thái được xác định bởi vị trí cụ thể của n con hậu. Theo cách thứ hai, trên bàn cờ có thể có từ 0 tới n con hậu, khi đó mỗi trạng thái được xác định bởi sắp xếp của từ 0 tới n con hậu trên bàn cờ và mỗi hành động được thực hiện bằng cách thêm một con hậu vào trạng thái cũ. - Trạng thái xuất phát: theo cách biểu diễn trạng thái thứ nhất, trạng thái xuất phát có thể được chọn bằng cách sắp xếp ngẫu nhiên n con hậu. Theo cách thứ hai, trạng thái xuất phát là bàn cờ trống không có con hậu nào. - Trạng thái đích: được cho bằng quy tắc kiểm tra, theo đó trạng thái là đích nếu gồm đủ n con hậu và không có quá một con trên cùng một cột, hoặc cùng một dòng, hoặc cùng một đường chéo. 25 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm - Chuyển động: Có nhiều cách khác nhau. Ví dụ, với cách xác định trạng thái thứ nhất, mỗi chuyển động được thực hiện bằng cách đổ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). Với cách xác định trạng thái thứ hai và trạng thái đích là bàn cờ trống, ta có thể quy định chuyển động như sau: tại mỗi chuyển động, tìm cách đặt thêm một con hậu và cột trái nhất còn trống sao cho con hậu mới đặt vào không đe dọa các con trước (cách chuyển động này cho không gian trạng thái nhỏ hơn nhiều so với các kiểu chuyển động khác và mỗi trạng thái chỉ cho phép không quá một con hậu trong một cột). Trong bài toán này, khác với bài toán tám ô, ta không quan tâm tới đường đi mà chỉ quan tâm tới trạng thái đích tìm được. Bài toán tìm đường đi Đây là bài toán có rất nhiều ứng dụng. Dạng đơn giản và thường gặp nhất là tìm đường đi giữa hai điểm trên bản đồ, có thể là đường đi theo đường bộ như trên hình 2.2, đường không, hoặc đường thủy. Các công cụ tìm đường dạng này có thể gặp trong ứng dụng bản đồ như của Google, bán kèm máy định vị GPS, công cụ hỗ trợ lái xe, dịch vụ đặt chuyến bay v.v. Bài toán tìm đường đi cũng gặp trong định tuyến cho mạng, chẳng hạn mạng Internet, trong đó cần tìm đường đi cho các gói tin giữa hai nút mạng. Hình 2.2. Ứng dụng tìm kiếm đường đi trên bản đồ Xét ví dụ tìm kiếm đường bộ trên bản đồ như trong ví dụ hình 2.2. Ta có các thành phần bài toán tìm kiếm như sau: - Trạng thái: mỗi trạng thái là một địa danh trên đường đi, ví dụ một thành phố, thị xã, thị trấn, hay một nút giao thông. Để cho đơn giản, ta sẽ quy định mỗi trạng thái là một nút giao thông từ mức thị trấn trở lên. Ví dụ, trạng thái hiện thời có thể là ở 26 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm nút giao thông Ninh Bình, hay nút giao thông Hòa Bình với bản đồ trên hình 2.2. - Trạng thái xuất phát: do người dùng xác định. - Trạng thái đích: do người dùng xác định. - Chuyển động: được xác định bằng tập các nút giao thông láng giềng của trạng thái hiện thời, tức là các nút giao thông có thể di chuyển tới từ nút giao thông hiện thời mà không phải đi qua một nút khác. - Giá thành: có thể tính bằng khoảng cách (số km) để di chuyển từ nút giao thông này sang nút giao thông khác. Giá thành cũng có thể tính bằng thời gian để di chuyển, số tiền phải bỏ ra cho tiền xăng và tiền phí giao thông (nếu có) v.v. Các hệ thống tìm đường sẽ trả về đường đi tức là chuỗi các chuyển động ngắn nhất theo hàm giá thành được chọn. Để tiện cho việc tập trung vào các thành phần chính, khi phát biểu bài toán tìm đường đi, nhiều chi tiết thường được bỏ qua như quỹ đạo thực tế, điều kiện thời tiết, chất lượng đường v.v. Khi đó, bài toán tìm đường đi thường được biểu diễn dưới dạng tìm đường đi giữa hai nút trên đồi thị như minh họa trên hình 2.3. Tại mỗi nút, các chuyển động được phép là chuyển động sang nút liền kề. Giá thành đường đi giữa hai nút liền kề được thể hiện trên cung nối hai nút. H A 55 45 45 E D 50 I 7282 4240 S 47 50 48 B F G 40 68 38 C K Hình 2.3. Ví dụ bài toán tìm đường đi trên đồ thị. Các số trên cung thể hiện giá thành. 2.2.3.Thuật toán tìm kiếm tổng quát và cây tìm kiếm Một cách tổng quát, các thuật toán tìm kiếm dựa trên nguyên lý chung như sau: Nguyên lý chung: bắt đầu từ trạng thái xuất phát, sử dụng các hàm chuyển động để di chuyển trong không gian trạng thái cho tới khi đạt đến trạng thái mong muốn. Trả về chuỗi chuyển động hoặc trạng thái đích tìm được tùy vào yêu cầu bài toán. Để minh họa nguyên lý tìm kiếm này, ta xét ví dụ trò đố 8 ô với trạng thái xuất phát là trạng thái trên cùng trong hình 2.4. Khởi đầu từ trạng thái xuất phát, thuật toán kiểm tra xem đây có phải đích chưa. Nếu chưa, ta áp dụng các chuyển động để sinh ra các trạng thái láng giềng. Tiếp theo, ta xét một trạng thái vừa được sinh ra, gọi là trạng thái hiện thời bằng cách 27 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm kiểm tra xem đây đã phải đích chưa. Nếu chưa, ta mở rộng trạng thái hiện thời bằng cách áp dụng các chuyển động được phép đối với trạng thái đó để sinh ra các trạng thái khác. Quá trình tìm kiếm như vậy kết thúc khi tìm được trạng thái đích hoặc khi không còn trạng thái nào để mở rộng nữa. Thuật toán tìm kiếm tổng quát như vậy 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, mỗi nhánh tương ứng với một chuyển động tại nút đang xét. 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.4 là ví dụ một phần cây tìm kiếm sinh ra cho bài toán đố 8 ô. 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: • Mở rộng nút là áp dụng các chuyển động lên trạng thái tương ứng để sinh ra các nút con. • Nút lá là các nút không có nút con tại thời điểm đang xét. • Các nút biên (còn gọi là nút mở): là tập các nút lá có thể mở rộng tiếp. • Tập các nút đã được mở rộng được gọi là tập các nút đóng, hay đơn giản là tập đóng. Hình 2.4. Cây tìm kiếm cho bài toán 8 ô Nguyên lý tìm kiếm vừa trình bầyđược thể hiện qua thuật toán tìm kiếm tổng quát trên hình 2.5. Thuật toán duy trì tập các nút biên O được khởi tạo bằng tập trạng thái xuất phát. Qua mỗi vòng lặp, thuật toán lấy ra một nút từ tập biện O, kiểm tra xem nút này có phải đích không. Nếu nút được lấy ra là đích, thuật toán trả về kết quả. Trong trường hợp ngược lại, nút này được mở rộng, tức là dùng hàm chuyển động để sinh ra các nút con. Các nút mới sinh ra lại được thêm vào tập O. Thuật toán kết thúc khi tìm thấy trạng thái đích hoặc khi O rỗng. 28 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm 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: tập các nút biên, bước này khởi tạo giá trị ban đầu cho O bằng S) 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.5. Thuật toán tìm kiếm tổng quát 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. Tránh vòng lặp Trong cây tìm kiếm trên hình 2.4 và thuật toán trên hình 2.5, ta đã 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. Chẳng hạn, trên hình 2.4, từ trạng thái ngoài cùng bên trái thuộc lớp giữa có thể quay về trạng thái xuất phát nếu sử dụng chuyển động “Dưới”. Tương tự, với đồ thị trên hình 2.3, thuật toán có thể dẫn tới vòng lặp G → A → S → A →… Việc chuyển động theo vòng lặp ảnh hưởng không tốt tới thuật toán tìm kiếm. Một số thuật toán tìm kiếm như tìm kiếm theo chiều sâu (trình bầy trong một phần sau) không thể tìm ra lời giải nếu rơi vào vòng lặp. Một số thuật toán khác như tìm theo chiều rộng, mặc dù vẫn tìm ra lời giải, nhưng sẽ phải tính toán lâu hơn, xem xét nhiều trạng thái hơn nếu gặp phải vòng lặp. Để tránh không rời vào vòng lặp cần có cách kiểm tra để không xem xét lại nút đã duyệt. Cách chung nhất để tránh duyệt lại các nút là duy trì tập các nút đóng, tức là các nút đã được mở rộng, và nhớ tất cả các nút đã được mở rộng vào tập đóng này. Nếu một nút mới sinh ra đã có mặt trong tập các nút đóng hoặc tập nút biên thì sẽ không được thêm vào tập các nút biên nữa. Trên hình 2.6 là phiên bản của thuật toán tìm kiếm tổng quát trình bầy trong hình 2.5, trong đó tập các nút đóng được sử dụng để lưu các nút đã mở rộng và cho phép tránh vòng lặp. Phần chữ đậm là các phần được bổ sung so với thuật toán cũ. Thuật toán này được đặt tên là Graph_Search để phân biệt với thuật toán không lưu các nút đóng. 29 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm Graph_Search(Q, S, G, P) (Q: tập 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: tập các nút biên, bước này khởi tạo giá trị ban đầu cho O bằng S D ← Ø // D là tập nút đóng, được khởi tạo bằng rỗng ---------------------------------------- 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 n vào D 4. Thêm các nút thuộc P(n) vào O nếu nút đó không thuộc D và O Return: Không có lời giải Hình 2.6. Thuật toán Graph_Search với danh sách các nút đóng cho phép tránh vòng lặp. Phần bôi đậm là phần khác so với thuật toán tìm kiếm không tránh vòng lặp. Lưu ý: cần phân biệt khái niệm nút và trạng thái khi triển khai thuật toán cụ thể. Mỗi nút được gắn với một đường đi cụ thể trên cây tìm kiếm còn trạng thái là đặc trưng của thế giới bài toán. Hai nút khác nhau có thể chứa cùng một trạng thái nếu trạng thái đó được sinh ra từ hai đường đi khác nhau. Như vậy, trong nhiều thuật toán, ta chỉ không duyệt lại các nút đã được mở rộng, trong khi vẫn có thể xem xét các trạng thái đã được xem xét trước đó nhưng được sinh ra theo những đường khác trong cây tìm kiếm. 2.2.4. 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. Để có thể so sánh với nhau, thuật toán tìm kiếm được đánh giá theo bốn tiêu chuẩn sau: • Tính đầy đủ: nếu bài toán có lời giải thì thuật toán có đảm bảo 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 đầy đủ. • 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? Tiêu chuẩn tối ưu thường được dùng là giá thành đường đi. Lời giải tối ưu là lời giải có giá thành đường đi nhỏ nhất. Thuật toán luôn đảm bảo tìm ra lời giải tối ưu được gọi là thuật toán có tính tối ưu. 30 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm • Độ 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 nút tối đa cần sinh ra 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 nút tối đa cần lưu trữ đồng thời trong bộ nhớ khi thực hiện thuật toán. Các tiêu chuẩn trên được đánh giá tùy theo độ khó (kích thước) của bài toán. Rõ ràng, bài toán có không gian trạng thái lớn hơn sẽ đòi hỏi tính toán nhiều hơn. Trong trường hợp không gian trạng thái được cho tường minh và hữu hạn, độ khó của bài toán được xác định bằng tổng số nút và số liên kết giữa các nút trong đồ thị tìm kiếm. Tuy nhiên, do không gian trạng thái có thể là vô hạn và được cho một cách không tường minh, độ khó của bài toán được xác định qua ba tham số sau: - Mức độ rẽ nhánh b: là số lượng tối đa nút con có thể sinh ra từ một nút cha. - Độ sâu d của lời giải: là độ sâu của lời giải nông nhất, trong đó độ sâu được tính bằng số nút theo đường đi từ gốc tới lời giải. - Độ sâu m của cây tìm kiếm: là độ sâu lớn nhất của mọi nhánh trên cây tìm kiếm. 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, ngoài ra không sử dụng thêm thông tin nào khác. 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 Thuật toán tìm kiếm không có thông tin được xem xét trước tiên là tìm kiếm theo chiều rộng (Breadth-first search, viết tắt là BFS), một dạng tìm kiếm vét cạn. 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. Như vậy, trước hết tất cả các nút có độ sâu bằng 0 (nút gốc) được mở rộng, sau đó tới các nút có độ sâu bằng 1 được mở rộng, rồi tới các nút có độ sâu bằng 2, và tiếp tục như vậy. Ở đây, độ sâu được tính bằng số nút nằm trên đường đi từ nút gốc tới nút đang xét. 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 FIFO để 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 2.7. Khác với thuật toán tìm kiếm tổng quát ở trên, tập nút biên O được tổ chức dưới dạng hàng đợi FIFO: các nút mới sinh ra được thêm vào cuối của O tại bước 3 của mỗi vòng lặp; nút đầu tiên của O sẽ được lấy 31 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm ra để mở rộng như tại bước 1 của vòng lặp của thuật toán trên hình vẽ. Bước 2 của vòng lặp kiểm tra điều kiện đích và trả về kết quả trong trường hợp nút lấy ra từ O là nút đích. Thuật toán kết thúc trong hai trường hợp: 1) khi lấy được nút đích từ O; và 2) khi tập O rỗng. Hai trường hợp này tương ứng với hai lệnh return ở trong và ngoài vòng lặp. Con trỏ ngược: 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. Khi cài đặt thuật toán, mỗi nút được biểu diễn bằng một cấu trúc dữ liệu có chứa một con trỏ ngược trỏ tới nút cha. Sau khi tìm được nút đích, có thể khôi phục đường đi tới nút đó bằng cách lần theo các con trỏ ngược, bắt đầu từ nút đích. 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 // trong thuật toán này, O là hàng đợi FIFO ----------------------------- 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.7. Thuật toán tìm kiếm theo chiều rộng Các cải tiến. Một số cải tiến sau đây có thể sử dụng kết hợp với thuật toán tìm theo chiều rộng vừa trình bầy. Tránh xem xét lại các nút đã mở rộng. Việc xem xét lại các nút đã mở rộng có thể dẫn tới vòng lặp. Mặc dù vòng lặp không ảnh hưởng tới khả năng tìm ra lời giải của tìm theo chiều rộng, xong việc có vòng lặp và xem xét lại các nút làm tăng độ phức tạp tính toán do phải khảo sát nhiều nút hơn. Vấn đề này có thể giải quyết bằng cách sử dụng tập đóng tương tự trong thuật toán Graph_Search trên hình 2.6. Một trạng thái đã có mặt trong tập đóng hoặc tập biên sẽ không được thêm vào tập biên nữa. Người đọc có thể tự kiểm tra kết quả của thuật toán trong trường hợp có sử dụng kiểm tra tập đóng và tập biên với trường hợp không kiểm tra bằng cách thực hiện thuật toán với ví dụ trên hình 2.8. Kiểm tra đích trước khi thêm vào tập biên. Trong thuật toán tổng quát, việc kiểm tra điều kiện đích được thực hiện khi nút được lấy ra khỏi O để mở rộng. Thay vào đó, ta có thể kiểm tra trước khi thêm nút vào O. Ưu điểm của cách làm này là giảm bớt số lượng nút cần 32 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm lưu trong nút biên cũng như số nút được mở rộng. Cụ thể về số lượng nút cần mở rộng khi thực hiện kiểm tra đích trước sẽ được trình bầy trong phần tính chất của thuật toán ở bên dưới. Ví dụ: Xét ví dụ tìm đường đi từ nút S tới nút G trên đồ thị ở hình 2.8. (để đơn giản, ví dụ này sử dụng đồ thị có hướng; quá trình tìm đường đi trên đồ thị vô hướng được thực hiện tương tự, trừ việc từ một nút có thể di chuyển sang nút cha của nút đó) A 55 45 45 E D 72 82 S 4240 50 48 B FG 40 C 68 73 H 60 Hình 2.8. Ví dụ đồ thị cho bài toán tìm đường đi Một số bước đầu tiên của thuật toán, có sử dụng việc lưu và kiểm tra tập nút đóng, được thể hiện dưới dạng các cây tìm kiếm như trên hình 2.9. Lưu ý: để thống nhất trong việc trình bầy, trong số các nút có vai trò giống nhau, tức là có cùng độ sâu, nút đứng trước trong bảng chữ cái sẽ được mở rộng trước. Quy tắc này không được quy định trong thuật toán và chỉ để tiện cho trình bầy. S S A B C E S S A B C E D S A B C E A B C E … D F D F H Hình 2.9. Một số cây tìm kiếm sinh ra khi tìm kiếm theo chiều rộng. Các cây được thể hiện theo thứ tự từ trái sang phải, từ trên xuống dưới. Nút mở rộng tiếp theo được đánh dấu bằng mũi tên 33 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm Kết quả thực hiện các bước của thuật toán cũng có thể theo dõi qua thứ tự mở rộng các nút và nội dung danh sách tập nút biên. Dưới đây là minh họa cho thứ tự mở rộng nút và tập biên cho ví dụ trên hình 2.8 (có sử dụng tập nút đóng). Để tiện cho trình bầy, ta sẽ quy định phía bên trái là đầu của hàng đợi O và phía bên phải là cuối của hàng đợi O. Như vậy các nút được thêm vào từ phía bên phải và lấy ra từ bên trái. Con trỏ tới nút cha sẽ được viết dưới dạng chỉ số bên cạnh mỗi nút Nút được mở rộng Tập biên O (hàng đợi FIFO trong trường hợp này) S S AS , BS , CS , ES AS BS , CS , ES, DA BS CS , ES, DA, FB CS ES , DA, FB , HC ES DA , FB, HC , GE DA FB, HC , GE FB HC , GE HC GE GE Đích Sau đó, sử dụng con trỏ ngược, theo đó E là nút cha của G, S là nút cha của E, ta tìm được đường đi G ← E ← S. 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. Thật vậy, nếu lời giải nằm ở độ sâu hữu hạn d thì thuật toán sẽ đạt tới lời giải đó sau khi đã khảo sát hết các nút nông hơn, trừ khi yếu tố rẽ nhánh b là vô hạn. Tìm theo chiều rộng là tìm kiếm vét cạn, trong đó các nút có độ sâu nhỏ hơn được xem xét trước. • Tính tối ưu: thuật toán đảm bảo tìm ra lời giải có độ sâu nhỏ 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. Cụ thể, trong ví dụ trên, thuật toán tìm ra đường đi SEG có độ sâu bằng 2 (nhỏ nhất) nhưng có độ dài 154, trong khi đường đi ngắn nhất SBFG có độ dài 132. 34 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm • Độ phức tạp tính toán: với mức độ rẽ nhánh là b và độ sâu lời giải d, thuật toán sinh ra O(bd +1) nút trước khi tìm ra lời giải hay O(bd) nút nếu kiểm tra đích trước khi thêm nút vào tập biên. Độ phức tạp này là lớn và tăng rất nhanh khi b và d tăng. 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ề. Như vậy từ nút gốc sẽ sinh ra b nút với độ sâu 1, các nút này lại sinh ra b2 nút với độ sâu 2, và tiếp tục như vậy. Giả sử nút đích của bài toán nằm ở độ sâu d. Trong trường hợp xấu nhất, nút đích nằm cuối cùng trong số các nút ở độ sâu này và do vậy ta cần mở rộng tất cả nút ở độ sâu d trước khi tìm ra đích, tức là sinh ra bd +1 nút ở độ sâu d +1. Như vậy, tổng số nút cần mở rộng để tìm ra nút đích là (tính cả nút gốc): 1 + b + b2 + ... + bd +1 = O(bd +1) Nếu tiến hành kiểm tra điều kiện đích trước khi thêm vào tập biên như đề cập ở trên, ta sẽ không phải sinh ra các nút ở độ sâu d + 1 và do vậy số nút cần sinh ra chỉ còn là O(bd). • Yêu cầu bộ nhớ: thuật toán cần lưu O(bd +1) nút trong tập biên sau khi đã mở rộng tất cả các nút ở độ sâu d. Nếu sử dụng tập các nút đóng thì tập này cần lưu O(bd) nút. Như vậy độ phức tạp bộ nhớ của tìm kiếm rộng là O(bd +1). Như vậy, ưu điểm của tìm theo chiều rộng là tính đầy đủ và tối ưu nếu giá thành đường đi như nhau. Nhược điểm của thuật toán này là độ phức tạp tính toán lớn và yêu cầu về bộ nhớ lớn. Trong hai nhược điểm sau, độ phức tạp về bộ nhớ lớn là nghiêm trọng hơn do không thể kiếm được máy tính có bộ nhớ đủ lớn để chạy thuật toán, trong khi ta có thể đợi thêm thời gian để chờ thuật toán chạy xong nếu thời gian chạy không quá lâu. Trên thực thế, thuật toán tìm theo chiều rộng chỉ có thể sử dụng cho các bài toán có kích thước rất nhỏ (b và d không quá 10). 2.3.2. Tìm kiếm theo giá thành thống nhất 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 thống nhất (Uniform-Cost-Search). Phương pháp: Thuật toán tìm theo giá thành thống nhất chọn nút n có giá thành đường đi g(n) 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, trong đó g(n) là giá thành đường đi từ nút xuất phát tới nút n. 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 nút n có giá thành g(n) 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 (g(n)) vào O Cách tránh vòng lặp được thực hiện như trong thuật toán Graph-search, tuy nhiên nếu nút đã có trong tập biên thì ta lưu lại bản có giá thành nhỏ hơn. 35 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm Ví dụ: với ví dụ trên hình 2.8, kết quả các bước tìm kiếm theo giá thành thống nhất được thể hiện dưới đây, với giá trị g(n) được cho trong ngoặc sau mỗi nút. Nút được mở rộng Tập biên O S(0) S AS (55) , BS (42), CS (48), ES (72) BS AS (55) , CS (48), ES (72), FB (82) CS AS (55) , ES (72), FB (82), HC (121) AS ES (72), FB (82), HC (121), DA (100) ES FB (82), HC (121), DA (100), GE (154) FB HC (121), DA (100), GF (132) DA HC (121), GF (132) HC GF (132) GF Đích The con trỏ ngược, ta tìm được đường đi G ← F ← B← S với giá thành 132. Thuật toán tìm kiếm theo giá thành thống nhất có một trường hợp riêng là thuật toán Dijkstra. Một trong những điểm khác nhau lớn nhất với thuật toán Dijkstra là thuật toán Dijkstra tìm đường đi ngắn nhất từ nút gốc tới tất cả các nút còn lại thay vì chỉ tìm đường tới nút đích như trong trường hợp tìm theo giá thống nhất. Thuật toán tìm kiếm này luôn cho lời giải tối ưu, tức là lời giải với đường đi có giá nhỏ nhất. Do thuật toán không lựa chọn nút để mở rộng dựa trên độ sâu mà dựa trên giá thành nên không thể phân tích độ phức tạp tính toán cũng như yêu cầu bộ nhớ của thuật toán dựa trên tham số b và d. Trong trường hợp giá thành mọi chuyển động bằng nhau, tìm kiếm theo giá thống nhất sẽ giống với tìm theo chiều rộng. 2.3.3. Tìm kiếm theo chiều sâu Thuật toán tìm kiếm mù được biết đến nhiều tiếp theo là tìm theo chiều sâu (Depth First-Search, viết tắt là DFS). Nguyên tắc của tìm kiếm theo chiều sâu là lựa chọn trong số những nút biên nút sâu nhất (xa nút gốc nhất) để mở rộng trước. Như vậy, thay thì khảo sát tất cả các nhánh của cây tìm kiếm một lúc như trong tìm theo chiều rộng, thuật toán tìm sâu sẽ di chuyển theo một nhánh trong cây tìm kiếm cho tới nút sâu nhất, tức là nút không có nút con, trước khi chuyển sang nhánh tiếp theo. Để 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 (vào sau ra trước). Thuật 36 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm toán tìm theo chiều sâu cũng có thể thực hiện bằng cách đệ quy và quay lui. Tuy nhiên, trong tài liệu này, ta không sẽ không xem xét phương án sử dụng đệ quy và quay lui. Thuật toán tìm kiếm theo chiều sâu được thể hiện trên hình 2.10, trong đó tập biên O được triển khai dưới dạng ngăn xếp LIFO. Các nút mới sinh ra được thêm vào đầu ngăn xếp O ở bước 3 của vòng lặp chính. Nút để mở rộng cũng được lấy ra từ đầu của O ở bước 1 của vòng lặp chính. Tương tự tìm theo chiều rộng, mỗi nút cần có con trỏ ngược về nút cha. Con trỏ ngược được sử dụng để khôi phục lại đường đi khi thuật toán đã tìm ra nút đích. Thuật toán kết thúc và trả về kết quả tại bước 2 của vòng lặp nếu nút lấy ra khỏi O là nút đích; hoặc thuật toán kết thúc (bằng lệnh return ở dưới cùng) mà không tìm được kết quả nếu tập O rỗng. 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 đíchC Khởi tạo: O←S // O được tổ chức như ngăn xếp LIFO ------------------------- While(O ≠ Ø) do 1. Chọn nút n đầu tiên của 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.10. Thuật toán tìm kiếm theo chiều sâu Tránh các nút lặp: Thuật toán trên hình 2.10 có thể dẫn tới vòng lặp. Ví dụ, trong bài toán tìm đường trên bản đồ, thuật toán có thể quay về vị trí trước đó và lặp đi lặp lại chuyển động giữa hai trạng thái liền nhau. Khác với tìm theo chiều rộng, tìm theo chiều sâu sẽ lặp vô hạn mà không tìm được lời giải. Để tránh vòng lặp khi tìm kiếm theo chiều sâu, có thể sử dụng một trong hai phương pháp. Phương pháp thứ nhất giống như phương pháp sử dụng trong thuật toán Graph_Search, tức là duy trì danh sách nút đóng và nhớ tất cả các nút đã mở rộng vào đây. Một nút mới sinh ra chỉ được thêm vào nút biên nếu nó chưa xuất hiện trong tập đóng và tập biên. Phương pháp này đòi hỏi nhiều bộ nhớ để duy trì tập nút đóng. Phương pháp thứ hai kiểm tra xem nút mới có thuộc đường đi từ gốc tới nút hiện thời không, nếu có, nút mới sẽ không được thêm vào tập nút biên. Cách này không đòi hỏi bộ nhớ để lưu tập đóng, 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. 37 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm Ví dụ: kết quả sau các bước lặp của thuật toán tìm theo chiều sâu cho bài toán tìm đường từ S tới G trên đồ thị hình 2.8 được thể hiện dưới đây dưới dạng các nút được mở rộng và nội dung tập biên O sau mỗi vòng lặp. Cũng như trong các ví dụ trước, nếu hai nút cùng độ sâu thì nút đứng trước trong bảng chữ cái được mở rộng trước. Việc tránh vòng lặp được thực hiện theo phương pháp thứ hai. Đỉnh ngăn xếp nằm phía trái và đáy ngăn xếp nằm bên phải trong mỗi dòng. Nút được mở rộng Tập biên O (ngăn xếp LIFO trong trường hợp này) S S AS , BS , CS , ES AS DA , BS , CS , ES DA ED, BS , CS , ES ED BS , CS , ES GE Đích Theo con trỏ ngược, ta tìm được đường đi G ← E ← D ← A ← S với độ sâu bằng 4 và độ dài 227. Tính chất thuật toán tìm theo chiều sâu: • Nếu không gian trạng thái là hữu hạn thì thuật toán là đầy đủ. Ngược lại, nếu không gian trạng thái là vô hạn thì thuật toán là không đầy đủ do có thể di chuyển theo một đường đi không chứa nút đích và có độ sâu 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( m b ) với m là độ sâu tối đa của cây tìm kiếm. Trong trường hợp không gian trạng thái là vô hạn thì m là vô hạn. 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. • Bộ nhớ cần nhớ tối đa b*m (mỗi mức chỉ nhớ b nút, với tối đa m mức), như vậy độ phức tạp về bộ nhớ của thuật toán này chỉ là O(bm). Để đá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. 2.3.4. Tìm kiếm sâu dần Tìm kiếm sâu dần (Iterative Deepening Search, viết tắt là IDS) là một phương pháp tìm 38 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm kiếm dựa trên tìm theo chiều sâu nhưng có tính đầy đủ và cho phép tìm ra lời giải tối ưu. Như đã nói ở trên, 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 chiều sâu 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. Nói cách khác, các nút ở độ sâu giới hạn sẽ không được mở rộng tiếp. Thuật toán này có yêu cầu bộ nhớ nhỏ tương tự tìm theo chiều sâu, trong khi chắc chắn tìm được lời giải. 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 ở miền bắc và bắc trung bộ không có nhiều hơn 15 thành phố thì khi tìm đường từ Hà nội vào Vinh có thể giới hạn chiều sâu tìm kiếm bằng 15. 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. Trong trường hợp ta biết chính xác độ sâu của lời giải, thuật toán sẽ cho lời giải tối ưu (lời giải nông nhất). 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 nút có độ sâu quá một giới hạn nào đó. Giới hạn độ sâu được bắt đầu từ 0, sau đó tăng lên 1, 2, 3 v.v. cho đến khi tìm được lời giải. Thuật toán tìm kiếm sâu dần thể hiện trên hình 2.11, 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. Sau mỗi vòng lặp, giá trị của C được tăng thêm một đơn vị và thuật toán xây dựng lại cây tìm kiếm từ đầu. Với mỗi giá trị của C, thuật toán tiến hành tìm kiếm theo chiều sâu nhưng không thêm vào ngăn xếp O các nút có độ sâu lớn hơn C. Việc kiểm tra này được thực hiện ở bước c) tại vòng lặp trong của thuật toán. Lưu ý rằng trong trường hợp này khó xác định điều kiện kết thúc của thuật toán trong trường hợp không tìm được lời giải. 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: ngăn xếp LIFO như trong DFS) C ← 0 (C là giới hạn độ sâu tìm kiếm) --------------------------------- While (điều kiện kết thúc chưa thoả mãn) do While(O ≠ Ø) do //Thực hiện 3 bước tương tự tìm kiếm sâu 39 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm a) Lấy nút đầu tiên n từ đầu của O b) If (n ∈ G) then return (đường đi tới n) c) If (độ sâu của n nhỏ hơn hoặc bằng C) then • Thêm P(n) vào đầu O C++, O←S Return: không tìm được lời Hình 2.11. 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.12. Hình 2.12. Cây tìm kiếm theo thuật toán tìm kiếm sâu dần 40 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm Ví dụ. Kết quả sau các bước lặp của thuật toán tìm kiếm sâu dần cho bài toán tìm đường từ S tới G trên đồ thị hình 2.8 được thể hiện dưới đây. Các thông tin sau mỗi bước lặp bao gồm giới hạn độ sâu C, nút được mở rộng, và nội dung tập biên O. Cũng như trong các ví dụ trước, nếu hai nút cùng độ sâu thì nút đứng trước trong bảng chữ cái được mở rộng trước. Việc tránh vòng lặp được thực hiện theo phương pháp thứ hai. Đỉnh ngăn xếp nằm phía trái và đáy ngăn xếp nằm bên phải trong mỗi dòng. Nút được mở rộng Tập biên O (ngăn xếp LIFO trong trường hợp này) C = 0 S S C = 1 S S AS , BS , CS , ES AS BS , CS , ES BS CS , ES CS ES ES C = 2 S S AS , BS , CS , ES AS BS , CS , ES, DA BS CS , ES, DA, FB CS ES, DA, FB, BC, FC, HC ES DA, FB, BC, FC, HC, GC DA FB, BC, FC, HC, GC FB BC, FC, HC, GC BC FC, HC, GC FC HC, GC HC GC GC Đích 41 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm Theo con trỏ ngược, ta tìm được đường đi G ← E ← S với độ sâu bằng 2 và độ dài 154. Đây là đường đi nông nhất, mặc dù không phải là đường đi ngắn nhất. Tính chất của tìm sâu dần: d) Thuật toán đầy đủ, tức là đảm bảo tìm ra lời giải nếu có. Thật vậy, tương tự tìm theo chiều rộng, tìm sâu dần xem xét toàn bộ các nút ở một độ sâu, bắt đầu từ độ sâu 0, trước khi chuyển sang xem xét toàn bộ nút ở độ sâu tiếp theo. Do vậy, thuật toán sẽ tìm được lời giải khi xem xét hết các nút ở độ sâu d (d là độ sâu lời giải). e) Tương tự tìm theo chiều rộng, thuật toán tối ưu nếu giá thành đường đi giữa hai nút giống nhau, tức là nếu có nhiều lời giải, có thể tìm ra được lời giải nông nhất. Thật vậy, thuật toán sẽ xem xét toàn bộ các nút có độ sâu bằng 0, trước khi xem xét các nút có độ sâu bằng 1 v.v. Do vậy, trong các lời giải có độ sâu khác nhau, thuật toán sẽ xem xét lời giải nông hơn trước. f) Yêu cầu bộ nhớ nhỏ. Cụ thể, yêu cầu bộ nhớ là O(bd). Thực chất, tại mỗi bước lặp, thuật toán thực hiện tìm kiếm theo chiều sâu nên yêu cầu bộ nhớ tương tự tìm theo chiều sâu, tức là O(bd). g) Độ phức tạp tính toán O( d b ).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 + b2 + ... + bd Nếu lời giải ở độ 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) + db + (d - 1)b2 + ... + 2bd-1 + bd Do đó thời gian tìm kiếm sâu dần là O(bd) tương tự tìm kiếm theo chiều rộng. Trên thực tế, do phải xem xét nhiều lần các nút ở độ sâu nhỏ, nên độ phức tạp tính toán của tìm sâu dần lớn hơn tìm kiếm theo chiều rộng nhưng không lớn hơn quá nhiều. 2.3.5.Tìm theo hai hướng 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.13). Tìm theo hai hướng (Bidirectional Search) là phương pháp tìm kiếm trong đó ta đồng thời xây dựng hai cây tìm kiếm có nút gốc là trạng thái xuất phát và trạng thái đích. 42 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm Phương pháp. Tìm kiếm bắt nguồn từ nút xuất phát và nút đích. Như 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ó nút lá của cây này trùng với nút lá của cây kia. Hình 2.13: Cây tìm kiếm trong trường hợp tìm theo hai hướng 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 nút con của x và D(x): tập các nút cha của x. Nút càng gần nút xuất phát càng được coi là tổ tiên Tính chất của tìm theo hai hướng: • Việc kiểm tra xem nút lá này có trùng với nút lá kia đòi hỏi tương đối nhiều thời gian. Thật vậy, ở độ sâu d, mỗi cây tìm kiếm sẽ sinh ra bd nút lá. Như vậy cần so sánh mỗi nút lá của cây theo hướng này với bd nút lá của hướng ngược lại. • Độ 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( d / 2 b ). 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. 2.4. TÌM KIẾM CÓ THÔNG TIN Đối với tìm kiếm mù, các nút biên lần lượt được mở rộng theo một thứ tự nhất định mà không tính tới việc ưu tiên các nút có khả năng dẫn tới lời giải nhan hơ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 43 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm 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 (Informed search) hay còn được gọi là tìm kiếm heuristic sử dụng thêm thông tin 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. Thông thường, độ tốt được đo bằng giá thành đường đi tới đích, do vậy nút có hàm f (n) nhỏ được ưu tiên 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 chỉ có thể ước lượng hàm f (n) dựa vào thông tin có được từ bài toán. Như sẽ thấy trong các phần sau, hàm f (n) thường chứa một thành phần là hàm heuristic h(n), là hàm ước lượng khoảng cách từ nút n tới đích. 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 Ý tưởng của tìm kiếm tham lam (Greedy Search) là chọn trong tập nút biên nút có khoảng cách tới đích nhỏ nhất để mở rộng. Lý do làm như vậy là việc mở rộng nút gần đích có xu hướng dẫn tới lời giải nhanh hơn. 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 tại mỗi bước, thuật toán cố gắng tiến về đích nhiều nhất có thể. Như ta sẽ thấy dưới đây, do thuật toán chỉ cố gắng làm tốt nhất tại mỗi bước mà không tính tới tổ hợp các bước, đường đi tìm được có thể không phải là đường đi ngắn nhất. Hàm heuristic được xây dựng dựa trên thông tin có được về bài toán. Hàm này phải thỏa mãn hai điều kiện: thứ nhất, đây là hàm không âm (h(n) ≥0), và thứ hai, nếu n là nút đích thì h(n) = 0. Như vậy, tìm kiếm tham lam sử dụng hàm heuristic h(n) để ước lượng khoảng cách từ các nút tới đích và thuật toán luôn mở rộng nút n có hàm h(n) nhỏ nhất trong số các nút biên. Ví dụ. Khi tìm đường đi giữa hai nút bản đồ, hàm heuristic cho một nút có thể tính bằng khoảng cách theo đường chim bay giữa thành phố đó với nút đích cần đến. Để minh họa, ta xét bài toán tìm đường đi từ nút S tới nút G trên đồ thị ở hình 2.14. Trên đồ thị này, khoảng cách thực giữa hai nút bất kỳ được cho dưới dạng số bên cạnh cung nối hai nút. Khoảng cách tính theo đường chim bay giữa một nút bất kỳ và nút đích G được cho bằng số in nghiêng bên cạnh nút đó. 44 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm D 45 115 H 70 123 55 A 45 E 72 50 I 40 125 S 7282 4240 82 47 55 48 40 B F G 0 40 68 38 118 C K 30 Hình 2.14. Ví dụ tìm đường đi trên đồ thị từ S tới G. Khoảng cách thực được cho trên các cung. Khoảng cách tính theo đường chim bay từ mỗi nút tới nút đích G được cho bằng số in nghiêng bên cạnh các nút. S 125 mở rộng S S A B C E 123 82 118 72 mở rộng E S A B C E 123 82 118 D G mở rộng G: đích 115 0 Hình 2.15. Minh họa hoạt động của thuật toán tìm kiếm tham lam Xuất phát từ S, thứ tự mở rộng các nút của thuật toán tham lam được thể hiện trên hình 2.15. sau khi mở rộng nút S, nút được chọn tiếp theo là E do nút này có giá trị hàm heuristic (khoảng cách theo đường chim bay) bằng 72, nhỏ nhất trong số 4 nút A, B, C, E. Sau khi mở rộng nút E, nút được chọn tiếp theo là G do nút này có giá trị hàm heuristic nhỏ nhất (bằng 0) 45 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm trong số 5 nút biên A, B, C, D, G. Kiểm tra G cho thấy đây là đích. Đường đi tìm được là S→E→G. Đặc điểm của tìm kiếm tham lam: • Không có tính đầy đủ do có khả năng tạo thành vòng lặp vô hạn ở một số nút. Chẳng hạn, nếu trong ví dụ ở trên cần tìm đường đi từ nút I tới nút D. Thuật toán sẽ chọn nút tiếp theo là H do nút này gần D hơn G theo đường chim bay. Mở rộng H, thuật toán lại thêm I vào tập biên và do I gần D hơn G, thuật toán lại chọn I, và như vậy bị lặp vô hạn giữa I và H. • Độ phức tạp về thời gian: trong trường hợp xấu nhất là O( m b ). Độ phức tạp này có thể giảm rất nhiều 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. • Độ phức tạp về không gian lưu trữ: trong trường hợp xấu nhất thuật toán lưu O( m b ) nút với m là độ sâu cây tìm kiếm, tuy nhiên nếu heuristic tốt thì số nút cần lưu giảm đi rất nhiều như trong ví dụ trên. • Thuật toán không tối ưu: trong ví dụ ở trên, đường đi S→E→G tìm được có độ dài là 154 trong khi đường đi ngắn nhất S→B→F→G có độ dài bằng 97. 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 tối ưu, tức là lời giải với đường đ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 quãng đườ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ẽ sử dụng hàm 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. Trong phần tìm kiếm mù, ta đã xem xét thuật toán tìm kiếm với giá thành thống nhất, trong đó nút biên có hàm g(n) nhỏ nhất được chọn để mở rộng. Như vậy, thuật toán A* khác tìm kiếm với giá thành thống nhất ở chỗ sử dụng thêm hàm h(n) để ước lượng khoảng cách tới đích. Thuật toán A* yêu cầu hàm h(n) là hàm chấp nhận được (admissible) theo định nghĩa sau. Đị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 độ dài đường đi thực ngắn nhất từ n tới nút đích. 46 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm Thuật toán A* được thể hiện trên hình 2.16. 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.16. Thuật toán A* Với thuật toán A*, có thể sử dụng phiên bản Graph-search (tức là có danh sách nút đóng) hoặc không. Trong trường hợp không sử dụng nút đóng, tất cả các nút mới sinh ra đều được thêm vào tập biên. Trong trường hợp sử dụng phiên bản Graph-search, một nút đã mở rộng sẽ không được thêm vào danh sách biên. Nếu một nút đã có một bản sao trong tập biên thì bản sao với giá trị hàm f(n) nhỏ hơn sẽ được giữ lại. Ví dụ. Kết quả các bước thực hiện thuật toán A* cho bài toán tìm đường từ S tới G trên đồ thị hình 2.14 được thể hiện dưới đây. Các thông tin bao gồm nút được mở rộng, danh sách các nút trong tập biên cùng với giá trị hàm f(n). Phiên bản được trình bầy ở đây là phiên bản không sử dụng danh sách nút đóng và không kiểm tra tập biên. Như vậy, tập biên có thể chứa nhiều phiên bản của cùng một nút với giá trị hàm f(n) khác nhau. Nút được mở rộng Tập biên O. Giá trị hàm f(n) được cho trong ngoặc S (125) S AS (123+55), BS (82+42), CS (118+48), ES (72+72) BS AS (123+55), CS (118+48), ES (72+72), SB (125+84), CB (118+82), FB (40+82) FB AS (123+55), CS (118+48), ES (72+72), SB (125+84), 47 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm CB (118+82), GF (0+137), CF (118+150) GF đích Sử dụng con trỏ ngược, ta có đường đi tìm được là G←F←B←S với độ dài 137. Đây cũng là đường đi ngắn nhất giữa S và G. Đặc điểm của thuật toán A*: • 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 nút với hàm f có giá trị rất nhỏ nằm giữa node xuất phát và node đích. • Độ phức tạp: trong trường hợp xấu nhất, khi hàm heuristic không có nhiều thông tin, độ phức tạp tính toán và yêu cầu bộ nhớ của A* đều là O( m b ). • Trong tất cả các thuật toán tìm kiếm tối ưu sử dụng cùng hàm heuristics thì thuật toán A* có độ phức tạp tính toán nhỏ nhất, tức là yêu cầu sinh ra ít nút nhất trước khi tìm ra lời giải. Yêu cầu bộ nhớ lớn là nhược điểm lớn nhất của A*. Do nhược điểm này, A* thường không thể sử dụng để giải các bài toán có kích thước lớn. Trong phần sau, ta sẽ xem xét một thuật toán với yêu cầu bộ nhớ nhỏ, trong khi vẫn cho phép tìm ra lời giải tối ưu và có độ phức tạp tính toán gần tốt như A*. 2.4.3. Các hàm heuristic Trong tìm kiếm có thông tin, các hàm heuristic đóng vai trò rất quan trọng. Hàm heuristic tốt đảm bảo tính tối ưu cho những thuật toán như A*. Bên cạnh đó, hàm heuristic tốt cho phép hướng thuật toán theo phía lời giải, nhờ vậy giảm số trạng thái cần khảo sát và độ phức tạp của thuật toán. 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. Để minh hoạ cho hàm heuristic, ta xét một số ví dụ sau. Ví dụ: Trong bài toán tìm đường, đườ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. Trong bài toán 8 ô, có thể xây dựng một số hàm heuristic. Dưới đây, ta sẽ xem xét hai trong số các hàm như vậy. 48 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm 3 1 6 5 4 2 7 8 1 2 3 4 5 6 7 8 Trạng thái hiện thời Trạng thái đích Ta có thể sử dụng hai hàm heuristic sau. - 1 h 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. - 2 h 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 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 2 h n( )trội hơn so với 1 h n( ). Rõ ràng hàm 2 h 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 đó khi ước lượng đường đi tới đích. Ví dụ, đối với hàm 1 h 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 phải di chuyển trên đường bộ (thường không phải là đường thẳng) và giả sử có thể di chuyển thẳng từ một điểm tới đích. 49 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm 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 lời giải. 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. 3. 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. … Ở đâ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 ( N2 ). 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. Một lời giải m* được gọi là β - tối ưu nếu g(m*) < g* + β, trong đó g* là giá thành của lời giải tối ưu. Như vậy, lời giải g* là lời giải có giá thành được đi không vượt quá β so với giá thành đường đi tối ưu. 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, bước nhẩy α cho ngưỡng • Đầu ra: đường đi ngắn nhất từ nút xuất phát đến nút đích • Khởi tạo: giá trị i = 0 là ngưỡng cho hàm f 50 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm danh sách các nút biên (nút mở) O ← S ------------------------------------ While (1) do 1. while (O không rỗng) do a) Lấy nút n từ đầu O b) Nếu n ∈ G, then 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.15. Thuật toán A* sâu dần Ví dụ. Xét bài toán tìm đường đi từ nút S tới nút G trên hình 2.16 với hàm heuristic cho cạnh các nút và giá thành đường đi bên cạnh các cung. h=4 h=3 3 2 h=1 h=6 S B C A 3 C 1 2 1 1 2 B D E G h=0 A C 3 D B 3 F h=4 h=4 h=1 A D Hình 2.16. Ví dụ bài toán tìm đường đi Kết quả các bước thực hiện thuật toán A* sâu dần với bước nhẩy α = 2 cho bài toán này được thể hiện trên bảng dưới đây. Kết quả bao gồm giá trị ngưỡng i, nút được mở rộng, tập biên O chứa các nút và giá trị hàm f. Thuật toán tìm sâu tại mỗi bước sử dụng phương pháp thứ hai, tức là nút được thêm vào tập biên nếu không nằm trên đường đi hiện thời. Đầu của danh sách O nằm phía trái và đuôi của O ở phía phải trong bảng. Nút được mở rộng Danh sách O. Giá trị hàm f(n) được cho trong ngoặc i = 0 i = 2 i = 4 51 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm i = 6 S(6) S AS(6) AS i = 8 S(6) S AS(6), BS(7) AS BS(7) BS DB(8) DB CD(8), FD(8) CD FD(8), EC(8) FD EC(8) EC GE(8) GE Đích Theo con trỏ ngược, ta tìm được đường đi G←E←C←D←B←S. Có thể dễ dàng kiểm tra, đây chính là đường đi ngắn nhất từ S tới G. Người đọc có thể tự kiểm tra trường hợp thực hiện thuật toán với bước nhẩy α = 3, lời giải sẽ không phải là lời giải tối ưu. Tính chất của tìm kiếm A* sâu dần: • Thuật toán đầy đủ và β - tối ưu (xem khái niệm β - tối ưu ở trên) • Yêu cầu bộ nhớ tuyến tính (chỉ nhớ nhánh đang xét hiện thời tương tự tìm kiếm sâu dần) • Độ phức tạp tính toán lớn hơn của thuật toán A* do tại mỗi vòng lặp ngoài, thuật toán lặp lại các bước của lần lặp trước. • Không phụ thuộc vào hàm heuristic h(n). Sau mỗi lần tăng giá trị ngưỡng, thuật toán lại xây dựng lại cây tìm kiếm từ đầu, tức là không sử dụng hàm heuristic h(n) để thu hẹp không gian tìm kiếm và hướng về phía nhiều khả năng có trạng thái đích. 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 di chuyển theo một số đường đi. Trong quá trình di chuyển, các thuật toán này lưu lại thông tin về đườ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 52 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm đ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). Đặc điểm chính của thuật toán tìm kiếm cục bộ là tại mỗi thời điểm, thuật toán chỉ sử dụng một trạng thái hiện thời, và chỉ xem xét các láng giềng của trạng thái đó. Thuật toán không lưu đường đi hoặc các trạng thái đã khảo sát, do vậy không đòi hỏi nhiều bộ nhớ như các thuật toán đã trình bầy ở trên. Mặc dù tìm kiếm cục bộ thường không cho phép tìm được lời giải tối ưu, thuật toán loại này cho phép tìm được lời giải tương đối tốt với thời gian và bộ nhớ nhỏ hơn nhiều so với tìm kiếm hệ thống, và do vậy có thể sử dụng cho các bài toán có kích thước lớn. 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 đó. Ví dụ, trong bài toán 8 con hậu, ta chỉ cần tìm vị trí của 8 con hậu mà không cần quan tâm tới đường di 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, lập thời khóa biểu, thiết kế vi mạch, 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: tìm kiếm cục bộ dựa trên ý tưởng chung như sau: • 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). • 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 53 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm 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à lớn nhất hoặc nhỏ nhất. Lưu ý: có thể dễ dàng biến đổi bài toán tìm trạng thái với hàm mục tiêu lớn nhất thành nhỏ nhất hoặc ngược lại bằng cách nhân hàm mục tiêu với –1. Để minh họa cho bài toán tìm kiếm cục bộ, ta xét ví dụ trên hình 2.17 (được tham khảo từ tài liệu số 1). 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.17. 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 Leo đồi (Hill climbing) là tên chung để chỉ một họ các thuật toán có nguyên lý giống nhau. 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 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.17). 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 54 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm 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. Thuật toán leo đồi còn được gọi là thuật toán tìm cục bộ tham lam do tại mỗi thời điểm thuật toán này chỉ xét một láng giềng tốt mà không quan tâm tới tương lai xa hơn. 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.18. Bước 1 là bước khởi tạo, trong đó ta chọn ngẫu nhiên trạng thái xuất phát. Bước 2 sinh ra các láng giềng của trạng thái hiện thời. Ở bước 3, thuật toán kiểm tra các láng giềng, nếu không có láng giềng nào tốt hơn thuật trạng thái hiện thời (tất cả láng giềng có giá trị hàm mục tiêu Obj không lớn hơn Obj của trạng thái hiện thời) thì kết thúc và trả về trạng thái hiện thời là kết quả. Trong trường hợp ngược lại, ở bước 4, thuật toán chọn láng giềng có giá trị hàm mục tiêu Obj lớn nhất và chuyển sang trạng thái đó, sau đó lặp lại từ bước 2. Đầ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. If ∀yi ∈ Y: Obj (yi) < Obj (x) then Kết thúc và trả lại x là kết quả 4. x ← yi , trong đó i = argmaxi (Obj (yi)) 5. Go to 2 Hình 2.18. 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. Trong các thuật toán trình bầy ở phần trước, khi lập trình cần sử dụng các cấu trúc dữ liệu để biểu diễn các nút, nhớ tập biên. Thuật toán leo đồi không đòi hỏi phải lập trình với các cấu trúc như vậy. - Như các giải thuật tìm kiếm cục bộ khác, leo đồi sử dụng ít bộ nhớ do không phải lưu lại các trạng thái. Tại mỗi thời điểm, thuật toán chỉ cần lưu lại trạng thái hiện thời và một tráng thái láng giềng. - Bên cạnh hai ưu điểm trên, leo đồi 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.17. Nếu bắt đầu từ một 55 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm trạng thái nằm trong phạm vi của các vùng “đồi” thấp, thuật toán sẽ di chuyển về trạng thái tương ứng với đỉnh đồi, sau đó dừng lại ở đỉnh do các trạng thái xung quanh đều không tốt bằng. Mặc dù đỉnh đồi thấp tương ứng với trạng thái tốt nhất trong một vùng, trạng thái đó không phải là trạng thái tối ưu trong toàn bộ không gian trạng thái. Để 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 đó. Nếu số lần thực hiện với trạng thái xuất phát ngẫu nhiên như vậy được thực hiện đủ nhiều thì xác suất tìm ra lời giải tối ưu sẽ tiến tới 1. Khi thiết kế thuật toán leo đồi với cách chuyển động sang trạng thái láng giềng tốt nhất, việc lựa chọn chuyển động rất quan trọng. Nếu nhiều chuyển động, từ trạng thái hiện thời có thể sinh ra nhiều láng giềng. Do thuật toán cần so sánh tất các láng giềng để tìm ra trạng thái tốt nhất, mỗi bước của vòng lặp sẽ đòi hỏi nhiều thời gian do phải tính hàm mục tiêu cho tất cả láng giềng. Ngược lại, nếu sinh ra tập láng giềng 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. Ví dụ minh hoạ 1: bài toán 8 con hậu. Ta sẽ quy định mỗi trạng thái là sắp xếp của cả 8 con hậu trên bàn cờ, sao cho mỗi cột chỉ gồm 1 con. Trạng thái xuất phát được khởi tạo ngẫu nhiên. Hàm mục tiêu là hàm heuristic được tính bằng số các đôi hậu đang đe dọa nhau. Như vậy hàm mục tiêu càng nhỏ thì càng gần với trạng thái đích cần tìm. Trạng thái đích là trạng thái có hàm mục tiêu nhỏ nhất (bằng 0). Để minh họa cho ảnh hưởng của việc lựa chọn hàm chuyển động, ta xét hai cách chuyển động sau. Cách 1: chọn một cột, dịch chuyển quân hậu trong cột đó sang dòng khác. Với cách chuyển động như vậy, từ mỗi trạng thái có thể sinh ra 7 x 8 = 56 láng giềng. Trên hình 2.19 a là ví dụ một trạng thái với hàm mục tiêu bằng 17, đồng thời trên các ô trống là giá trị hàm mục tiêu (số đôi hậu đe dọa nhau) ứng với chuyển động di chuyển quân hậu trong cùng cột tới ô đó. Với số lượng láng giềng tương đối ít, cách này dễ dẫn tới cực trị địa phương, chẳng hạn trạng thái trên hình 2.18 b có hàm mục tiêu = 2 nhưng tất cả láng giềng đều có hàm mục tiêu lớn hơn và do vậy không tìm được lời giải. Cách 2: chọn hai cột, dịch chuyển đồng thời mỗi quân hậu trong hai cột đó sang dòng khác với dòng hiện thời. Cách này tạo ra 7 x 8 + 7 x 7 láng giềng cho mỗi trạng thái. Mặc dù số lượng láng giềng lớn đòi hỏi mỗi bước lặp phải tính toán nhiều gần gấp đôi so với cách 1 nhưng sẽ ít khả năng dẫn tới cực trị địa phương như trạng thái trên hình 2.19 b hơn. 56 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm (a) (b) Hình 2.19. Bài toán 8 con hậu với giá trị hàm mục tiêu cho mỗi trạng thái láng giềng (a) và trạng thái cực trị địa phương (b) 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.20. Đầ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.20. Thuật toán leo đồi ngẫu nhiên Các thực nghiệm trên nhiều bài toán cho thấy, trong trường hợp mỗi trạng thái có nhiều láng giềng, leo đồi ngẫu nhiên cho kết quả nhanh hơn do thuật toán có thể chuyển sang trạng thái tiếp theo mà không cần khảo sát toàn bộ tập láng giềng. Ngoài ra, leo đồi ngẫu nhiên cũng ít gặp phải cực trị địa phương hơn leo đồi chuyển sang trạng thái tốt nhất. Nhìn chung, khả năng tìm được lời giải tối ưu của các thuật toán leo đồi phụ thuộc nhiều vào không gian trạng thái. Đối với những không gian có ít cực trị địa phương, leo đồi thường tìm được lời giải khá nhanh. Trong trường hợp không gian trạng thái phức tạp, thuật toán thường chỉ tìm được cực trị địa phương. Tuy nhiên, bằng cách thực hiện nhiều lần với trạng thái xuất phát ngẫu nhiên, leo đồi thường tìm được cực trị địa phương khá tốt. Ví dụ minh hoạ 2: Bài toán người bán hàng. Cho một đồ thị gồm n nút, trong đó hai nút bất kỳ đều được nối với nhau bằng một cung. Cần tìm đường đi xuất phát từ một nút, qua tất cả các nút khác đúng một lần và quay về nút xuất phát sao cho độ dài đường đi là nhỏ nhất. 57 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm Bài toán này mô phỏng trường hợp một người bán hàng cần đi qua tất cả các thành phố đúng một lần và quay về nơi xuất phát với chi phí nhỏ nhất. Có thể áp dụng thuật toán leo đồi cho bài toán người bán hàng như sau. Trạng thái: Mỗi trạng thái là một chu trình Hamilton, tức là chu trình qua các đỉnh đúng một lần. Hàm mục tiêu: Là độ dài của chu trình Hamilton. Cần tìm trạng thái có hàm mục tiêu nhỏ nhất. Chuyển động: Chuyển động theo kiểu thay_đổi_k_cung, trong đó k = 2, 3, 4, … Ví dụ, với k = 2, từ trạng thái hiện thời ta lấy ra 2 cung không liền nhau, bỏ hai cung đó và nối nút đầu cung này với nút cuối cung kia để tạo ra 2 cung mới như ví dụ trên hình 2.21 (trên). Với mỗi cặp cung như vậy ta được một láng giềng mới của trạng thái hiện thời. Trong ví dụ đang xét, bằng cách thay đổi 2 cung, ta có thể tạo ra 20 láng giềng cho mỗi trạng thái. Tương tự, hình 2.21 (dưới) minh họa một số trạng thái láng giềng được tạo ra khi thực hiện thay_đổi_3_cung. Với đồ thị có nhiều nút, khi k tăng lên, số chuyển động và láng giềng tương ứng cũng tăng theo. A H B C D E G F A H B C D E G F A H B C D E G F (a) (b) A H B C D E G F A H B C D E G F (c) A H B C D E G F Hình 2.21. Ví dụ một trạng thái của bài toán người bán hàng (a), một số láng giềng sinh ra nhờ thay_đổi_2_cung (b), và một số láng giềng sinh ra nhờ thay_đổi_3_cung. Với các đồ thị có vài chục nút trở lên, các nghiên cứu thực nghiệm cho thấy một số kết quả sau. Giá trị k = 3 cho kết quả tốt hơn nhiều (thường tìm được đường đi ngắn hơn) so với k = 2. Việc sử dụng k = 4 và lớn hơn không cải thiện chất lượng lời giải đáng kể so với k = 3, trong khi đòi hỏi khối lượng tính toán lớn hơn nhiều do tập láng giềng lớn. 58 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm 2.5.2. Thuật toán tôi thép 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 hay mô phỏng luyện kim (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. 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.22. Khác với thuật toán leo đồi, trong đó ta luôn chuyển động sang trạng thái tốt hơn và do vậy trạng thái hiện thời luôn là trạng thái tốt nhất, thuật toán tôi thép có thể di chuyển sang trạng thái kém hơn. Do vậy, thuật toán tôi thép sử dụng một biến x* để lưu trạng thái tốt nhất đã từng khảo sát, tính tới thời điểm hiện tại. Lệnh if rand[0,1] < p then x ← y có nghĩa là gán y cho x với xác suất p, trong đó rand[0,1] là hàm trả về giá trị ngẫu nhiên trong khoảng [0,1]. Lệnh này có thể triển khai trên máy tính có hàm sinh số tự nhiên. 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 59 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiế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 //gán y cho x với xác suất p. 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.22. 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 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: 1 0* t k T T t+ = α * Trong đó: T0 > 0 là giá trị ban đầu, α thuộc (0,1), 1 < k < m Với sơ đồ làm lạnh này, khi số vòng lặp tăng lên, tức là t tăng, giá trị của T giảm. Tiếp theo, từ công thức tính xác suất sử dụng trong thuật toán, có thể nhận thấy khi T tăng và tiến tới vô cùng, xác suất p → 1 mọi ∆(x, y). Khi đó, thuật toán chấp nhận bất chuyển động nào bất kể trạng thái mới tốt hơn hay kém hơn, tức là thuật toán di chuyển ngẫu nhiên trong không gian trạng thái. Ngược lại, khi T → 0, ta có p → 0 với mọi ∆(x, y), tức là thuật toán không chấp nhận các trạng thái kém hơn trạng thái hiện thời và do vậy trở thành leo đồi ngẫu nhiên. Như vậy, có thể coi thuật toán tôi thép là sự kết hợp giữa leo đồi ngẫu nhiên với chuyển động ngẫu nhiên, trong đó khởi đầu xu hướng chuyển động ngẫu nhiên lớn hơn, và càng về cuối, xu hướng leo đồi càng chiếm ưu thế. 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ể. 60 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm 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ế. Nhiều ứng dụng cho thấy, thuật toán tôi thép có khả năng tìm được lời giải tốt hơn so với thuật toán leo đồi. 2.5.3. Giải thuật di truyền Giải thuật di truyền (genetic algorithm) hay thuật toán di truyền là thuật toán tìm kiếm được thiết kế dựa trên sự tương tự với quá trình chọn lọc tự nhiên và thuyết tiến hoá của Charles Darwin. Giải thuật di truyền là trường hợp riêng của một lớp giải thuật được gọi là giải thuật tiến hoá (evolutionary algorithms). Giải thuật di truyền cho lời giải tốt trong nhiều bài toán tối ưu và được sử dụng rộng rãi trong rất nhiều ứng dụng khác nhau. Về mặt thuật toán, có thể xem giải thuật di truyền như một phiên bản leo đồi ngẫu nhiên với một số khác biệt chính. Thứ nhất, thuật toán đồng thời duy trì nhiều lời giải tại mỗi thời điểm thay vì một lời giải như leo đồi. Thứ hai, từng cặp lời giải có thể trao đổi thành phần với nhau để tạo ra lời giải mới. Về mặt ý tưởng, giải thuật di truyền học tập từ quá trình sinh tồn và chọn lọc tự nhiên của sinh vật trong tự nhiên, trong đó cá thể với khả năng thích nghi cao hơn sẽ chiếm ưu thế và tồn tại. Nếu ta coi đây là bài toán tối ưu thì quá trình tiến hoá sẽ sinh ra cá thể tối ưu, tức là cá thể thích nghi cao. 1) Nguyên lý chung. Giải thuật di truyền mô phỏng quá trình tiến hoá qua các thế hệ trong tự nhiên như sau. Mỗi thế hệ gồm một số nhất định lời giải, còn gọi là cá thể. Mỗi lời giải hay cá thể được biểu diễn bằng một nhiễm sắc thể, chứa các gen. Độ tốt của lời giải được đánh giá bằng hàm thích nghi (fitness). Thông thường, hàm thích nghi chính là hàm mục tiêu của bài toán tối ưu. Các lời giải trong mỗi thế hệ được biến đổi trong quá trình thích nghi để tạo ra thế hệ tiếp theo. Nguyên bản sinh học. Trong sinh học, mỗi cá thể được mã hoá di truyền bằng bộ gen, bộ gen có thể gồm nhiều nhiễm sắc thể như của người hoặc động vật bậc cao, mỗi nhiễm sắc thể gồm nhiều gen. Khi sinh sản, hai cá thể bố mẹ trao đổi các gen với nhau, cá thể con nhận một số gen từ bố và một số gen từ mẹ. Giải thuật di truyền sử dụng các quy tắc sau để tạo ra thế hệ lời giải tiếp theo. - Các cá thể cạnh tranh với nhau. Cá thể với độ thích nghi cao hơn sẽ tạo ra nhiều hậu duệ hơn cá thể kém thích nghi. - Gen từ các cá thể thích nghi tốt được kết hợp với nhau, nhờ đó có thể tạo ra hậu duệ tốt hơn tổ tiên. - Từng cá thể cũng có thể thay đổi gen của mình. - Nhờ vậy, thế hệ tiếp theo sẽ chứa cá thể thích nghi hơn với môi trường. 2) Biểu diễn lời giải và không gian tìm kiếm Để sử dụng giải thuật di truyền, trước hết mỗi lời giải phải được biểu diễn bằng một nhiễm sắc thể, chứa các gen. Ở đây, nhiễm sắc thể là một vec tơ có độ dài xác định, mỗi phần tử của vec tờ là một gen. Thông thường, lời giải được biểu diễn bằng vec tơ nhị phân, tức là 61 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm phần tử nhận giá trị {0, 1}, nhưng cũng có thể sử dụng phần tử là số hoặc chữ. Ví dụ của gen, nhiễm sắc thể, và quần thể được minh hoạ trên hình 2.23. 1 1 0 1 0 1 0 0 0 1 1 0 0 1 1 0 0 1 0 0 1 1 0 1 … 0 0 0 1 0 1 1 1 0 1 1 0 gen Nhiễm sắc thể Quần thể Hình 2.23. Ví dụ biểu diễn lời giải và quần thể trong giải thuật di truyền Mỗi lời giải được gán một độ thích nghi thể hiện khả năng cạnh tranh của lời giải. Thông thường, độ thích nghi được tính từ hàm mục tiêu của bài toán, hàm mục tiêu tốt tương đương với độ thích nghi cao. Giải thuật thực hiện qua nhiều bước lặp, mỗi bước lặp tương ứng với một thế hệ. Tại mỗi thế hệ, giải thuật duy trì một quần thể, tức là một tập hợp gồm N lời giải, trong đó N là tham số. Quần thể trong thế hệ đầu tiên được khởi tạo ngẫu nhiên bằng cách sinh ngẫu nhiên các lời giải. Từ quần thể hiện tại, từng cặp cá thể được lựa chọn dựa trên độ thích nghi và được lai ghép với nhau để tạo ra cá thể con. Cá thể với độ thích nghi cao được lựa chọn với xác suất cao hơn. Cá thể con được tạo ra như vậy sẽ thay thế cá thể bố mẹ để tạo ra quần thể mới trong thế hệ tiếp theo. Như vậy, thế hệ tiếp theo sẽ chứa các lời giải với các gen tốt hơn mức trung bình trong thế hệ trước. Nói cách khác, thế hệ sau chứa các lời giải thành phần tốt hơn thế hệ trước. Thuật toán lặp lại cho đến khi cá thể trong thế hệ tiếp theo không khác nhiều so với thế hệ trước. Khi đó thuật toán được gọi là hội tụ. Cũng có thể sử dụng các tiêu chí kết thúc khác, chẳng hạn sau khi lặp một số lần nhất định. 2) Giải thuật Quần thể đầu tiên được khởi tạo ngẫu nhiên. Sau đó thuật toán được thực hiện qua nhiều bước lặp, tại mỗi bước lặp thuật toán sinh ra một quần thể mới. Các quần thể tiếp theo được tạo ra từ quần thể trước đó bằng cách áp dụng ba thao tác: chọn lọc, lai ghép, và đột biến. Để minh hoạ cho các bước của thuật toán, ta xét ví dụ bài toán 8 quân hậu, trong đó mỗi quân hậu được đặt trong một cột riêng. Mỗi trạng thái gồm thông tin về vị trí 8 quân hậu trong cột của mình. Nếu chọn biểu diễn dưới dạng chuỗi bit, cần 3 bit cho một vị trí, tức là 24 bit cho mỗi trạng thái. Nếu biểu diễn dưới dạng chuỗi số thập phân, cần 8 chữ số thập phân cho mỗi trạng thái. Trong ví dụ minh hoạ này, ta sẽ dùng biểu diễn dưới dạng thập phân như minh hoạ trên hình 2.24 và 2.25. Chẳng hạn, nhiễm sắc thể 24415124 cho biết quân hậu thứ nhất nằm ở hàng thứ 2 trong cột đầu tiên bên trái, quân thứ hai nẳm ở hàng 4 trong cột tiếp theo 62 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm v.v. Do trạng thái tốt ứng với giá trị hàm thích nghi lớn nên ta sẽ chọn độ thích nghi bằng số lượng đôi hậu không đe doạ nhau. Trạng thái lời giải là trạng thái có độ thích nghi bằng 28. Chọn lọc (selection). Chọn lọc cá thể để tham gia việc tạo ra thế hệ tiếp theo. Cá thể có độ thích nghi càng cao càng có nhiều khả năng được chọn. Có nhiều phương pháp thực hiện lựa chọn như vậy, chi tiết sẽ được trình bầy ở dưới. Trong ví dụ trên hình 2.24, cá thể thứ nhất được chọn 1 lần, các thể thứ hai được chọn 2 lần, cá thể thứ ba được chọn một lần, cá thể thứ tư không được chọn. Lai ghép (crossover), còn gọi là trao đổi chéo, hay tái tổ hợp. Lai ghép là thao tác kết hợp các phần từ nhiễm sắc thể của bố và mẹ để tạo ra hai cá thể con với một xác suất nhất định. Cá thể bố và mẹ được lựa chọn bằng cách sử dụng thao tác chọn lọc ở trên. Sau đó, nhiễm sắc thể bố và mẹ được cắt ra. Phần đầu nhiễm sắc thể bố được nối với phần đuôi nhiễm sắc thể mẹ và ngược lại. Trên hình 2.24, vị trí cắt ở giữa gen thứ 6 và gen thứ 7. Cũng có thể cắt mỗi nhiễm sắc thể bố mẹ thành nhiều hơn hai phần và ghép các phần con với nhau. Việc chọn điểm cắt và số phần con phụ thuộc bài toán cụ thể. Như vậy, nhờ kết quả lai ghép, mỗi cá thể con nhận một phần gen từ bố và một phần gen từ mẹ. Lưu ý là, với mỗi cặp bố mẹ, thao tác lai ghép được thực hiện với một xác suất nhất định gọi là xác suất lai ghép. Xác suất này thường được chọn lớn hơn 0.5. Đột biến (mutation). Thay đổi giá trị các gen của cá thể con vừa tạo ra với một xác suất nhất định. Cụ thể, với mỗi cá thể con, duyệt các gen và với một xác suất rất nhỏ thay đổi giá trị của gen đó (0 thành 1 và ngược lại nếu biểu diễn nhị phân). Xác suất này thường được chọn nhỏ hơn 0.1 để tránh đột biến quá nhiều. Trong ví dụ hình 2.24, các gen thứ 4 của cá thể con số 1 và gen thứ 8 của cá thể con số 4 được thay đổi giá trị. Mục đích của thao tác đột biến là để tạo ra những đoạn gen hoàn toàn mới, chưa có trong quần thể cha mẹ. Đột biến cũng cho phép hạn chế việc hội tụ quá sớm của thuật toán. Về bản chất, đột biến có hiệu quả tương tự di chuyển ngẫu nhiên trong không gian trạng thái, có thể cho phép vượt qua các trường hợp cực trị địa phương. Tại mỗi bước lặp, thuật toán thực hiện ba thao trên này để sinh ra quần thể mới. Quá trình lặp được thực hiện cho tới khi thuật toán hội tụ, tức là cá thể con không khác nhiều cá thể bố mẹ, hoặc khi thực hiện đủ một số lượng vòng lặp do người dùng quy định. Toàn bộ thuật toán được trình bầy trên hình 2.26. 63 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm Hình 2.24. Ví dụ minh hoạ các thao tác của giải thuật di truyền với bài toán 8 quân hậu. Mỗi lời giải được biểu diễn bằng chuỗi 8 chữ số tương ứng với vị trí của mỗi quân trong cột tương ứng. Hàm thích nghi được tính bằng số đôi hậu không đe doạ nhau và thể hiện bằng số ở phía trên lời giải (chỉ thể hiện cho quần thể ban đầu) Hình 2.25. Bàn cờ minh hoạ kết quả lai ghép giữa hai nhiễm sắc thể bố mẹ thứ 1 và 2, dòng 2, trên hình 2.24 GA(X, f, N, c, m) Đầu vào: bài toán tối ưu với không gian trạng thái X hàm thích nghi f kích thước quần thể N 64 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm xác suất lai ghép c xác suất đột biến m Đầu ra: lời giải (cá thể) với độ thích nghi cao Khởi tạo: Khởi tạo ngẫu nhiên quần thể G gồm N lời giải ------------------------------------------------ While (chưa thoả mãn điều kiện dừng) do 1. For i = 1 to N do Tính giá trị hàm thích nghi f(i) cho cá thể thứ i 2. For i = 1 to ⎣N/2⎦ do i. Chọn lọc: chọn 2 cá thể bố mẹ x và y từ G tuỳ theo giá trị thích nghi ii. Lai ghép: với xác suất c, đổi chỗ đoạn gen trên x và y iii. Đột biến: với xác suất m, thay đổi giá trị các gen trên cá thể mới tạo ra iv. Thêm cá thể mới vào quần thể mới G’ 3. Gán G ← G’ Return: Lời giải thuộc G với giá trị thích nghi tốt nhất Hình 2.26. Giải thuật di truyền 3) Một số chi tiết Các phương pháp thực hiện chọn lọc. Việc chọn lọc cá thể có thể thực hiện theo nhiều cách, ví dụ các cách sau: - Bánh xe ru let: là phương pháp thường dùng nhất. Bánh xe ru let là phương pháp chọn ngẫu nhiên hay dùng trong một trò chơi ở sòng bạc. Theo phương pháp này, xác suất lựa chọn một lời giải tỷ lệ thuận với độ thích nghi của lời giải đó. Ta có thể hình dung tổng giá trị thích nghi của quần thể được biểu diễn bằng một hình tròn, hay một bánh xe ru let. Các hình quạt của bánh xe được gán cho các lời giải sao cho kích thước hình quạt tỷ lệ thuận với độ thích nghi của lời giải. Ta có thể cho bánh xe quay và tung hòn bi để chọn lời giải tương ứng với hình quạt mà hòn bi dừng lại. Giả sử f(i) là độ thích nghi của lời giải thứ i. Theo phương pháp bánh xe ru let, xác suất chọn lời giải thứ i được tính theo công thức: p(i) = f (i)f (i) ∑ i=1..N Phương pháp bánh xe ru lét có thể cài đặt bằng thuật toán sau: + Tính tổng giá trị thích nghi của tất cả cá thể trong quần thể, gọi tổng này là S. + Sinh ra số ngẫu nhiên trong khoảng (0, S), gọi số này là r. + Lần lượt cộng giá trị thích nghi của từng cá thể trong quần thể, gọi tổng này là s. Khi nào s > r thì dừng và trả về cá thể hiện thời. 65 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm - Thi đấu: chọn ngẫu nhiên một đôi cá thể sử dụng phân bố xác suất đều, sau đó chọn cá thể tốt hơn trong hai cá thể đó như một cá thể cha mẹ. Thực hiện tương tự để chọn cá thể cha mẹ còn lại. - Lựa chọn cá thể tinh hoa (Elitism). Các phương pháp trên đều không đảm bảo cá thể tốt nhất được lựa chọn. Trong phương pháp lựa chọn tinh hoa, một số lượng nhất định các cá thể tốt nhất được lựa chọn trước, sau đó phần còn lại được lựa chọn theo các phương pháp ru lét hay thi đấu như ở trên. Như vậy, các cá thể tốt nhất luôn được duy trì đoạn gen của mình sang thế hệ sau và tránh làm mất lời giải tốt nhất đã tìm được. - Loại bỏ các cá thể có hàm thích nghi nhỏ hơn một ngưỡng nhất định, sử dụng các cá thể còn lại để lai ghép và tạo quần thể mới. Giá trị xác suất. Xác suất lai ghép. Nếu xác suất lai ghép là 1 (100%) thì toàn bộ cá thể con sẽ được tạo ra do lai ghép. Ngược lại, nếu xác suất lai ghép là 0 thì toàn bộ cá thể con là bản sao của một số cá thể bố mẹ nhưng không nhất thiết quần thể tiếp theo trùng với quần thể cũ. Như đã nói ở trên, xác suất lai ghép được lựa chọn tương đối lớn, thường từ 0.5 trở lên. Xác suất đột biến. Nếu xác suất đột biến là 100% thì toàn bộ cá thể sau khi lai ghép sẽ bị thay đổi. Ngược lại, nếu xác suất này là 0 thì không cá thể nào bị thay đổi. Xác suất đột biến được lựa chọn rất nhỏ, ít khi vượt quá 0.1. Xác suất đột biến nhỏ để tránh cho thuật toán di chuyển theo kiểu ngẫu nhiên. Kích thước quần thể. Kích thước quần thể N là số lượng cá thể được duy trì trong mỗi thế hệ. Nếu N quá nhỏ, thuật toán có ít lựa chọn để thực hiện lai ghép, dẫn tới chỉ một phần không gian tìm kiếm được khảo sát và do vậy có thể không tìm được lời giải tốt. Nếu N quá lớn, thuật toán sẽ thực hiện chậm do phải xử lý nhiều trong mỗi vòng lặp. Giá trị tốt của N phụ thuộc vào bài toán cụ thể và cách mã hoá lời giải. Tuy nhiên, nhiều kết quả thực nghiệm cho thấy, khi N tăng tới một mức độ nào đó, chất lượng lời giải không tăng, trong khi thuật toán sẽ chậm hơn. Mã hoá lời giải Lời giải hay cá thể cần được mã hoá dưới dạng nhiễm sắc thể. Cách mã hoá cụ thể phụ thuộc rất nhiều vào từng bài toán. Sau đâu là một số cách mã hoá thường gặp. - Mã hoá dưới dạng chuỗi bit hay dạng nhị phân. Mỗi nhiễm sắc thể là một vec tơ gồm các số 0 hoặc 1 như ví dụ trên hình 2.23. Đây là cách mã hoá thông dụng nhất. Cách mã hoá tạo ra rất nhiều nhiễm sắc thể. Tuy nhiên, với nhiều bài toán, cách mã hoá này không tự nhiên và việc lai ghép hay đột biến có thể tạo ra nhiễm sắc thể không tương ứng với lời giải hợp lệ nào và do vậy cần xử lý để nhận được lời giải hợp lệ. - Mã hoá dưới dạng các hoán vị. Cách mã hoá này thường sử dụng trong bài toán cần xác định thứ tự như đường đi hay thời khoá biểu. Ví dụ, trong bài toán người bán hàng đã trình bầy trong phần trước, mỗi gen tương ứng với một thành phố và nhiễm sắc thể mã hoá thứ tự đường đi dưới dạng hoán vị thứ tự thành phố (1 ứng với A, 2 với B v.v.). Nhiễm sắc thể 1 5 3 2 6 4 7 9 8 66 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm - Mã hoá dưới dạng các giá trị. Trong một số trường hợp, các giá trị như số thực được sử dụng để biểu diễn lời giải. Việc sử dụng trực tiếp số thực là cần thiết do việc biểu diễn bằng bit trong trường hợp này rất phức tạp. Với cách mã hoá này, nhiễm sắc thể là một chuỗi giá trị, trong đó giá trị có thể là số thực , số nguyên, chữ cái hoặc xâu ký tự. Trong bài toán 8 quân hậu ở trên, ta đã thấy vị trí các con hậu được biểu diễn bởi vec tơ các số nguyên như trên hình 2.24. Một ví dụ khác là khi huấn luyện mạng nơ ron, cần xác định trọng số cho các kết nối. Nhiễm sắc thể khi đó chứa các trọng số này. Dưới đây là ví dụ một số nhiễm sắc thể khi mã hoá kiểu này; Nhiễm sắc thể 1.2324 5.3243 0.4556 2.3293 2.4545 Nhiễm sắc thể ABDJEIFJDHDIERJFDL Nhiễm sắc thể (trên) (dưới) (dưới) (trái) (trên) (phải) Các phương pháp lai ghép Thao tác lai ghép rất đa dạng và phụ thuộc vào cấu trúc của lời giải trong bài toán cụ thể. Các lựa chọn bao gồm: - Lựa chọn điểm cắt. Thông thường sử dụng cùng điểm cắt trên cả bố và mẹ nhưng cũng có thể sử dụng điểm cắt khác nhau. Trường hợp sau sinh ra cá thể con có độ dài thay đổi và do vậy cần xử lý riêng sau đó. - Lựa chọn số đoạn gen. Thông thường nhiễm sắc thể được cắt làm hai phần nhưng cũng có thể nhiều hơn. Ví dụ lai ghép với một điểm cắt: 11001|011+11011|111 = 11001111 Ví dụ lai ghép với hai điểm cắt: 11|0010|11 + 11|0111|11 = 11011111 Với cách mã hoá kiểu hoán vị như trong bài toán người bán hàng, khi lai ghép với một điểm cắt, phần trước điểm cắt được lấy nguyên từ cá thể bố mẹ thứ nhất. Phần sau điểm cắt được tạo ra bằng cách lấy các số chưa được sử dụng từ cá thể bố mẹ thứ hai (thay vì lấy nguyên cả đoạn từ sau điểm cắt). Cách này đảm bảo để mỗi số chỉ xuất hiện đúng một lần (cần lưu ý là có những cách khác cho phép đảm bảo điều này). Ví dụ: (1 2 3 4 5 6 7 8 9) + (4 5 3 6 8 9 7 2 1) = (1 2 3 4 5 6 8 9 7) - Lai ghép đều. Trong phương pháp này, mỗi gen được sao chép từ bố hoặc từ mẹ với xác suất bằng nhau. Ví dụ lai ghép đều: 11101011 + 11011101 = 11111111 - Lai ghép số học. Áp dụng phép tính số học hoặc logic trên cặp bit tương ứng của bố và mẹ. Ví dụ: 11001011 + 11011111 = 11001001 (AND) 67 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm - Có thể sử dụng ba cha mẹ thay vì hai. Các phương pháp tạo đột biến Đối với cách mã hoá nhị phân, đột biến được thực hiện bằng cách đổi giá trị các bit được chọn. Đối với mã hoá dạng hoán vị: hai số được chọn và đổi vị trí cho nhau. Ví dụ: (1 2 3 4 5 6 8 9 7) => (1 8 3 4 5 6 2 9 7) Đối với mã hoá dạng vec tơ các giá trị: thay đổi giá trị các gen được chọn như trong ví dụ 8 quân hậu ở trên. 4) Hiệu ứng của các thao tác Các thao tác chọn lọc, lai ghép và đột biến có các hiệu ứng như sau khi được sử dụng riêng rẽ hoặc kết hợp với các thao tác khác. - Nếu chỉ sử dụng thao tác chọn lọc thì thuật toán có xu hướng chọn cá thể tốt nhất từ thế hệ trước. Như vậy chỉ có thể tăng độ thích nghi trung bình và tránh lời giải ít thích nghi chứ không tạo ra lời giải tốt hơn lời giải tốt nhất của thế hệ trước. - Kết hợp chọn lọc và lai ghép có xu hướng khiến thuật toán hội tụ ở lời giải tương đối tốt nhưng không tối ưu. - Sử dụng một mình thao tác đột biến sinh ra chuyển động ngẫu nhiên. Nếu chỉ sử dụng một mình thao tác đột biến, thuật toán sẽ không di chuyển về hướng có lời giải tốt. - Sử dụng chọn lọc kết hợp với đột biến tạo ra một dạng leo đồi song song ổn định hơn leo đồi thông thường. Như vậy, giải thuật di truyền có thể coi như một biến thể mở rộng của tìm kiếm leo đồi ngẫu nhiên thực hiện song song trên một tập hợp các lời giải. 2.5.4. 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: 1) Tìm kiếm tabu. Tìm kiếm tabu (Tabu search) có thể coi như sự kết hợp của leo đồi với một số kỹ thuật cho phép tránh cực trị địa phương. Cụ thể, thuật toán cho phép chuyển sang các láng giềng không tốt hơn trạng thái hiện thời. Tuy nhiên, để tránh xét lại các trạng thái đã sử dụng trước đó, 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 và không được xem xét nữa. Kích thước của danh sách cấm là hữu hạn và sau một thời gian, các nút được lưu vào danh sách cấm từ trước sẽ bị đẩy ra khỏi danh sách và lại có thể xem xét lại. 2) Tìm kiếm chùm cục bộ Tìm kiếm chùm cục bộ (Local beam search) là phương pháp tìm kiếm cục bộ tương tự leo đồi nhưng thay vì chỉ lưu một trạng thái tại mỗi thời điểm, tìm kiếm chùm lưu k trạng thái. Ở mỗi vòng lặp, thuật toán sinh ra tất cả láng giềng của toàn bộ k trạng thái và kiểm tra các láng giềng này. Nếu một trong các trạng thái mới sinh ra là đích thì thuật toán dừng và trả về 68 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm kết quả. Nếu ngược lại, thuật toán chọn k trạng thái tốt nhất trong số mới sinh ra và chuyển sang vòng lặp tiếp theo. Như vậy, thuật toán đồng thời duy trì một “chùm” gồm k trạng thái. Hiệu quả của việc duy trì k trạng thái là nếu một trạng thái sinh ra các láng giềng tốt hơn các trạng thái còn lại thì thuật toán sẽ tập trung vào các láng giềng của trạng thái này và như vậy sẽ bỏ hướng tìm kiếm sinh ra từ các trạng thái còn lại. Điều này giúp tìm kiếm chùm có kết quả khác với việc chạy đồng thời k phiên bản leo đồi ngẫu nhiên. Tìm kiếm chùm sẽ nhanh chóng từ bỏ những hướng tìm kiếm trông có vẻ không hứa hẹn. Do có xu hướng từ bỏ sớm những hướng tìm kiếm trông không hứa hẹn, tìm kiếm chùm có xu hướng tập trung vào một vùng nhỏ trong không gian tìm kiếm và bỏ qua các vùng có lời giải tối ưu. Để giảm bớt hiệu ứng này, có thể sử dụng phiên bản tìm kiếm chùm ngẫu nhiên, theo đó thay vì giữ lại k trạng thái tốt nhất cho vòng lặp sau, thuật toán chọn ngẫu nhiên k trạng thái sao cho trạng thái tốt hơn có xác suất lớn hơn. Cách chọn này tương tự thao tác chọn lọc sử dụng bánh xe ru lét trong giải thuật di truyền. Phương pháp tối ưu đàn kiến Tối ưu đàn kiến (Ant colony optimization) là phương pháp tối ưu xác suất được Marco Dorigo đề xuất vào năm 1992, ban đầu để giải bài toàn tìm đường tối ưu trên đồ thị. Phương pháp tối ưu đàn kiến sau đó có thể mở rộng để giải quyết các bài toán tối ưu bằng cách quy về bài toán tìm đường ngắn nhất trên đồ thị. Ý tưởng phương pháp này dựa trên hành vi của đàn kiến khi di chuyển giữa tổ và nơi có thức ăn. Trong trường hợp giữa tổ kiến và nguồn thức ăn có nhiều đường đi, sau một thời gian đàn kiến sẽ tập trung đi theo đường đi ngắn nhất mặc dù kiến không có bản đồ và có thể mù. Kết quả này đạt được nhờ cơ chế sau. Khởi đầu kiến di chuyển ngẫu nhiên theo các đường đi có thể giữa hai điểm. Trong quá trình di chuyển, các con kiến để lại trên đường đi các pheromone, một dạng chất sinh học mà kiến sinh ra và có thể cảm nhận được. Nếu kiến đi theo đường ngắn hơn thì sẽ mau trở lại hơn và chuyển động được nhiều lần hơn trên đường ngắn hơn này. Kết quả là sau một thời gian, đường đi ngắn hơn sẽ có lượng pheromone nhiều hơn. Các con kiến đi sau đó sẽ tập trung theo đường đi có nhiều pheromone, tức là đường ngắn. Thuật toán tối ưu đàn kiến được thực hiện bằng cách lựa chọn các cung trên đồ thị với xác suất tỷ lệ thuận với lượng pheromone trên cung đó. Mỗi khi di chuyển qua một cung, thuật toán cũng cập nhật để tăng lượng pheromone trên cung. Phương pháp tối ưu đàn kiến được sử dụng trong một số bài toán tối ưu như định tuyến mạng, quy hoạch mạng giao thông. Ưu điểm của phương pháp này so với tôi thép và giải thuật di truyền là có thể thực hiện rất nhanh trong trường hợp cấu trúc mạng thay đổi. Nhờ vậy, thuật toán cho phép tìm giải pháp cho bài toàn định tuyến mạng khi cấu trúc mạng là động và thay đổi theo thời gian thực. 2.6. ỨNG DỤNG MINH HOẠ Trên thực tế, tìm kiếm cục bộ và tìm kiếm heuristic được sử dụng rộng rãi nhất do khả năng giải quyết những bài toán thực kích thước lớn. Các thuật toán heuristic và tìm kiếm cục bộ được dùng để giải quyết nhiều bài toán tối ưu như tìm đường đi, thiết kế vi mạch, lập lịch sản xuất, làm thời khoá biểu v.v. 69 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm Trong phần 2.5.1, ta đã xem xét cách giải quyết bài toán người bán hàng bằng thuật toán leo đồi. Bài toán người bán hàng cũng có thể giải quyết bằng thuật toán tôi thép với cùng cách lựa chọn trạng thái xuất phát, chuyển động và hàm mục tiêu như đã trình bầy cho leo đồi. Để giải quyết bằng giải thuật di truyền có thể dùng cách biểu diễn lời giải và các thao tác lựa chọn, lai ghép, đột biến như trình bầy trong phần về giải thuật di truyền. Các thực nghiệm cho thấy thuật toán tôi thép và giải thuật di truyền thường cho kết quả tốt hơn (đường đi ngắn hơn) so với leo đồi. Trong phần này, ta sẽ xem xét cách sử dụng tìm kiếm cục bộ, cụ thể là thuật toán leo đồi ngẫu nhiên và tìm kiếm tabu, trong một bài toán có nhiều ứng dụng: xếp thời khoá biểu cho trường trung học (cơ sở và phổ thông). Các kỹ thuật trình bầy ở đây cũng có thể áp dụng trong xếp thời khoá biểu cho trường đại học với một số bổ sung và điều chỉnh phù hợp. Yêu cầu chung: Xếp thời khoá biểu là bài toán xác định giáo viên nào dậy lớp nào vào tiết nào sao cho thoả mãn một số ràng buộc như không có giáo viên nào dậy hai lớp cùng một lúc hay không có lớp nào học hai môn cùng một lúc v.v. Để đơn giản, ta sẽ giả sử thời khoá biểu của các tuần là giống nhau và do vậy chỉ cần lập thời khoá biểu cho một tuần. Phát biểu bài toán: Giả sử có m lớp học c1, …, cm , n giáo viên t1,…,tn , và p tiết học trong một tuần 1,…,p. Ma trận R kích thước m x n thể hiện phân công giáo viên, sao cho phần tử rij là số tiết mà giáo viên tj phải dậy cho lớp ci trong một tuần. Hai ma trận Tn x p và Cm x p thể hiện các tiết mà giáo viên và lớp có thể dậy hoặc học. Cụ thể, tjk = 1 nếu giáo viên j có thể dậy vào tiết k, và tjk = 0 nếu ngược lại, chẳng hạn giáo viên nữ có con nhỏ không phải dậy tiết đầu buổi sáng. Tương tự, cik =1 (hoặc 0) nếu lớp i có thể học (hoặc không) vào tiết k, chẳng hạn có thể quy định để mỗi lớp có một số tiết trống vào những giờ nhất định dành cho ngoại khoá. Tiếp theo, Dm x p là ma trận ràng buộc sao cho tjk =1 nếu lớp i bắt buộc phải học vào tiết k và tjk = 0 nếu không bắt buộc. Bài toán xếp thời khoá biểu được phát biểu như sau: Tìm xijk (i = 1..m, j = 1..n, k = 1..p) Thoả mãn các ràng buộc sau: xijk = 0 hoặc 1 (i = 1..m, j = 1..n, k = 1..p) (1) // xijk = 1 nếu giáo viên j dậy lớp i vào tiết k và xijk = 0 nếu ngược lại. p ∑ = rij (i =1..m, j =1..n) (2) xijk k=1 m ∑ (j =1..n, k =1..p) (3) xijk ≤ tjk i=1 n ∑ (i =1..m, k =1..p) (4) xijk ≤ cik j=1 n ∑ (i =1..m, k =1..p) (5) xijk ≥ dik j=1 Ràng buộc cứng: các ràng buộc (1) – (5) ở trên là các ràng buộc cứng, tức là ràng buộc mà lời giải buộc phải thoả mãn. Trong trường hợp cụ thể có thể thêm hoặc bớt ràng buộc cứng. Chẳng hạn có thể thêm ràng buộc thể hiện việc học lớp ghép trong một số môn học. 70 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm Ràng buộc mềm. Ngoài ràng buộc cứng còn có ràng buộc mềm, tức là ràng buộc không bắt buộc nhưng mong muốn thoả mãn càng nhiều càng tốt. Ràng buộc mềm sẽ đóng góp vào hàm mục tiêu của bài toán. Dưới đây là một số ràng buộc mềm thường gặp. Để tiện cho việc xây dựng hàm mục tiêu ở bên dưới, mỗi ràng buộc mềm được gán một trọng số w thể hiện điểm phạt khi một ràng buộc mềm như vậy bị vi phạm. - Gián đoạn (w1 = 6): hai tiết của một giáo viên cho cùng một lớp không nằm liền nhau. - Tiết trống (w2 = 1): giáo viên có tiết trống giữa các tiết dậy. - Dậy quá ít (w3 = 3): giáo viên dậy ít hơn mức tối thiểu trong một ngày. - Dậy quá nhiều (w4 = 3): giáo viên dậy nhiều hơn mức tối đa trong một ngày. - Phân bố không đều (w5 = 5): một giáo viên dậy quá nhiều tiết cho cùng một lớp trong một ngày (chẳng hạn nhiều hơn 2 tiết). Ràng buộc này đảm bảo các tiết của một giáo viên cho một lớp phân bố đều trong tuần. - Dậy vào thời gian không mong muốn (w6 = 3): giáo viên có thể đăng ký một số giờ không mong muốn. Số vi phạm được chuẩn hoá bằng cách chia đều cho số đăng ký. - Không có giờ thực hành (w7 = 10): không xếp được tiết liền nhau cho các môn có giờ thực hành. Cần lưu ý rằng các ràng buộc trên có thể thay đổi (thêm/bớt) cho từng trường hợp cụ thể. Giá trị mặc định của trọng số được dùng để minh hoạ và có thể thay đổi tuỳ vào độ quan trọng của từng loại ràng buộc với mỗi trường cụ thể. Hàm mục tiêu. Để sử dụng với thuật toán tìm kiếm cục bộ, các ràng buộc cứng và mềm cần được kết hợp thành một hàm mục tiêu duy nhất. Hàm mục tiêu được tính bằng số ràng buộc cứng bị vi phạm nhân với trọng số cho ràng buộc cứng cộng với số ràng buộc mềm bị vi phạm nhân với trọng số tương ứng. Các ràng buộc bị vi phạm được tính trên toàn bộ giáo viên và lớp. Hàm mục tiêu = số ràng buộc cứng vi phạm * w0 + số ràng buộc mềm loại i vi phạm * wi Giá trị trọng số mặc định w0 cho mỗi ràng buộc cứng bị vi phạm được chọn cao hơn ràng buộc mềm. Chẳng hạn, có thể chọn trọng số cho ràng buộc cứng: w0 = 20. Biểu diễn thời khoá biểu. Để thuật tiện cho việc thực hiện các chuyển động, thời khoá biểu (tức là các giá trị xijk) được biểu diễn dưới dạng ma trận Bn x k , trong đó mỗi dòng tương ứng với một giáo viên, mỗi cột tương ứng với một tiết. Phần tử bjk chứa số thứ tự của lớp mà giáo viên j dậy vào tiết k. Giá trị bjk = 0 nếu giáo viên không dậy nếu giáo viên không dậy vào tiết đó. Giá trị lớn hơn số lớp có thể dùng để biểu diễn các hoạt động khác của giáo viên. Bên cạnh cách biểu diễn này, có thể sử dụng cách biểu diễn trong đó dòng tương ứng với lớp, cột với tiết học và mỗi phần tử chứa số thứ tự giáo viên dậy cho lớp tương ứng vào tiết tương ứng. Ở đây, ta sẽ sử dụng cách biểu diễn bằng ma trận B như đề cập ở trên. Trên hình 2.27 là một phần của thời khoá biểu với cách biểu diễn dùng mà trận B. Để tiện cho việc hình dung, trên hình vẽ thể hiện tên lớp thay vì số thứ tự được dùng trong thuật toán. Các ô trống tương ứng với giờ mà giáo viên không dậy. Các ô "--" tương ứng với giờ mà giáo viên không thể dậy (tương ứng tjk = 0). 71 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm Cần lưu ý rằng, với cách biểu diễn như vậy, việc một giáo viên dậy nhiều hơn một lớp tại một thời điểm là không thể, do vậy ràng buộc (3) luôn được thoả mãn một phần. Giáo viên (số thứ tự) Thứ hai Thứ ba … t1 t2 t3 t4 t5 t1 t2 t3 t4 t5 t1 t2 t3 t4 t5 t1 t2 t3 t4 t5 1 2 3 4 5 … 8A 8A 9B 9B 9A 9A 7A 7A -- 8A 8B 8C 7B 7C -- -- -- -- -- -- -- -- -- -- 6B 6B 7A 7A … -- -- -- -- -- -- -- -- -- -- 7B 7B 7C 7C 9B 9B 7C 7C 6A 6C 6B 6D 6A 16A 7B 7B … … Hình 2.27. Một phần thời khoá biểu Khởi tạo. Trạng thái đầu tiên (thời khoá biểu đầu tiên) được khởi tạo bằng cách xếp lịch cho từng giáo viên một cách ngẫu nhiên sao cho ràng buộc (2) được thoả mãn, tức là tổng số giờ lên lớp cho mỗi giáo viên được đảm bảo. Chuyển động. Để sử dụng các thuật toán như leo đồi, tôi thép hay tìm kiếm tabu, ta cần xác định các chuyển động cho phép sinh ra các trạng thái (thời khoá biểu) láng giềng từ trạng thái hiện thời. Các nghiên cứu trước đây cho thấy có thể sử dụng kết hợp hai loại chuyển động sau. Dạng thứ nhất là dạng chuyển động đơn, được thực hiện bằng cách đổi chỗ hai giờ giảng của cùng một giáo viên, hoặc, nếu một trong hai giờ là giờ trống thì chuyển giờ dậy sang giờ trống đó. Chuyển động này được xác định bằng bộ ba . Dạng thứ hai là dạng chuyển động kép, được tạo thành từ hai chuyển động đơn, sao cho chuyển động đơn thứ hai khắc phục ràng buộc cứng mà chuyển động đơn thứ nhất phá vỡ. Trong trường hợp chuyển động đơn thứ nhất không dẫn tới việc vi phạm ràng buộc cứng thì chuyển động đơn thứ hai sẽ được bỏ qua và chuyển động kép trở thành chuyển động đơn thông thường. Thuật toán tìm kiếm. Cách biểu diễn bài toán và chuyển động như trên có thể sử dụng trong các thuật toán leo đồi, tôi thép, tìm kiếm Tabu. Một số nghiên cứu trước đây cho thấy có thể kết hợp leo đồi ngẫu nhiên và tìm kiếm Tabu để cho ra kết quả tốt. Cụ thể, quá trình tìm kiếm được thực hiện như sau. Bước 1: Khởi tạo như mô tả ở trên. Bước 2: Thuật toán leo đồi ngẫu nhiên được sử dụng để cải thiện lời giải hiện thời. Thuật toán leo đồi ngẫu nhiên được sửa đổi để cho phép đi ngang, tức là chuyển sang các trạng thái tốt bằng trạng thái hiện thời tối đa N lần (N là tham số). Bước 3: Sau khi leo đồi ngẫu nhiên dừng lại do không cải thiện được nữa, thuật toán Tabu sẽ được thực hiện trên lời giải do leo đồi ngẫu nhiên trả về. Bước 4: Lặp lại bước 2 và bước 3 M lần (M là tham số). 72 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm Việc sử dụng leo đồi ngẫu nhiên có hai tác dụng. Thứ nhất, leo đồi ngẫu nhiên tạo ra trạng thái xuất phát cho tìm kiếm Tabu để tiết kiệm thời gian do thời gian thực hiện Tabu lâu hơn leo đồi. Thứ hai, sau khi Tabu không thể cải thiện tiếp lời giải, leo đồi cho phép di chuyển sang vùng lời giải khác để bước thực hiện Tabu tiếp theo có thể khảo sát vùng không gian lời giải khác vòng chạy trước. Cách kết hợp hai thuật toán cho phép tìm ra lời giải chất lượng hơn với độ phức tạp tính toán chập nhận được. Kết quả. Thực nghiệm với các trường phổ thông với trên 30 lớp và trên 50 giáo viên cho thấy các kỹ thuật trình bầy ở trên tìm ra thời khoá biểu có chất lượng tốt hơn nhiều (hàm mục tiêu nhỏ hơn nhiều) so với thời khoá biểu xếp bằng tay và các phương pháp heuristic. Quá trình xếp thời khoá biểu có thể thực hiện trên máy tính cá nhân thông thường trong vòng vài phút tới vài chục phút tuỳ kích thước trường. 2.7. CÂU HỎI VÀ BÀI TẬP CHƯƠNG 1. Giả sử ta có ba can đựng nước với dung tích 3 lít, 8 lít và 12 lít. Ta có thể đổ nước đầy các can hoặc rót toàn bộ nước trong can ra ngoài hoặc sang can khác. Cần tìm cách đổ đầy và rót nước khỏi can để đong được 1 lít nước. Trình bầy dưới bài toán này dưới dạng bài toán tìm kiếm và viết chương trình để tìm lời giải, sử dụng một thuật toán tìm kiếm phù hợp. 2. Bài toán nhà truyền giáo và người ăn thịt người. Có ba nhà truyền giáo và ba người thuộc bộ lạc ăn thịt người ở trên bờ một con sông. Cần chuyển cả sáu người sang bờ bên kia bằng một con thuyền có thể chở tối đa hai người. Yêu cầu đặt ra là không có lúc nào số người ăn thịt trên một bờ sông hoặc trên thuyền lớn hơn số nhà truyền giáo. • Hãy phát biểu bài toán dưới dạng bài toán tìm kiếm trong không gian trạng thái và sử dụng thuật toán tìm kiếm phù hợp để tìm ra lời giải. • Xây dựng chương trình máy tính để thực hiện hiện thuật toán. 3. Các khẳng định sau đúng hay sai, giải thích tại sao: • Để tìm được lời giải, tìm theo chiều sâu không bao giờ mở rộng ít nút hơn tìm kiếm A* với hàm heuristic chấp nhận được. • h(n) = 0 là hàm heuristic chấp nhận được cho bài toán 8 quân hậu. • Tìm theo chiều rộng là đầy đủ kể cả khi giá thành đường đi giữa hai trạng thái có thể bằng không. 4. Giả sử cần tìm chuỗi các link cho phép di chuyển từ trang Web này sang trang Web khác. • Hãy lựa chọn thuật toán tìm kiếm phù hợp cho bài toán này và viết chương trình hiện thức hóa thuật toán. • Việc sử dụng tìm kiếm theo hai hướng cho bài toán này có hiệu quả không? 5. Các khẳng định sau là đúng hay sai, giải thích (chứng minh) câu trả lời: • Tìm theo chiều rộng là trường hợp riêng của tìm theo giá thành thống nhất. • Tìm theo giá thành thống nhất là trường hợp riêng của tìm kiếm A*. 73 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm 6. Cho đồ thị trên hình sau: Hãy xác định đường đi từ START tới GOAL sử dụng các thuật toán tìm kiếm sau: a) Tìm theo chiều rộng. b) Tìm theo chiều sâu. c) Tìm theo giá thành thống nhất. d) Tìm kiếm sâu dần. Thể hiện nút được mở rộng và danh sách các nút trong tập biên tại mỗi vòng lặp của thuật toán. Sử dụng con trỏ ngược để khôi phục lại đường đi khi tìm được nút đích. Hãy cho biết trong trường hợp nào đường đi tìm được là ngắn nhất. 7. Cho đồ thị trên hình sau: trong đó giá thành đường đi giữa hai nút được thể hiện cạnh cung tương ứng, giá trị hàm heuristic h được thể hiện bên cạnh các nút. a) Hãy cho biết hàm h có phải là hàm heuristic chấp nhận được hay không? Tại sao? b) Tìm đường đi từ S tới G sử dụng thuật toán tìm kiếm tham lam với hàm h là hàm heuristic. 74 CuuDuongThanCong.com https://fb.com/tailieudientucntt Giải quyết vấn đề bằng tìm kiếm c) Thay đổi giá trị h tại nút D thành h = 3, sau đó tìm đường đi từ S tới G sử dụng thuật toán A* với h là hàm heuristic. Hãy cho biết đường đi trong trường hợp này có phải là đường đi ngắn nhất không. d) Thay đổi giá trị h tại nút D thành h = 5, sau đó tìm đường đi từ S tới G sử dụng thuật toán A* với h là hàm heuristic. Hãy cho biết đường đi trong trường hợp này có phải là đường đi ngắn nhất không. e) Sử dụng thuật toán A* sâu dần để tìm đường đi từ S tới G với bước nhẩy bằng 2. Hãy cho biết đường đi tìm được có tối ưu không? f) Sử dụng thuật toán A* sâu dần để tìm đường đi từ S tới G với bước nhẩy bằng 3. Hãy cho biết đường đi tìm được có tối ưu không? So sánh với kết quả ở câu e. 8. Viết chương trình giải bài toán n quân hậu với n lớn (từ 1000 trở lên) sử dụng thuật toán leo đồi với trạng thái xuất phát được khởi tạo ngẫu nhiên nhiều lần. Có thể sử dụng không gian trạng thái với đầy đủ cả n quân hậu, mỗi quân nằm trong một cột. Thử nghiệm và so sánh kết quả sử dụng các kiểu chuyển động khác nhau: thay đổi vị trí 1, 2, 3, 4, quân hậu. Trong trường hợp nào thuật toán tìm được lời giải tốt hơn. Trong trường hợp nào thời gian thực hiện thuật toán ngắn hơn. 9. Viết chương trình giải bài toán n quân nhưhậu với n lớn, sử dụng thuật toán tôi thép. Có thể thử nghiệm các kiểu chuyển động tương tự như ở bài tập 8. 75 CuuDuongThanCong.com https://fb.com/tailieudientucntt CHƯƠNG 3: BIỂU DIỄN TRI THỨC VÀ LẬP LUẬ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à lập luậ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ề thế giới xung quanh và lập luận (reasoning) với tri thức đó. 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à lập luậ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à lập luận (bao gồm suy diễn và suy luậ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 lập luậ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 (như cách sinh ra các chuyển động) 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à lập luậ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 lập luận. Các hệ thống có sử dụng tri thức được gọi là hệ dựa trên tri thức. Hệ thống loại này gồm thành phần cơ bản là cơ sở tri thức (tiếng Anh là Knowledge Base, viết tắt là KB). Cơ sở tri thức gồm các câu hay các công thức trên một ngôn ngữ nào đó và chứa các tri thức về thế giới của bài toán. Cùng với cơ sở tri thức, hệ thống còn có khả năng lập luận, gồm cả suy diễn (inference) và suy luận (deduction), cho phép đưa ra các hành động hoặc câu trả lời hợp lý dựa trên tri thức và thông tin quan sát được. Thực chất, suy diễn hay suy luận là cách tạo ra các câu mới từ những câu đã có. Như vậy, một hệ dựa trên tri thức bao gồm cơ sở tri thức và 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: CuuDuongThanCong.com https://fb.com/tailieudientucntt Biểu diễn tri thức và suy diễn logic - Ngôn ngữ phải có khả năng biểu đạt tốt, tức là cho phép biểu diễn mọi tri thức và thông tin 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. 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 hay các công thức 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 logic 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ũng như mọi ngôn ngữ biểu diễn tri thức, logic đượ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 toán họ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. Ví dụ, trong ngôn ngữ toán học, câu a + 1 = 3 là câu đúng cú pháp. Theo ngữ nghĩa của ngôn ngữ toán học, câu này là đúng trong miền bài toán có a = 2 và sai trong những miền bài toán có a ≠ 2. − Cơ chế 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. Ta có thể sử dụng suy diễn để sinh ra các tri thức mới từ tri thức đã có trong cơ sở tri thức. Logic cung cấp một công cụ hình thức để biểu diễn và suy luận tri thức. Các phần tiếp theo sẽ trình bày về hai dạng logic mệnh đề và logic vị từ cũng như cách sử dụng các hệ thống logic này trong biểu diễn tri thức và suy diễn. 3.2. LOGIC MỆNH ĐỀ 3.2.1. Cú pháp 1 Một 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ờ 2 Lưu ý, đây là tiên đề dùng cho suy diễn xác suất, trong trường hợp tổng quát, ta có P(Ω)=1, P(∅)=0, trong đó Ω là toàn bộ không gian lấy mẫu. 77 3 Đây là một ví dụ được sử dụng trong bài báo “Bayesian networks without tears” đăng trên tạp chí AI Magazine CuuDuongThanCong.com https://fb.com/tailieudientucntt Biểu diễn tri thức và suy diễn logic 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 hay câu. a) Các ký hiệu Các ký hiệu được dùng trong logic mệnh đề bao gồm: − Các ký hiệu chân lý hay các hằng logic: True (ký hiệu T) và False (ký hiệu F). − 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,... − Các kết nối logic ∧, ∨, ←, ⇒, ⇔. − Các dấu ngoặc, chẳng hạn “(“ và “)”. b) Các câu hay công thức Các câu hay công thức trong logic mệnh đề được xác định theo các quy tắc sau: Quy tắc 1: Mọi ký hiệu chân lý và ký hiệu mệnh đề là câu. Ví dụ: True, P Các câu chỉ gồm ký hiệu chân lý hoặc ký hiệu mệnh đề như vậy gọi là các câu đơn hay câu nguyên tử. Quy tắc 2: Thêm ngoặc ra ngoài một câu sẽ được một câu. Ví dụ, nếu P là câu thì (P) cũng là câu. Quy tắc 3: 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 là “A hội B” hoặc “A và B”) (A∨B) (đọc là “A tuyển B” hoặc “A hoặc B”) (← A) (đọc là “phủ định A”) (A⇒B) (đọc là “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 là “A và B kéo theo nhau” hay “A và B tương đương nhau”, một số tài liệu sử dụng ký hiệu ≡ cho phép nối logic này) là các câu. Các câu được tạo ra như vậy không phải câu đơn và được gọi là câu phức hợp. Để 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: ←, ∧, ∨, ⇒, ⇔ Nếu P là câu đơn 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 A1∨...∨Am trong đó Ai là các literal sẽ được gọi là câu tuyển (clause). 78 CuuDuongThanCong.com https://fb.com/tailieudientucntt Biểu diễn tri thức và suy diễn logic 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 “Voi là gia cầm” là sai (trong thế giới của chúng ta). 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←True/ A←False) thì ta nói mệnh đề A đúng/sai trong minh họa đó. Ngữ nghĩa của logic cần quy định cách tính giá trị (đúng hoặc sai) cho các câu theo mô hình thế giới của bài toán. Do bất cứ câu nào cũng được tạo ra từ câu đơn và 5 kết nối logic, ta có thể tính giá trị các câu nếu xác định được giá trị câu nguyên tử và giá trị tạo ra bởi từng phép nối. Giá trị của câu đơn được xác định như đã nói ở trên, tức là người sử dụng sẽ quy định giá trị đúng hay sai cho từng mệnh đề. Hằng True luôn đúng, và hằng False luôn sai. Tiếp theo, ta cần xác định giá trị câu được tạo ra bởi kết nối logic. Ý nghĩa các kết nối logic được cho bởi bảng chân lý, trong đó liệt kê giá trị của câu phức cho tất cả tổ hợp giá trị các thành phần của câu. Bảng chân lý cho năm kết nối logic được cho trong bảng sau: Bảng 3.1. Bảng chân lý của các kết nối logic A B ← A A∧B A v B A=>B A<=>B False False True True False True False True True True False False False False False True False True True True True True False True True False False 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. 79 CuuDuongThanCong.com https://fb.com/tailieudientucntt Biểu diễn tri thức và suy diễn logic 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) Luật phủ định kép 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 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 ={G1,.....,Gm} nếu trong bất kỳ minh họa nào mà {G1,.....,Gm} đú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 để sinh ra tri thức mới, tức là sinh ra 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ách 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) 80 CuuDuongThanCong.com https://fb.com/tailieudientucntt