Giáo trình Lập trình máy tính - Trí tuệ nhân tạo và hệ chuyên gia (Phần 1)
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
: Đạt trung bình
: Đạt khá
50-69
70-85
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
trình
Thiết kế mạng và quản trị
mạng
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à
hệ chuyên gia
Phân tích
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
Chuyên đề tự chọn
Cơ sở dữ liệu
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
Xử lý dữ
Lập trình xử lý ký hiệu
-
Xử lý dữ liệu định tính (các ký hiệu tượng
trưng) và xử lý tri thức.
liệu
Tri thức được cấu trúc trong bộ nhớ làm
việc theo các ký hiệu.
-
Dữ
liệu
trong bộ nhớ được đánh địa chỉ số.
Xử lý theo các thuật giải heuristic và theo
các cơ chế lập luận.
-
Xử lý theo
các thuật toán
Định hướng xử lý các đại lượng định tính,
các ký hiệu tượng trưng và danh sách.
-
Định hướng
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á
trình thực hiện.
tự hoặc theo mẻ
-
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.
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:
“tiềm năng của máy tính làm được mọi thứ, xem nó là thông minh.” (Rowe, 1988)
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
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
Tải về để xem bản đầy đủ
103 trang
12/05/2022
1560
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Lập trình máy tính - Trí tuệ nhân tạo và hệ chuyên gia (Phần 1)", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_lap_trinh_may_tinh_tri_tue_nhan_tao_va_he_chuyen.pdf
