Giáo trình Trí tuệ nhân tạo và hệ chuyên gia (Nghề Lập trình máy tính): Phần 1 - CĐ Nghề

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:103

Thêm vào BST

Báo xấu

50
lượt xem 13
download

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

(NB) Giáo trình Trí tuệ nhân tạo và hệ chuyên gia (Nghề Lập trình máy tính): Phần 1 được biên soạn nhằm cung cấp cho bạn kiến thức về trí tuệ nhân tạo, giải quyết vấn đề, phương pháp tìm kiếm, chứng minh định lý và các khái niệm tri thức. Mời các bạn tham khảo!

Chủ đề:

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

Lưu

Nội dung Text: Giáo trình Trí tuệ nhân tạo và hệ chuyên gia (Nghề Lập trình máy tính): Phần 1 - CĐ Nghề

BỘ LAO ĐỘNG - THƯƠNG BINH VÀ XÃ HỘI TỔNG CỤC DẠY NGHỀ GIÁO TRÌNH Môn học: TRÍ TUỆ NHÂN TẠO VÀ HỆ CHUYÊN GIA Mã số: ITPGR3_07 NGHỀ: LẬP TRÌNH MÁY TÍNH Trình độ :Cao đẳng nghề NĂM 2012
LỜI TỰA Đây là tài liệu được xây dựng theo chương trình của dự án giáo dục kỹ thuật và dạy nghề, để có đươc giáo trình này dự án đã tiến hành theo hai giai đoạn. Giai đoạn 1 : Xây dựng chương trình theo phương pháp DACUM, kết quả của gian đoạn này là bộ khung chương trình gồm 230 trang cấp độ 2 và 170 trang cấp độ 3. Giai đoạn 2 : 29 giáo trình và 29 tài liệu hướng dẫn giáo viên cho nghề lập trình máy tính 2 cấp độ. Để có được khung chương trình chúng tôi đã mời các giáo viên, các chuyên gia đang làm việc trong lĩnh vực công nghệ thông tin cùng xây dựng chương trình. Trong giai đoạn viết giáo trình chúng tôi cũng đã có những sự điều chỉnh để giáo trình có tính thiết thực và phù hợp hơn với sự phát triển của lĩnh vực công nghệ thông tin. Trong quá trình biên soạn, mặc dù đã cố gắng tham khảo nhiều tài liệu và giáo trình khác nhưng tác giả không khỏi tránh được những thiếu sót và hạn chế. Tác giả chân thành mong đợi những nhận xét, đánh giá và góp ý để cuốn giáo trình ngày một hoàn thiện hơn. Tài liệu này được thiết kế theo từng mô đun/ môn học thuộc hệ thống mô đun/môn học của một chương trình, để đào tạo hoàn chỉnh nghề Lập trình máy tính ở cấp trình độ bậc cao và được dùng làm Giáo trình cho học viên trong các khoá đào tạo, cũng có thể được sử dụng cho đào tạo ngắn hạn hoặc cho các công nhân kỹ thuật, các nhà quản lý và người sử dụng nhân lực tham khảo. Đây là tài liệu thử nghiệm sẽ được hoàn chỉnh để trở thành giáo trình chính thức trong hệ thống dạy nghề. 2
MỤC LỤC ĐỀ MỤC TRANG 1. LỜI TỰA.................................................................................................3 2. MỤC LỤC................................................................................................4 3 . GIỚI THIỆU ............................................................................................5 4. BÀI 1 : TỔNG QUAN VỀ TRÍ TUỆ NHÂN TẠO.......................................9 5. BÀI 2 : GIẢI QUYẾT VẤN ĐỀ..................................................................16 6. BÀI 3 : CÁC PHƯƠNG PHÁP TÌM KIẾM................................................46 7. BÀI 4 : CHỨNG MINH ĐỊNH LÝ..............................................................58 8. CÂU HỎI VÀ BÀI TẬP.............................................................................89 9. BÀI 5 : CÁC KHÁI NIỆM TRI THỨC.........................................................90 10. BÀI 6 : XỬ LÝ TRI THỨC.......................................................................116 11. BÀI 7 :TỔNG QUAN VỀ HỆ CHUYÊN GIA VÀ ỨNG DỤNG....................131 12. BÀI 8 :CẤU TRÚC HỆ CHUYÊN GIA.......................................................179 13. BÀI 9 :HỆ CHUYÊN GIA MYCIN..............................................................183 14. BÀI 10:CÁC CÔNG CỤ TẠO LẬP HỆ CHUYÊN GIA...............................190 TÀI LIỆU THAM KHẢO............................................................................194 3
GIỚI THIỆU VỀ MÔN HỌC Vị trí, ý nghĩa, vai trò môn học Trí tuệ nhân tạo đã trở thành một môn học chuyên ngành của sinh viên các ngành Công nghệ Thông tin. Mục đích của lĩnh vực này là phương pháp để tự tìm hiểu bản thân chúng ta và mô phỏng nó bằng nhân tao. Không giống triết học và tâm lý học, hai khoa học liên quan đến trí tuệ, AI cố gắng thiết lập các các yếu tố trí tuệ cũng như tìm biết về chúng. AI có nhiều sản phẩm quan trọng và đáng lưu ý, ngay lúc sản phẩm mới được hình thành. Mặc dù khó dự báo, nhưng máy tính điện tử với độ thông minh nhất định đã ảnh hưởng lớn tới cuộc sống ngày nay và tương lai của văn minh nhân loại. Mục tiêu của môn học Nắm được các khái niệm cơ bản về trí tuệ nhân tạo, biết biểu diễn các vấn đề, sử dụng các kỹ thuật chiến lược giải quyết vấn đề, biết biểu diễn các tri thức dưới 5 dạng cơ bản, biết sử dụng các phương pháp tìm kiếm cơ bản. Nắm được các kỹ thuật của mô tơ suy diễn, nắm được cấu trúc hệ chuyên gia, thu thập tri thức từ các chuyên gia, xây dựng hệ chuyên gia cỡ nhỏ khoảng vài chục luật và sự kiện, biết tích hợp ứng dụng hệ chuyên gia trong các ứng dụng khác của hệ thống thông tin v à đánh giá khả năng của hệ chuyên gia. Mục tiêu thực hiện của mô đun/môn học Nắm được các khái niệm cơ bản về trí tuệ nhân tạo và lịch sử phát triển của TTNT trong lĩnh vực CNTT Biểu diễn các vấn đề cần giải bằng các phương pháp khác nhau dưới dạng máy tính có thể giải quyết được: Mô hình toán học, không gian trạng thái Sử dụng các kỹ thuật chiến lược giải quyết vấn đề đòi hỏi trí tuệ: Biểu diễn các tri thức dưới 5 dạng cơ bản: Logíc, frame, OAV, luật sản xuất, mạng ngữ nghĩa Sử dụng các phương pháp tìm kiếm cơ bản: vét cạn, theo chiều sâu, rộng, heuristic để giải quyết bài toán Nắm được các kỹ thuật của mô tơ suy diễn tiến, lùi để suy luận trên cơ sở tri thức. Tính dư thừa, tính mâu thuẫn Nắm được cấu trúc hệ chuyên gia : 5 thành phần chính Thu thập tri thức từ các chuyên gia Xây dựng hệ chuyên gia cỡ nhỏ khoảng vàI chục luật và sự kiện cho một ứng dụng cụ thể Sử dụng các công cụ tạo lập hệ chuyên gia Tích hợp ứng dụng hệ chuyên gia trong các ứng dụng khác của hệ thống thông tin Đánh giá khả năng của hệ chuyên gia: Thời gian, chất lượng Nội dung chính của môn học :  Trí tuệ nhân tạo và lịch sử phát triển  Các tiền đề phát triển TTNT  TTNT trong công nghệ thông tin  Các thành phần cơ bản TTNT. Các ứng dụng TTNT 4
 Giải quyết vấn đề, các phương pháp biểu diễn vấn đề và chiến lược giải quyết vấn đề  Chứng minh định lý  Cơ sở tri thức, các phương pháp biểu diễn tri thức  Các phương pháp tìm kiếm  Các kỹ thuật suy diễn : Tiến lùi  Các lĩnh vực TTNT tiên tiến : Xử lý ngôn ngữ tự nhiên, Xử lý ảnh, học máy, mạng nơ ron  Tổng quan về hệ chuyên gía và ứng dụng  Cấu trúc hệ chuyên gia  Hệ chuyên gia MYCIN  Các công cụ tạo lập hệ chuyên gia  Thu thâp cơ sở tri thức  Xử lý tri thức  Hệ giảI thích  Hệ giao diện Kỹ năng thực thành:  Phân tích một bàI toán TTNT  Phát biểu bàI toán dưới dạng hình thức hoá  áp dụng hiệu quả chiến lược giảI quyết vấn đề cho bàI toán thích hợp  Biểu diễn bàI toán sao cho dễ hiểu và xử lý được  Phân tích một hệ chuyên gia ứng dụng  Kỹ năng thu thập tri thức  Kỹ năng sử dụng phần mềm ngôn ngữ logic hình thức  Biểu diễn bàI toán sao cho dễ hiểu và xử lý được Thái độ học viên:  Rèn kuyện kỹ năng phân tích, tổng hợp, cẩn thận. Đánh giá thông qua kiểm tra trắc nghiệm  Kiểm tra trắc nghiệm được thực hiện trên máy tính và chấm cho kết quả ngay.  Xây dựng ngân hàng các câu hỏi. Học viên sẽ nhận được ngẫu nhiên Các câu hỏi trắc nghiệm 100 câu (mỗi chức năng 20 câu), Thời gian kiểm tra hạn chế trong 60 phút. Học viên có thể chưa qua lớp học máy tính nhưng tối thiểu biết gõ bàn phím và di chuột . Thang điểm: 0-49 : Không đạt 50-69 : Đạt trung bình 70-85 : Đạt khá 86-100 : Đạt Giỏi 5
Sơ đồ quan hệ theo trình tự học nghề Học kỳ V Học kỳ VI Tiếng Anh chuyên ngành Lập trình nâng cao hướng .NET Phát triển phần mềm ứng dụng Cơ sở kỹ thuật điện - điện tử Phân tích và thiết kế giải thuật Lý thuyết về ngôn ngữ lập Thiết kế mạng và quản trị trình mạng Cấp độ 3 Kho dữ liệu Bảo trì máy tính Mô hình client-server trên SQL server Cơ sở trí tuệ nhân tạo và Phân tích hệ chuyên gia hướng đối tượng UML Tích hợp các ứng dụng trên mạng Lập trình logic An toàn thông tin Cơ sở dữ liệu Chuyên đề tự chọn nâng cao 6
BÀI 1 TỔNG QUAN VỀ TRÍ TUỆ NHÂN TẠO MÃ BÀI ITPRG3_07.1 Mục tiêu thực hiện Học xong bài này học viên sẽ có khả năng:  Hiểu được các kháI niệm cơ bản về TTNT  Nắm được cách giảI quyết một bàI toán đòi hỏi tri thức Nội dung 1.1 Lịch sử hình thành và phát triển TTNT 1.2. Các tiền đề phát triển TTNT 1.3. Trí tuệ nhân tạo trong CNTT 1.4. Các ứng dụng của TTNT 1.5 Các lĩnh vực nghiên cứu cơ bản 1.1 Lịch sử hình thành và phát triển TTNT Những năm gần đây, khá nhiều sách, báo, công trình nghiên cứu khoa học đề cập đến các kỹ thuật tính toán, nguời ta hay nhắc đến nhiều thuật ngữ như: máy tính thông minh, máy tính thế hệ V, hệ chuyên gia, mạng ngữ nghĩa… các ngôn ngữ lập trình như Prolog, LISP mở đường cho việc áp dụng hàng loạt các hệ thống chương trình có khả năng “thông minh”. Trước đây mỗi khi nói đến trí tuệ nhân tạo (TTNT) người ta thường quan tâm đến việc tạo lập các máy tính có khả năng “suy nghĩ”, thậm chí trong một số phạm vi hẹp nào đó, có thể cạnh tranh hoặc vượt quá khả năng của bộ não con người. Những hy vọng này trong một thời gian dài đã ảnh hưởng rất nhiều đến các nghiên cứu trong phòng thí nghiệm. Mặc dù những mô hình tương tự các máy tính thông minh đã được đưa ra hàng nhiều năm trước, nhưng chỉ từ khi Alan Turing công bố những kết quả nghiên cứu quan trọng đầu tiên, người ta mới bắt đầu thực sự nghiên cứu đến các vấn đề TTNT một cách nghiêm túc. Phát triển của Turing cho rằng chương trình có thể được lưu trữ trong bộ nhớ để sau đó được thực hiện trên cơ sở các phép toán cơ bản thao tác với các bít 0, 1. Điều này đã tạo nên những nền tản của máy tính hiện đại. Việc lưu trữ chương trình trong máy cho phép thay đổi chức năng của nó một cách nhanh chóng và dễ dàng thông qua việc nạp một chương trình mới vào bộ nhớ. Theo một nghĩa nào đó, khả năng này làm cho máy tính có khả năng học và suy nghĩ. Đó cũng chính là một trong những biểu hiện quan trọng đầu tiên của những máy tính được trang bị TTNT. Năm 1956, chương trình dẫn xuất kết luận trong hệ hình thức đã được công bố. Tiếp theo đó, năm 1959, chương trình chứng minh các định lý hình học phẳng và chương trình giải quyết bài toán vạn năng (GPS – General Problem Solving) đã được đưa ra. Tuy vậy, chỉ cho đến khoảng năm 1960 khi McCathy ở MIT (Massachussets Institute of technology) đưa ra ngôn ngữ lập trình đầu tiên dùng cho trí tuệ nhân tạo LISP (list Processing), các nghiên cứu về TTNT mới phát triển mạnh mẽ. Thuật ngữ TTNT do Marvin Minsky một chuyên gia nổi tiếng cũng ở MIT đưa ra năm 1961 trong bài báo “Steps Forwards To Artificical Intelligence”, Những năm 60 có thể xem là một mốc quan trọng trong quá trình xây dựng các máy có khả năng suy nghĩ. Các chương trình chơi cờ và các định lý chứng minh định lý toán học đầu tiên cũng được công bố trong khoảng thời gian này Những bế tắt, hạn chế thành công của cac công trình nghiên cứu TTNT trong những năm 60 chính là do giới hạn khả năng của các thiết bị, bộ nhớ và đặt biệt là yếu tố thời gian thực hiện. Chính những yếu tố này không cho phép tổng quát hóa những thành công bước 7
đầu đạt được trong các hệ chương trình TTNT đã xây dựng. Tuy rằng vào giữa những năm 70, bộ nhớ máy tính và thời gian tính toán đã được nâng cao đáng kể về chất, song những cách tiếp cận khác nhau đến trí tuệ nhân tạo vẫn chưa mang tới những thành công thực sự do bùng nổ tổ hợp trong quá trình tìm kiếm lời giải cho các bài toán đặt ra. Cuối những năm 70, một nghiên cứu cơ bản trong các lĩnh vực như xử lý ngôn ngữ tự nhiên, biểu diễn tri thức, lý thuyết giải quyết vấn đề đã đem lại diện mạo mới cho TTNT. Thị trường tin học đã bắt đầu đón nhận những sản phẩm TTNT ứng dụng đầu tiên mang tính thương mại. Đó là các hệ chuyên gia được áp dụng trong các lĩnh vực khác nhau. Hệ chuyên gia là các phần mềm máy tính, chứa các thông tin và tri thức về một lĩnh vực nào đó, có khả năng giải quyết những yêu cầu của người dùng ở một mức độ nào đó với trình độ như một chuyên gia có kinh nghiệm lâu năm. Một trong những hệ chuyên gia đầu tiên thành công trong thực tế là hệ MYCIN, được thiết và cài đặt tại trường Đại học tổng hợp Stanford. Một sự kiện quan trọng trong sự phát triển của khoa học TTNT là sự ra đời của ngôn ngữ Prolog, do Alain Calmerauer đưa ra năm 1972. Năm 1981, dự án của Nhật xây dựng các máy tính thế hệ thứ V lấy ngôn ngữ Prolog như là ngôn ngữ cơ sở đã làm thay đổi khá nhiều tình hình phát triển trí tuệ nhân tạo ở Mỹ cũng như Châu Âu. Giai đoạn 1981 trở đi người ta cảm nhận khá rõ nét rằng các chuyên gia về TTNT đang dần chuyển các kết quả trong phòng thí nghiệm sang cài đặt các ứng dụng cụ thể. Có thể nói đây cũng là giai đoạn cạnh tranh ráo riết của các công ty, các viện nghiên cứu hàng đầu nhằm đưa ra thị trường các sản phẩm phần mềm ứng dụng kỷ thuật TTNT. Cuối những năm 80, đầu những năm 90 thị trường các sản phẩm dân dụng đã có nhiều sản phẩm ở trình độ cao như máy giặt, máy ảnh… sử dụng TTNT. Các hệ thống nhận dạng và sử lý hình ảnh, tiếng nói đang ngày càng thúc đẩy sự phát triển kỹ thuật mạng Neuron. Sự xích lại của hai cách tiếp cận: Tiếp cận mở trong lập luận xấp xỉ và kỹ thuật mạng Neuron đã và đang gây được sự quan tâm đặt biệt của các chuyên gia tin học. Bên cạnh sự xuất hiện của các hệ chuyên gia, các ứng dụng công nghiệp và quản lý xã hội, quản lý kinh tế cũng đòi hỏi sự ra đời của các hệ thống xử lý tri thức – dữ liệu tích hợp. Thế giới đang chuyển mình trong những nghiên cứu về TTNT. Tuy vậy, câu hỏi liệu kỹ thuật TTNT có tạo nên những bước nhảy vọt trong công nghệ tin học, đặc biệt là trong công nghệ máy tính như người ta đã mong đợi hay không vẫn chưa có lời giải đáp thỏa đáng. 1.2. Các tiền đề phát triển TTNT Phương pháp giải quyết vấn đề hình thành trong thập kỉ đầu nghiên cứu AI là liên kết các bước lập luận cơ bản để tìm cách hoàn thiện. Chương trình DENDRAL (Buchanan, 1969) là một ví dụ về cách tiếp cận phương pháp này. Với bài học này, Feigebaum và các thành viên khác tại Stanford bắt đầu lập dự án cho chương trình Heuristic, đầu tư mở rộng vào các phương pháp mới của hệ chuyên gia nhằm áp dụng vào các lĩnh vực khác nhau. Những nỗ lực chính là chuẩn đoán y học. Feigenbaum, Buchanan và Edward Shortlife đã phát triển hệ chuyên gia MYCIN để chẩn đoán bệnh nhiễm trùng máu. Với khoảng 450 luật, hệ chuyên gia MYCIN có thể thực hiện tốt hơn nhiều bác sĩ mới. Có hai sự khác biệt cơ bản của hệ MYCIN với hệ chuyên gia DENDRAL. Thứ nhất: không giống như các luật DENDRAL, không một mẫu chung nào tồn tại mà có thể suy luận từ các luật của hệ MYCIN. Các luật phải có câu chất vấn của chuyên gia- người có nhiệm vụ tìm chúng từ kinh nghiệm. Thứ hai: các luật phản ánh mối liên quan không chắc chắn với kiến thức y học. MYCIN kết hợp với hệ vi phân của biến số được coi là các nhân tố phù hợp (ở mọi lúc) với phương pháp mà các bác sĩ tiếp cận với các triệu chứng trong quá trình chuẩn đoán. Cách tiếp cận khác để chuẩn đoán y học cũng được nghiên cứu. Tại trường đại học Rutger, những máy tính trong ngành sinh hoá của Sual Amarel cố gắng chuẩn đoán bệnh tật dựa trên kiến thức được mô tả của máy phân tích quá trình gây bệnh. Trong khi đó, một số nhóm lớn hơn tại MIT và trung tâm y tế của Anh tiếp tục phương pháp chuẩn đoán và điều trị dựa trên học thuyết có tính khả thi và thực tế. Mục đích của họ là xây dựng các hệ thống có 8
thể đưa ra các phương pháp chẩn đoán y học. Về y học, phương pháp Stanford sử dụng các qui luật do các bác sĩ cung cấp ngay từ đầu đã được chứng minh là phổ biến hơn. Một hệ chuyên gia khác: PROSPECTOR (Duda 1979) được công bố để tư vấn trong lĩnh vực thăm dò quặng. Một trong những yếu tố có tính tiền đề cho phát triển AI là ngôn ngữ của trí tuệ nhân tao. Một vài ngôn ngữ dựa vào logic như PROLOG phổ biến ở châu Âu, PLANNER ở Mĩ. Các ngôn ngữ khác, theo sau các ý tưởng của Minsky (1975) chấp nhận phương pháp tiếp cận cấu trúc, thu thập các chứng cứ về đối tượng và các loại sự kiện. 1.3. Trí tuệ nhân tạo trong CNTT Khoa học trí tuệ nhân tạo có nhiệm vụ nghiên cứu các kỹ thuật làm cho máy tính có thể suy nghĩ một cách thông minh. Khoa học trí tuệ nhân tạo còn mô phỏng quá trình suy nghĩ của con người khi đưa ra những quyết định, lời giải nhờ tìm kiếm trong không gian bài toán hay phân rã bài toán thành các bào toán con. Do vậy, chia nhỏ quá trình suy nghĩ này thành những bước cơ bản. Trên cơ sở đó thiết kế những chương trình máy tính để giải quyết bài toán dựa vào chính các bước cơ bản trong quá trình tìm kiếm. Trí tuệ nhận tạo tạo nên một cách tiếp cận đơn giản và có cấu trúc để xây dựng các chương trình ra quyết định phức hợp đòi hỏi phải dựa trên những tri thức nhất định. Trí tuệ nhân tạo tạo cho máy tính một khả năng suy nghĩ. Nhờ đơn giản hoá phương cách kết hợp các chương trình với nhau, trí tuệ nhân tạo có thể mô phỏng quá trình học của con người, trên cơ sở đó thu nạp được những thông tin mới phục vụ cho quá trình suy diễn sau đó. Các kỹ thuật trí tuệ nhân tạo cho phép tạo lập một chương trình trong đó mỗi phần của nó thể hiện một thao tác độc lập trong quá trình đi tới lời giải cuối cùng cho bài toán. Có thể coi mỗi phần của chương trình như một mẩu thông tin trong bộ não con người. Nếu mẩu thông tin này thay đổi thì bộ não có thể chỉnh lý quá trình suy nghĩ để phù hợp với tập các sự kiện mới mà không cần phải xét lại toàn bộ những gì đã có. Thay vào đó, chỉ cần xét một số các phần có liên quan. Sự ra đời và phát triển của trí tuệ nhân tạo tạo nên những bước nhảy vọt về chất trong kỹ thuật và kỹ nghệ xử lý thông tin. Trí tuệ nhân tạo chính là cơ sở của công nghệ xử lý thông tin mới, độc lập với công nghệ xử lý thông tin truyền thống dựa vào văn bản và giấy tờ. So sánh kỹ thuật lập trình truyền thống và kỹ thuật xử lý ký hiệu trong trí tuệ nhân tạo: 9
Lập trình truyền thống Lập trình xử lý ký hiệu - Xử lý dữ Xử lý dữ liệu định tính (các ký hiệu tượng liệu trưng) và xử lý tri thức. Tri thức được cấu trúc trong bộ nhớ làm - Dữ liệu việc theo các ký hiệu. trong bộ nhớ được đánh địa chỉ số. Xử lý theo các thuật giải heuristic và theo - Xử lý theo các cơ chế lập luận. các thuật toán Định hướng xử lý các đại lượng định tính, - Định hướng các ký hiệu tượng trưng và danh sách. xử lý các đại lượng định lượng số. Xử lý theo chế độ tương tác cao (như hội thoại theo ngôn ngữ tự nhiên … ) - Xử lý tuần Có thể giải thích hành vi hệ thống trong quá tự hoặc theo mẻ trình thực hiện. - Không giải thích trong quá trình thực hiện Bảng 1. So sánh kỹ thuật lập trình truyền thống và xử lý ký hiệu trong trí tuệ nhân tạo 1.4. Các ứng dụng của TTNT Các ứng dụng của trí tuệ nhân tạo là rất đa dạng: các hệ điều khiển tự động các quá trình sản xuất công nghiệp, các robot làm việc trong các môi trường đặc biệt, các hệ chuyên gia trong các lĩnh vực, các hệ dịch tự động, các hệ nhận dạng … 1.4.1 Kỹ thuật robot Cuối những năm 1960, kỹ thuật và công nghệ chế tạo người máy có những bước phát triển mới, trên cơ sở kết hợp những thành tựu nghiên cứu của những lý thuyết trí tuệ nhân tạo và điều khiển. Các nghiên cứu và ứng dụng các phương pháp nhận dạng, hình ảnh, tiếng nói là những tiền đề quan trọng tiến tới chế tạo những robot thông minh. Người máy thế hệ thứ ba có thể đảm nhận nhiều nhiệm vụ khá phức tạp, đòi hỏi khả năng trí tuệ rất cao, các kỹ thuật trí tuệ nhân tạo cho phép điều khiển chuyển động người máy dựa trên các tri thức phụ thuộc không gian và thời gian. 1.4.2 Các chương trình trò chơi Các chương trình trò chơi theo một nghĩa nào đó là xuất phát điểm của các nghiên cứu và thử nghiệm lập trình heuristic, trong đó điểm mấu chốt là xác định các hàm giá. Có rất nhiều loại chương trình trò chơi: chương trình chơi cờ, chơi bài, trò chơi Go, Nimo … 1.4.3 Xử lý ngôn ngữ tự nhiên Việc sử dụng ngôn ngữ tự nhiên ngày càng trở nên phổ biến và cần thiết. Phạm vi xử lý ngôn ngữ tự nhiên bao gồm: - Giao tiếp bằng ngôn ngữ tự nhiên với các máy tự động. - Các hệ thống thu thập tin tự động - Robot có khả năng nghe, hiểu - Giao tiếp với các hệ chuyên gia - Hiểu văn bản - Hiểu tiếng nói liên tục … 10
1.4.4 Các hệ thống xử lý tri thức và dữ liệu tích hợp Xây dựng các hệ CSDL cỡ lớn và các hệ chuyên gia dựa trên tri thức dựa trên một số cách tiếp cận hợp lý cho phép xử lý cùng một lúc cả dữ liệu và tri thức, như: cách tiếp cận biểu diễn hướng đối tượng, CSDL suy diễn, Biểu diễn luật-đối tượng … Các hệ hỗ trợ quyết định dựa trên tri thức được xem như kết quả của sự kết hợp tri thức - dữ liệu cùng với việc sử dụng các mô hình toán học. 1.4.5 Các giao diện người-máy thông minh. 1.4.6 Các thiết bị điện tử thông minh sử dụng logic mờ 1.5 Các lĩnh vực nghiên cứu cơ bản 1.5.1 Lý thuyết giải quyết vấn đề và các kỹ thuật suy diễn thông minh. Những phương pháp giải quyết vấn đề cơ bản là:  Phương pháp biểu diễn bài toán trong không gian và chiến lược tìm kiếm trên đồ thị trạng thái  Phương pháp quy bài toán về các bài toán con và chiến lược tìm kiếm trên đồ thị và/hoặc.  Phương pháp GPS  Phương pháp hình thức sử dụng cách tiếp cận logic 1.5.2 Lý thuyết tìm kiếm heuristic Lập trình heuristic là một hướng tiếp cận quan trọng trong việc xây dựng các hệ thống trí tuệ nhân tạo. Lý thuyết tìm kiếm heuristic bao gồm các phương pháp và các kỹ thuật tìm kiếm, sử dụng các tri thức đặc biệt nảy sinh từ bản thân bài toán cần giải để rút ngắn quá trình giải, nhanh chóng đi đến kết quả mong muốn. Kỹ thuật cơ bản dựa trên các giao thức heuristic hay được sử dụng trong thực tiễn là các hàm đánh giá. 1.5.3 Lý thuyết biểu diễn tri thức và kỹ nghệ xử lý tri thức Hai thành phần cơ bản trong mọi hệ thống trí tuệ nhân tạo là các phương pháp biểu diễn tri thức và các phương pháp suy diễn, các phương pháp tìm kiếm tương ứng. Các kỹ nghệ xử lý tri thức đang là lĩnh vực đang được tập trung nghiên cứu của các chuyên gia trí tuệ nhân tạo.Sự ra đời của các hệ chuyên gia là kết quả của sự kết hợp những tư tưởng cơ bản trong biểu diễn tri thức và các phương pháp suy diễn. Những năm gần đây, người ta thường quan tâm đến việc xử lý tri thức và dữ liệu tích hợp, tạo tiền đề cho những áp dụng thực tế của các hệ trợ giúp quyết định. 1.5.4 Lý thuyết nhận dạng Vấn đề nhận dạng thông tin hình ảnh, tiếng nói vẫn còn là một thách thức đối với các chuyên gia trí tuệ nhân tạo. Nhờ công cụ hệ chuyên gia, người ta đã xây dựng được một số hệ thống trí tuệ nhân tạo hiểu được hình ảnh ba chiều, hiểu được tiếng nói liên tục dựa trên tri thức về ảnh, ngữ cảnh và ngữ điệu giọng nói. Cơ sở toán học của lý thuyết nhận dạng được xây dựng và phát triển theo các cách tiếp cận sau:  Lý thuyết thống kê về nhận dạng  Lý thuyết cấu trúc về nhận dạng  Lý thuyết đại số về nhận dạng  Lý thuyết heuristic về nhận dạng. 1.5.5 Các ngôn ngữ trí tuệ nhân tạo 11
Sự phát triển của các lĩnh vực trí tuệ nhân tạo đòi hỏi phải thiết kế các ngôn ngữ lập trình chuyên dụng, chứa đựng những công cụ xử lý ký hiệu và danh sách hữu hiệu, hướng tới giải quyết các bài toán sáng tạo đặt ra trong thực tiễn. Hai ngôn ngữ lập trình được đề cập tới nhiều nhất là: LISP và PROLOG. Tuy nhiên sử dụng các ngôn ngữ này đòi hỏi kinh phí quá lớn và bị hạn chế về khả năng phát triển hệ thống. Ngôn ngữ CLIPS ra đời đã khắc phục những nhược điểm trên và hướng tới biểu diễn hướng đối tượng và xử lý các luật suy diễn. 12
A. BÀI TẬP VÀ CÂU HỎI 1. Chúng ta đưa ra định nghĩa của AI theo các khía cạnh, con người, ý tưởng và hành động. Nhiều khía cạnh khác có giá trị đáng xét đến như sự khích lệ của chúng ta về kết quả lí thuyết hoặc ứng dụng. Một khía cạnh nữa có thể nhận ra là các máy tính của chúng ta có thông minh hay không. Đã có 8 định nghĩa tiêu biểu trong Bảng 1.1 theo bốn khía cạnh chúng ta vừa đề cập và bạn cảm thấy các định nghĩa nào sau đây là hữu ích? AI là: a. “một tập hợp các thuật toán dễ tính toán, thích hợp với tính gần đúng cho các bài toán đặc biệt khó” (Partridge, 1991) b. “có sự tham gia trong thiết kế hệ thống kí hiệu vật lí sao cho có thể vượt qua trắc nghiệm của Turning.” c. “lĩnh vực của khoa học máy tính nhằm nghiên cứu về các máy có thể hành động thông minh” (Jackson, 1986) d. “một lĩnh vực nghiên cứu quanh các kĩ thuật tính toán, cho phép thực hiện các công việc đòi hỏi sự thông minh thực sự khi có con người tham gia” (Tanimoto, 1990) e. “một sự đầu tư rất lớn trí tuệ của tự nhiên và các nguyên lí, các máy móc với yêu cầu sự hiểu biết hoặc tái tạo nó” (Sharples, 1989) f. “tiềm năng của máy tính làm được mọi thứ, xem nó là thông minh.” (Rowe, 1988) 2. Nghiên cứu tài liệu AI để tìm ra các công việc nào dưới đây có thể giải quyết được bằng máy tính: a. Trò chơi bóng bàn. b. Lái xe. c. Khám phá và chứng minh các lý thuyết toán học mới. d. Viết một truyện cười. e. Đưa ra một lời khuyên khá hợp lý trong phạm vi liên quan đến luật pháp. f. Dịch tiếng Anh sang tiếng Việt theo thời gian thực. 3. Bạn có cho rằng: “những chiếc máy tính là không thông minh - chúng chỉ có thể làm được những gì mà lập trình viên bảo chúng” là câu mà phần trước thì đúng và ý sau thì sai? 13
BÀI 2 GIẢI QUYẾT VẤN ĐỀ MÃ BÀI ITPRG3_07.2 Mục tiêu thực hiện Học xong bài này học viên sẽ có khả năng:  Phân tích một bàI toán thực tiễn thành bàI toán TTNT  GiảI quyết lớp bàI toán bằng các chiến lược giảI quyết vấn đề Nội dung 2.1 Giải quyết vấn đề là gì? 2.2 Con người giảI quyết vấn đề như thế nào? 2.3. Các phương pháp biểu diễn vấn đề 2.4 Các chiến lược giải quyết vấn 2.5 Các ví dụ giảI quyết vấn đề cho các bàI toán cụ thể 2.1 Giải quyết vấn đề là gì? Chúng ta đã khảo sát nhiều bài toán được giải quyết theo tiếp cận xem bài toán TTNT là sự kết hợp của biểu diễn bài toán và giải thuật tìm kiếm một lời giải trong không gian các trạng thái của bài toán. Tiếp cận giải quyết vấn đề này còn được gọi là phương pháp giải quyết vấn đề yếu (weak problem solving methods), vì các phương pháp này chủ yếu là muốn cài đặt một chiến lược tổng quát để giải quyết cho mọi bài toán, cụ thể là các phương pháp duyệt đồ thị không gian tìm kiếm tổng quát cho mọi bài toán. Các phương pháp này chỉ có thể phân tích hình thức cú pháp của các trạng thái để giải quyết bài toán, chứ chúng không thể sử dụng tri thức lý thuyết hay thực nghiệm về một vấn đề nào đó mà con người đang có. Nhưng thật không may là trong thực tế, không có bất kỳ một chiến lược hay kinh nghiệm (heuristic) nào có thể áp dụng một cách thành công cho tất cả các bài toán. Mà thông thường khi giải quyết một vấn đề trong một lĩnh vực nào đó, thì chúng ta sử dụng rất nhiều tri thức về lĩnh vực đó. Chẳng hạn như các bác sĩ có thể chẩn đoán bệnh cho ta vì bên cạnh khả năng giải quyết vấn đề tổng quát, họ còn có một kiến thức rất rộng về y học. Các kiến trúc sư có thể thiết kế nhà vì họ biết nhiều về kiến trúc. Những phương pháp giải quyết vấn đề thực tế này được gọi là phương pháp giải quyết vấn đề mạnh (strong problem solving methods), vì chúng sử dụng các tri thức tường minh về lĩnh vực của vấn đề. 2.2 Con người giảI quyết vấn đề như thế nào? Trong cuộc sống, sở dĩ các chuyên gia có thể giải quyết vấn đề ở một mức độ cao vì họ có rất nhiều tri thức về lĩnh vực họ hoạt động. Thực tế hiển nhiên và đơn giản này chính là cơ sở nền tảng cho việc thiết kế các máy giải quyết vấn đề dựa trên tri thức mà ta thường gọi là hệ chuyên gia. Một hệ chuyên gia sử dụng tri thức của một lĩnh vực cụ thể để cung cấp việc giải quyết vấn đề với “chất lượng chuyên gia” trong lĩnh vực đó. Thông thường, các nhà thiết kế HCG thu thập tri thức này, bao gồm lý thuyết đến cả các kinh nghiệm, kỹ xảo, phương pháp làm tắt, chiến lược heuristic đã tích lũy được của các chuyên gia con người qua quá trình làm việc của họ trong một lĩnh vực chuyên môn. Từ tri thức này, người ta cố gắng cài đặt chúng vào hệ thống để hệ thống có thể mô phỏng theo cách thức các chuyên gia làm việc. Tuy nhiên, không giống với con người, các chương trình hiện tại không tự học lấy kinh nghiệm: mà tri thức phải được lấy từ con người và mã hóa thành ngôn ngữ hình thức. Đây là nhiệm vụ chính mà các nhà thiết kế HCG phải đương đầu. Do bản chất heuristic và tri thức chuyên sâu của việc giải quyết vấn đề cấp độ chuyên gia, các hệ chuyên gia nói chung: 14
1. Cung cấp sự kiểm tra đối với các quá trình suy luận của chúng, bằng cách hiển thị các bước trung gian và bằng cách trả lời câu hỏi về quá trình giải. 2. Cho phép sửa đổi dễ dàng, cả khi thêm và xóa các kỹ năng giải quyết vấn đề vào cơ sở tri thức (knowledge based). 3. Suy luận một cách heuristic, sử dụng tri thức (thường là không hoàn hảo) để tìm lời giải hữu ích cho vấn đề. Người ta đã xây dựng các hệ chuyên gia để giải quyết hàng loạt những vấn đề trong các lĩnh vực như y học, toán học, công nghệ, hóa học, địa chất, khoa học máy tính, kinh doanh, luật pháp, quốc phòng và giáo dục. Các chương trình này đã giải quyết một lớp rộng các loại vấn đề như: 1. Diễn giải (interpretation) – hình thành những kết luận hay mô tả cấp cao từ những tập hợp dữ liệu thô. 2. Dự đoán (prediction) – tiên đoán những hậu quả có thể xảy ra khi cho trước một tình huống. 3. Chẩn đoán (diagnosis) – xác định nguyên nhân của những sự cố trong các tình huống phức tạp dựa trên các triệu chứng có thể quan sát được. 4. Thiết kế (design) – tìm ra cấu hình cho các thành phần hệ thống, đáp ứng được các mục tiêu trong khi vẫn thỏa mãn một tập hợp các ràng buộc về thiết kế. 5. Lập kế hoạch (planning) – tìm ra một chuỗi các hành động để đạt được một tập hợp các mục tiêu, khi được cho trước các điều kiện khởi đầu và những ràng buộc trong thời gian chạy (run-time). 6. Theo dõi (monitoring) – so sánh hành vi quan sát được của hệ thống với hành vi mong đợi. 7. Bắt lỗi và sửa chữa (debuging and repair) – chỉ định và cài đặt những phương pháp chữa trị cho các trục trặc. 8. Hướng dẫn (instruction) – phát hiện và sửa chữa những thiếu sót trong quan niệm của học viên về một chủ đề lĩnh vực nào đó. 9. Điều khiển (control) – chỉ đạo hành vi của một môi trường phức tạp. 2.3. Các phương pháp biểu diễn vấn đề 2.3.1Các chiến lược tìm kiếm Công việc chủ yếu của việc tìm kiếm đã chuyển sang việc tìm kiếm một chiến lược tìm kiếm đúng đắn đối với một vấn đề. Trong sự nghiên cứu của chúng ta về lĩnh vực này, chúng ta sẽ đánh giá các chiến lược bằng các thuật ngữ của bốn tiêu chuẩn sau:  Tính hoàn thành: chiến lược có bảo đảm tìm thấy một giải pháp khi có một vấn đề  Độ phức tạp thời gian: chiến lược mất bao lâu để tìm ra một giải pháp?  Độ phức tạp không gian (dung lượng bộ nhớ): chiến lược đó cần bao nhiêu dung lượng bộ nhớ cần thiết để thực hiện việc tìm kiếm.  Tính tối ưu: chiến lựơc có tìm được giải pháp có chất lượng cao nhất khi có một số các giải pháp khác nhau? Phần này sẽ nói đến 6 chiến lược tìm kiếm mà được sử dụng dưới tiêu đề tìm kiếm không đủ thông tin (uninformed search). Thuật ngữ này có nghĩa là không có các thông tin về số các bước hay chi phi đường đi từ trạng thái hiện tại cho tới đích – tất cả những gì chúng có thể làm là phân biệt một trạng thái đích với một trạng thái không phải là trạng thái đích. Tìm kiếm không có thông tin đầy đủ đôi khi còn được gọi là tìm kiếm mù (blind search). 15
Tìm kiếm theo chiều rộng Một chiến lược tìm kiếm đơn giản là tìm kiếm theo chiều rộng. Trong chiến lược này, nút gốc được mở rộng trước tiên, sau đó đến lượt tất cả các nút mà được sinh ra bởi nút gốc được mở rộng, và sau đó tiếp đến những nút kế tiếp của chúng và cứ như vậy. Nói một cách tổng quát, tất cả các nút ở độ sâu d trên cây tìm kiếm được mở rộng trước các nút ở độ sâu d+1. Tìm kiếm theo chiều rộng có thể được thực hiện bằng cách gọi giải thuật general-search với một hàm hàng đợi mà đưa các trạng thái mới được sinh ra vào cuối của hàng đợi, đứng sau tất cả các trạng thái mà đã được sinh ra trước nó: Function Tìm- kiếm- rộng(problem) Returns một giải pháp hoặc thất bại Return General-search (problem, xếp vào cuối hàng) Bảng 2. Tìm kiếm theo chiều rộng Bảng 3. Tìm kiếm trên một cây nhị phân đơn giản Tìm kiếm theo chiều rộng là một chiến lược rất có phương pháp (có hệ thống) bởi vì nó xem xét tất cả các đường đi có độ dài bằng 1 trước, sau đó đến tất cả những đường đi có độ dài bằng 2, và cứ như vậy. Hình 2.3 chỉ ra quá trình của sự tìm kiếm trên một cây nhị phân đơn giản. Nếu như có một giải pháp, tìm kiếm theo chiều rộng đảm bảo sẽ tìm được nó, và nếu có nhiều giải pháp, tìm kiếm theo chiều rộng sẽ luôn tìm ra trạng thái đích nông nhất trước tiên. Dưới thuật ngữ của 4 tiêu chuẩn, tìm kiếm theo chiều rộng là hoàn thành, và nó được cung cấp một cách tối ưu chi phí đường dẫn bằng một hàm tăng của độ sâu các nút. Chúng ta phải xem xét thời gian và dung lượng bộ nhớ nó sử dụng để hoàn thành một cuộc tìm kiếm. Để làm điều này, chúng ta xem xét một không gian trạng thái có tính giả thiết trong đó mỗi trạng thái có thể được mở rộng để tạo ra các trạng thái mới b. Chúng ta nói rằng yếu tố phân nhánh của những trạng thái này (và của cây tìm kiếm) là b. Gốc của cây tìm kiếm sinh ra b nút ở mức đầu tiên, mỗi nút đó lại sinh ra thêm b nút, và sẽ có cả thảy b2 nút ở mức thứ hai. Mỗi một nút này lại sinh ra thêm b nút, tạo ra b3 nút ở mức thứ ba, và cứ như vậy. Bây giờ chúng ta giả sử rằng giải pháp cho bài toán này có độ dài đường đi là d, như vậy số nút tối đa được mở rộng trước khi tìm thấy một giải pháp là : 1 + b + b2 + b3 +.... + bd Đây là số nút tối đa, nhưng giải pháp có thể được tìm thấy ở bất cứ điểm nào thuộc mức có độ sâu là d. Do đó, trong trường hợp tốt nhất , số lượng các nút sẽ ít hơn. 16
Tìm kiếm với chi phí thấp nhất Phép tìm kiếm theo chiều rộng tìm được trạng thái đích, nhưng trạng thái này có thể không phải là giải pháp có chi phí thấp nhất đối với một hàm chi phí đường đi nói chung. Tìm kiếm với chi phí thấp nhất thay đổi chiến lược tìm kiếm theo chiều rộng bằng cách luôn luôn mở rộng nút có chi phí thấp nhất (được đo bởi công thức tính chi phí được đi g(n)), thay vì mở rộng nút có độ sâu nông nhất. Dễ thấy rằng tìm kiếm theo chiều rộng chính là tìm kiếm với chi phí thấp nhất với g(n)= DEPTH(n). Khi đạt được những điều kiện nhất định, giải pháp đầu tiên được tìm thấy sẽ đảm bảo là giải pháp rẻ nhất, do nếu như có một đường đi khác rẻ hơn, nó đã phải được mở rộng sớm hơn và như vậy nó sẽ phải được tìm thấy trước. Việc quan sát các hành động của chiến lược sẽ giúp giải thích điều này. Hãy xem xét bài toán tìm đường đi. Ván đề là đi từ S đến G, và chi phí của mỗi toán tử được ghi lại. Đầu tiên chiến lược sẽ tiến hành mở rộng trạng thái ban đầu, tạo ra đường đi tới A, B và C. Do đường đi tới A là rẻ nhất, nó sẽ tiếp tục được mở rộng, tạo ra đường đi SAG mà thực sự là một giải pháp, mặc dù không phải là phương án tối ưu. Tuy nhiên, giải thuật không công nhận nó là một giải pháp, bởi vì nó chi phí là 11, và nó bị che bởi đường đi SB có chi phí là 5 ở trong hàng đợi. Dường như thật là xấu hổ nếu sinh ra một giải pháp chỉ nhằm chôn nó ở sâu trong hàng đợi, nhưng điều đó là cần thiết nếu chúng ta muốn tìm một giải pháp tối ưu chứ không đơn thuần là tìm bất cứ giải pháp nào. Bước tiếp theo là mở rộng SB, tạo ra SBG, và nó là đường đi rẻ nhất còn lại trong hàng đợi, do vậy mục tiêu được kiểm tra và đưa ra một giải pháp. Phép tìm kiếm chi phí ít nhất tìm ra giải pháp rẻ nhất thoả mãn một yêu cầu đơn giản: Chi phí của một đường đi phải không bao giờ giảm đi khi chúng ta đi dọc theo đường đi. Nói cách khác, chúng ta mong muốn rằng g(Successor(n))  g(n) với mọi nút n. Giới hạn đối với chi phí đường đi không được giảm thực sự sẽ là vấn đề cần quan tâm nếu chi phí đường đi của một nút là tổng chi phí của các toán tử mà tạo nên đường đi. Nếu như mọi toán tử có một chi phí không âm, thì chi phí của đường đi không bao giờ có thể giảm đi khi chúng ta đi dọc theo đường đi và phép tìm kiếm với chi phí giống nhau có thể tìm được đường đi rẻ nhất mà không cần kiểm tra hết toàn bộ cây. Nhưng nếu một số toán tử có chi phí âm thì chẳng có một cách tìm kiếm nào khác ngoài một phép tìm kiếm toàn bộ tất cả các nút để tìm ra giải pháp tối ưu, bởi vì chúng ta sẽ không bao giờ biết được rằng khi nào một đường đi sẽ chuyển sang một bước với chi phí âm cao và do đó trở thành đường đi tốt nhất trong tất cả các đường đi, bất kể là nó dài bao nhiêu và chi phí thế nào. Tìm kiếm theo chiều sâu Tìm kiếm theo chiều sâu luôn luôn mở rộng một trong các nút ở mức sâu nhất của cây. Chỉ khi phép tìm kiếm đi tới một điểm cụt (một nút không phải đích mà không có phần mở rộng), việc tìm kiếm sẽ quay lại và mở rộng đối với những nút nông hơn. Chiến lược này có thể được thực hiện bởi General-search với một hàm hàng đợi mà luôn đưa các trạng thái mới được sinh ra vào trước hàng đợi. Do nút được mở rộng là sâu nhất, các nút kế tiếp của nó thậm chí sẽ sâu hơn và khi đó sẽ trở thành sâu nhất. Quá trình tìm kiếm được minh hoạ trong hình 2.4. 17
Bảng 4. Tìm kiếm theo chiều sâu Phép tìm kiếm theo chiều sâu yêu cầu dung lượng bộ nhớ rất khiêm tốn. Như hình vẽ cho thấy, nó chỉ cần phải lưu một đường duy nhất từ gốc tới nút lá, cùng với các nút anh em với các nút trên đường đi chưa được mở rộng còn lại. Đối với một không gian trạng thái với hệ số rẽ nhánh b và độ sâu tối đa m, phép tìm kiếm theo chiều sâu chỉ yêu cầu lưu trữ bm nút, ngược lai so với bd nút mà phép tìm kiếm theo chiều rộng yêu cầu trong trường hợp mục tiêu nông nhất ở độ sâu d. Độ phức tạp thời gian của phép tìm kiếm sâu là O(bm). Đối với những vấn đề mà có rất nhiều giải pháp, phép tìm kiếm sâu có thể nhanh hơn tìm kiếm rộng, bởi vì nó có một cơ hội tốt tìm ra một giải pháp chỉ sau khi khám phá một phần nhỏ của toàn bộ không gian. Tìm kiếm theo chiều rộng sẽ vẫn phải tìm tất cả các đường đi có độ sâu d-1 trước khi xem xét bất cứ đường đi nào có độ sâu d. Phép tìm kiếm theo chiều sâu vẫn cần thời gian O(bm) trong trường hợp tồi nhất. Mặt hạn chế của phép tìm kiếm sâu là nó có thể bị tắc khi đi theo một đường sai. Rất nhiều bài toán có các cây tìm kiếm rất sâu, thậm chí vô hạn, vì vậy tìm kiếm sâu sẽ không bao giờ có thể quay trở lại được một trong các nút gần đỉnh của cây sau khi có một sự lựa chọn sai. Phép tìm kiếm sẽ luôn luôn tiếp tục đi xuống mà không quay trở lại, thậm chí khi có một giải pháp ở mức rất nông tồn tại. Như vậy đối với những bài toán này, phép tìm kiếm sâu sẽ hoặc là bị sa lầy trong một vòng lặp vô hạn và không bao giờ đưa ra một giải pháp, hoặc là cuối cùng nó có thể đưa ra một đường đi giải pháp mà dài hơn so với phương án tối ưu. Điều đó có nghĩa là phép tìm kiếm theo chiều sâu là không hoàn thành và không tối ưu. Bởi vì điều này, cần tránh sử dụng phép tìm kiếm sâu cho các cây tìm kiếm có độ sâu tối đa là vô hạn hoặc rất sâu. Việc thực hiện phép tìm kiếm sâu với general-search là khá tầm thường: Function tìm kiếm sâu(bài toán) returns một giải pháp hoặc thất bại returns General-search(bài toán, xếp ở đầu hàng đợi) Bảng 5. Tìm kiếm theo chiều sâu với general-search Người ta thường thực hiện phép tìm kiếm sâu cùng với một hàm đệ qui mà gọi tới chính nó ở lần lượt mỗi con của nó. Trong trường hợp này, hàng đợi được lưu trữ hoàn toàn trong không gian địa phương của mỗi lần gọi trong ngăn xếp gọi. Tìm kiếm theo độ sâu giới hạn 18
Tìm kiếm theo độ sâu giới hạn tránh các bẫy mà tìm kiếm theo chiều sâu mắc phải bằng cách đặt một giới hạn đối với độ sâu tối đa của đường đi. Giới hạn này có thể được thực hiện với một giải thuật tìm kiếm theo độ sâu giới hạn đặc biệt hoặc sử dụng các giải thuật tìm kiếm tổng quát với các toán tử theo dõi độ sâu. Chẳng hạn, trên bản đồ Rumani, có 20 thành phố, vì vậy chúng ta biết rằng nếu như có một giải pháp, thì nó phải có độ dài nhiều nhất là bằng 19. Chúng ta có thể thực hiệnviệc giới hạn độ sâu bằng cách sử dụng các toán tử dưới dạng “ Nếu bạn ở thành phố A và vừa đi một đoạn đường ít hơn 19 bước, thì khởi tạo một trạng thái mới ở thành phố B với độ dài đường đi lớn hơn 1”. Với tập các toán tử mới này, chúng ta đảm bảo tìm thấy giải pháp nếu nó tồn tại, nhưng chúng ta vẫn không đảm bảo tìm thấy giải pháp ngắn nhất trước tiên: phép tìm kiếm theo chiều sâu giới hạn là hoàn thành nhưng không tối ưu. Nếu chúng ta chọn một giới hạn độ sâu mà quá nhỏ, thì phép tìm kiếm theo chiều sâu giới hạn thậm chí không hoàn thành. Độ phức tạp về không gian và thời gian của phép tìm kiếm theo chiều sâu giới hạn tương đương với phép tìm kiếm sâu. Nó mất O(bl) thời gian và O(bl) không gian, với l là giới hạn độ sâu. Tìm kiếm lặp sâu dần (Iterative Deepening Search) Thành phần khó khăn của tìm kiếm theo độ sâu giới hạn đem lại một giới hạn khá tốt. Chúng ta lấy 19 như là một giới hạn độ sâu “hiển nhiên” cho bài toán Rumani, nhưng thực ra nếu chúng ta nghiên cứu kỹ bản đồ, chúng ta sẽ thấy rằng bất cứ thành phố nào cũng có thể đi đến được từ bất kỳ thành phố nào khác với nhiều nhất là 9 bước. Con số này, được biết đến như là đường kính của không gian trạng thái , cho chúng ta một giới hạn độ sâu tốt hơn, và đưa đến một phép tìm kiếm theo độ sâu giới hạn hiệu quả hơn. Tuy nhiên, đối với hầu hết các bài toán, chúng ta chỉ biết một giới hạn độ sâu tốt sau khi đã giải quyết xong bài toán. Function tìm kiếm -lặp -sâu dần(bài toán) returns một dãy giải pháp Inputs: bài toán, một vấn đề cần giải quyết For độ sâu = 0 to  do If tìm kiếm -độ sâu -giới hạn(bài toán, độ sâu) thành công then returns kết quả End Hình 3.15 Giải thuật tìm kiếm lặp sâu dần Return thất bại Bảng 6 . Tìm kiếm lặp sâu dần Phép tìm kiếm lặp sâu dần là một chiến lược né tránh vấn đề lựa chọn giới hạn độ sâu tốt nhất và cố gằng thử tất cả các giơí hạn độ sâu có thể: đầu tiên thử độ sâu bằng 0, sau đó độ sâu bằng 1, tiếp theo là 2, và cứ như vậy. Về mặt hiệu quả, việc lặp sâu dần kết hợp lợi ích của cả hai phép tìm kiếm theo chiều sâu và tìm kiếm theo chiều rộng. Đây là phương pháp tối ưu và đầy đủ, giống như phép tìm kiếm theo chiều rộng, nhưng chỉ yêu cầu bộ nhớ rất ít như phép tìm kiếm sâu yêu cầu. Thứ tự mở rộng các trạng thái tương tự với tìm kiếm rộng, ngoại trừ việc một số trạng thái được mở rộng nhiều lần. Phép tìm kiếm lặp sâu dần có thể dường như là hơi lãng phí, bởi vì có rất nhiều trạng thái được mở rộng nhiều lần. Tuy nhiên, đối với hầu hết các bài toán, tổng chi phí của sự mở rộng nhiều lần này thực ra khá nhỏ. Bằng trực giác, có thể thấy rằng trong một cây tìm kiếm theo luật số mũ, hầu hết tất cả các nút là ở mức thấp nhất, vì vậy việc các mức ở bên trên được mở rộng nhiều lần sẽ không thành vấn đề lắm. nhắc lại rằng số lần mở rộng trong phép tìm kiếm theo độ sâu giới hạn tới độ sâu d với hệ số phân nhánh b là: 1+ b + b2+ ….+ bd-2+ bd-1+ bd 19
Cụ thể, cho b=10, và d=5 thì số lần mở rộng là : 1+10+100+1000+10.000+100.000= 111.111 Trong phép tìm kiếm lặp sâu dần, các nút ở mức dưới cùng được mở rộng một lần, những nút ở trên mức dưới cùng được mở rộng hai lần, và cứ như vậy đến gốc của cây tìm kiếm sẽ được mở rộng d+1 lần. Do đó tổng số lần mở rộng trong một phép tìm kiếm lặp sâu dần là : (d+1)1 + (d)b + (d-1)b2+ …..+ 3bd-2 + 2bd-1 + 1bd Và cụ thể lại cho b=10, và d=5 thì số lần mở rộng là : 6+50+400+3000+20.000+100000= 123.456 Như vậy chúng ta thấy, một phép tìm kiếm lặp sâu dần từ độ sâu1 xuống tới độ sâu d chỉ mở rộng nhiều hơn khoảng11% số nút so với phép tìm kiếm theo chiều rộng hay phép tìm kiếm theo chiều sâu tới độ sâu d khi hệ số phân nhánh b=10. Hệ số phân nhánh càng cao, tổng số các trạng thái được mở rộng lặp lại (nhiều lần) càng thấp, nhưng thậm chí khi hệ số phân nhánh là 2, phép tìm kiếm lặp sâu dần chỉ mở rộng số trạng thái nhiều gấp hai so với một phép tìm kiếm theo chiều rộng đầy đủ. Điều đó có nghĩa rằng độ phức tạp thời gian của phép tìm kiếm lặp sâu dần vẫn là O(bd), độ phức tạp không gian là O(bd). Nói chung, lặp sâu dần là phép tìm kiếm được tham khảo đến khi có một không gian tìm kiếm lớn và độ sâu của giải pháp là không biết trước. Tìm kiếm tiến lùi Ý tưởng của phép tìm kiếm tiến lùi là thực hiện đồng thời hai phép tìm kiếm: tìm kiếm từ trạng thái đầu về phía trước và tìm kiếm ngược lại từ trạng thái đích, và dừng lại khi hai phép tìm kiếm này gặp nhau. Đối với những bài toán mà hệ số rẽ nhánh là b ở cả hai hướng, phép tìm kiếm tiến lùi có thể đưa lại một sự khác biệt rất lớn. Nếu chúng ta vẫn giả sử rằng có một giải pháp ở độ sâu d, thì giải pháp sẽ được tìm thấy sau O(2bd/2) = O(bd/2) bước, bởi vì mỗi phép tìm kiếm tiến và lùi chỉ phải đi một nửa quãng đường. Xét ví dụ cụ thể, với b=10 và d=6, phép tìm kiếm rộng sinh ra 1.111.111 nút, trong khi đó phép tìm kiếm tiến lùi thành công khi mỗi hướng ở độ sâu bằng 3, tại thời điểm 2.222 nút đã được tạo ra. Điều này về mặt lý thuyết nghe rất hấp dẫn. Chúng ta cần phải xem xét một số vấn đề trước khi thực hiện giải thuật Câu hỏi chính là, tìm kiếm lùi từ đích có nghiã là như thế nào? Chúng ta định nghĩa các nút tổ tiên (predecessor) của một nút n là tất cả các nút mà có nút n là nút kế vị (successor). Phép tìm kiếm lùi có nghĩa là sinh ra những nút tổ tiên liên tiếp bắt đầu từ nút đích. Khi tất cả các toán tử là có thể đảo ngược, các tập kế vị và tập tổ tiên là giống hệt nhau. Tuy nhiên, đối với một số bài toán, việc tính toán các phần tử tổ tiên là rất khó khăn. Con số O(bd/2) của độ phức tạp thừa nhận rằng quá trình kiểm tra sự giao nhau của hai biên giới có thể được thực hiện trong một khoảng thời gian không đổi (như vậy, nó không phụ thuộc vào số trạng thái). Điều này thường có thể thu được với một bảng băm. Để hai phép tìm kiếm cuối cùng sẽ gặp nhau, tất cả các nút của ít nhất một trong hai phép tìm kiếm phải được lưu giữ trong bộ nhớ (giống như với trường hợp của phép tìm kiếm rộng). Điều này có nghĩa là độ phức tạp không gian của phép tìm kiếm tiến lùi không có đủ thông tin là O(bd/2). So sánh các chiến lược tìm kiếm 20