NỘI DUNG Chương 1. Giới thiệuTTNT Chương 2. Phép tính vị từ Chương 3. Cấu trúc và kế hoạch dùng cho tìm kiếm trên khoảng trống trạng thái ( TK-KGTT ) Chương 4. Tìm kiếm heuristic Chương 5. Điều khiển và thiết lập TK-KGTT Chương 6 : Giải quyết yếu tố tri fthức sâu xa Chương 7 : Suy luận với thông tin không đúng chuẩn hoặc không khá đầy đủ. Chương 8. Suy luận tự động hóa ( Automatic reasoning ) Chương 9. Học máy TRÍ TUỆ NHÂN TẠO LÀ GÌ ? Là một nhánh của khoa học máy tính tương quan đến sự tự động hóa hành vi mưu trí. Trí tuệ là gì ? Các câu hỏi chưa có câu vấn đáp : Liệu trí tuệ có phải là một năng lực duy nhất hay chỉ là một tên gọi cho một tập hợp những hành vi phân biệt và độc lập nhau ? Thế nào là năng lực phát minh sáng tạo ? Thế nào là trực giác ? Điều gì diễn ra trong quy trình học ? Có thể Tóm lại ngay về tính trí tuệ từ việc quan sát một hành vi hay không hay cần phải có bộc lộ của một chính sách nào đó nằm bên trong ?
81 trang
| Chia sẻ : maiphuongtl
| Lượt xem: 2907
| Lượt tải : 1
Bạn đang xem trước 20 trang tài liệu Bài giảng Trí tuệ nhân tạo – Đại học Cần Thơ, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
TRÍ TUỆ NHÂN TẠO Khoa Coâng Ngheä Thoâng Tin Tröôøng Ñaïi hoïc Caàn Thô Artificial Intelligence : Structure and Strategies for Complex Problem Solving. ( 3 rd edition – 1997 ) George F. Luger, William A. Stubblefield Giáo viên : Trần Ngân Bình Nội Dung Chương 1. Giới thiệuTTNT Chương 2. Phép tính vị từ Chương 3. Cấu trúc và kế hoạch dùng cho tìm kiếm trên khoảng trống trạng thái ( TK-KGTT ) Chương 4. Tìm kiếm heuristic Chương 5. Điều khiển và thiết lập TK-KGTT Chương 6 : Giải quyết yếu tố tri fthức nâng cao Chương 7 : Suy luận với thông tin không đúng chuẩn hoặc không không thiếu. Chương 8. Suy luận tự động hóa ( Automatic reasoning ) Chương 9. Học máy Trí Tuệ Nhân Tạo là gì ? Là một nhánh của khoa học máy tính tương quan đến sự tự động hóa hành vi mưu trí. Trí tuệ là gì ? Các câu hỏi chưa có câu vấn đáp : Liệu trí tuệ có phải là một năng lực duy nhất hay chỉ là một tên gọi cho một tập hợp những hành vi phân biệt và độc lập nhau ? Thế nào là năng lực phát minh sáng tạo ? Thế nào là trực giác ? Điều gì diễn ra trong quy trình học ? Có thể Tóm lại ngay về tính trí tuệ từ việc quan sát một hành vi hay không hay cần phải có biểu lộ của một chính sách nào đó nằm bên trong ? C. 1 – Giới thiệu Định Nghĩa AI Rich, E. and K. Knight. 1991. Artificial Intelligence. New York : McGraw-Hill. “ Artificial intelligence ( AI ) is the study of how to make computers do things which at the moment, people do better. ” George Luger : “ An AI approach problem-solving is one which : uses domain-specific knowledge to find a good-enough solution to a hard problem in a reasonable amount of time. ” C. 1 – Giới thiệu Turing Test Ưu điểm của Turing Test Khái niệm khách quan về trí tuệ Tránh đi những đàm đạo về quy trình bên trong và ý thức Loại trừ định kiến thiên vị của người thẩm vấn C. 1 – Giới thiệu Các quan điểm phản đối Turing Test Thiên vị những trách nhiệm xử lý yếu tố bằng ký hiệu Trói buộc sự mưu trí máy tính theo kiểu con người, trong khi con người có : Bộ nhớ số lượng giới hạn Có khuynh hướng nhầm lẫn Tuy nhiên, trắc nghiệm Turing đã phân phối một cơ sở cho nhiều sơ đồ nhìn nhận dùng thực sự cho những chương trình TTNT văn minh. C. 1 – Giới thiệu Các Ứng Dụng của TTNT Trò chơi và những bài toán đố Suy luận và chứng minh định lý tự động hóa Các hệ chuyên viên ( những hệ tri thức ) Xử lý ngôn từ tự nhiên Lập kế hoạch và người máy Máy học Mạng Neuron và giải thuật di truyền … C. 1 – Giới thiệu Trí Tuệ Nhân Tạo – Đặc Điểm Sử dụng máy tính vào suy luận trên những ký hiệu, nhận dạng qua mẫu, học, và những suy luận khác … Tập trung vào những yếu tố “ khó ” không thích hợp với những giải thuật mang tính thuật toán. Quan tâm đến những kỹ thuật xử lý yếu tố sử dụng những thông tin không đúng chuẩn, không không thiếu, mơ hồ … Cho giải thuật ‘ đủ tốt ’ chứ không phải là giải thuật đúng chuẩn hay tối ưu. Sử dụng heuristics – “ tuyệt kỹ ” Sử dụng tri thức trình độ … C. 1 – Giới thiệu Những yếu tố chưa được xử lý Chương trình chưa tự sinh ra được heuristic Chưa có năng lực giải quyết và xử lý song song của con người Chưa có năng lực diễn giải một yếu tố theo nhiều giải pháp khác nhau như con người. Chưa có năng lực giải quyết và xử lý thông tin trong thiên nhiên và môi trường liên tục như con người. Chưa có khả năng học như con người. Chưa có năng lực tự thích nghi với môi trường tự nhiên. C. 1 – Giới thiệu TTNT = Biểu Diễn + tìm kiếm TTNT màn biểu diễn và tìm kiếm Hệ thống ký hiệu vật lý Hệ thống ký hiệu = tập hợp những mẫu và những quy trình, trong đó những quy trình sản xuất, triệt tiêu và đổi khác những mẫu. Các hành vi mưu trí đạt được bằng việc sử dụng : Các mẩu ký hiệu để màn biểu diễn những góc nhìn quan trọng của nghành nghề dịch vụ bài toán. Các phép toán trên những mẫu này để sinh ra những giải thuật có năng lực của bài toán .. Tìm kiếm một lời giải trong số những năng lực này. TTNT màn biểu diễn và tìm kiếm Giả thuyết về mạng lưới hệ thống ký hiệu vật lý “ Một mạng lưới hệ thống ký hiệu vật lý có những phương tiện đi lại cần và đủ cho một hành vi mưu trí tổng quát ” ( Nowell và Simon ) Allen Newell and Herbert A. Simon, Computer Science as Empirical Inquiry : Symbols and Search, Communications of the ACM ( March 1976 ) TTNT màn biểu diễn và tìm kiếm TTNT như thể sự màn biểu diễn và tìm kiếm Sự màn biểu diễn phải : Cung cấp một cơ cấu tổ chức tự nhiên để biểu lộ tri thức / thông tin / tài liệu một cách khá đầy đủ => Tính miêu tả Hỗ trợ việc thực thi một cách hiệu suất cao việc tìm kiếmđáp án cho một yếu tố => Tính hiệu suất cao Liệu việc tìm kiếm : Có kết thúc không ? Có chắc như đinh sẽ tìm được lời giải không ? Có chắc như đinh sẽ tìm được lời giải tối ưu không ? TTNT trình diễn và tìm kiếm TTNT như thể trình diễn và tìm kiếm Giải quyết yếu tố như thể sự tìm kiếm lời giải trong một đồ thị khoảng trống trạng thái : Nút ~ trạng thái ( node ~ state ) Liên kết ( link ) Ví dụ : Trò chơi tic-tac-toe Chẩn đoán trục trặc máy móc trong xe hơi TTNT màn biểu diễn và tìm kiếm KGTT của Trò Chơi Tic-Tac-Toe TTNT màn biểu diễn và tìm kiếm Chẩn đoán trục trặc máy móc trong xe hơi TTNT màn biểu diễn và tìm kiếm Chương 2 – Phép tính vị từ Logic hình thức Logic hình thức = Biễu diễn + suy luận Dùng như thể một chính sách biễu diễn tri thức Dùng như là tìm kiếm khoảng trống trạng thái trong những đồ thị And / Or Dùng để hình thức hóa những luật heuristic Có hai ngôn từ : Phép tính mệnh đề Phép tính vị từ C2 – Phép tính vị từ Phép tính mệnh đề ( 1 ) Mệnh đề : là những câu chứng minh và khẳng định về quốc tế. Mệnh đề hoàn toàn có thể đúng ( true ) hoặc sai ( false ). Mệnh đề đơn thuần : Đồng là một sắt kẽm kim loại => Đúng Gỗ là một sắt kẽm kim loại => Sai Hôm nay là thứ Hai => Sai Ký hiệu trong phép tính mệnh đề : Ký hiệu mệnh đề : P., Q., R, S, … Ký hiệu chân lý : true, false Các phép toán logic : ( hội ), ( tuyển ), ( phủ định ), ( kéo theo ), = ( tương tự ) C2 – Phép tính vị từ Phép tính mệnh đề ( 2 ) Định nghĩa câu trong phép tính mệnh đề : Mỗi ký hiệu mệnh đề, ký hiệu chân lý là một câu. Phủ định của một câu là một câu. Hội, tuyển, kéo theo, tương tự của hai câu là một câu. Ký hiệu ( ), [ ] được dùng để nhóm những ký hiệu vào những biểu thức con. Một biểu thức mệnh đề được gọi là một câu ( hay công thức dạng chuẩn – WFF ) nó hoàn toàn có thể được tạo thành từ những ký hiệu hợp lệ trải qua một dãy những luật trên. Ví dụ : ( ( P Q ) R ) = P Q R C2 – Phép tính vị từ Ngữ Nghĩa của Phép Tính MĐ Sự thông dịch ( Intepretation ) : Là sự gán giá trị chân lý ( T / F ) cho những câu mệnh đề. Là một sự khẳng định chắc chắn chân lý của những câu mệnh đề trong một quốc tế khả hữu nào đó. Sự thông dịch của một câu kép thường được xác lập bằng bảng chân lý : P Q P P Q P Q P Q P = Q T T F T T T T T F F F T F F F T T F T T F F F T F F T T C2 – Phép tính vị từ Sự Tương Đương của Phép Tính MĐ ( P ) = P ( P Q ) = ( P Q ) Luật tương phản : ( P Q ) = ( Q P ) Luật De Morgan : ( P Q ) = ( P Q ), và ( P Q ) = ( P Q ) Luật giao hoán : ( P Q ) = ( Q P ), và ( P Q ) = ( Q P ) Luật phối hợp : ( ( P Q ) R ) = ( P ( Q R ) ), ( ( P Q ) R ) = ( P ( Q R ) ) Luật phân phối : P ( Q R ) = ( P Q ) ( P R ), P ( Q R ) = ( P Q ) ( P R ) C2 – Phép tính vị từ Phép TínhVị Từ ( 1 ) Ký hiệu vị từ là tập hợp gồm những vần âm, chữ số, ký hiệu “ _ ”, và được khởi đầu bằng vần âm. VD : X3, tom_and_jerry Ký hiệu vị từ hoàn toàn có thể là : ký hiệu chân lý : true, false Hằng : dùng để chỉ một đối tượng người tiêu dùng / thuộc tính trong quốc tế. Ký hiệu mở màn bằng chữ thường : VD : helen, yellow, rain Biến : dùng để chỉ một lớp tổng quát những đối tượng người dùng / thuộc tính. Ký hiệu khởi đầu bằng chữ hoa : VD : X, People, Students Hàm : dùng để chỉ một hàm trên những đối tượng người dùng. Ký hiệu khởi đầu bằng chữ thường : VD : father, plus Mỗi ký hiệu hàm có một ngôi n, chỉ số lượng những đối số của hàm. Vị từ : dùng để định nghĩa một mối quan hệ giữa không hoặc nhiều đối tượng người dùng. Ký hiệu vị từ khởi đầu bằng chữ thường. VD : likes, equals, part_of C2 – Phép tính vị từ Phép TínhVị Từ ( 2 ) Biểu thức hàm : là một ký hiệu hàm theo sau bởi n đối số. VD : father ( david ) price ( bananas ) like ( tom, football ) Mục ( term ) : là một hằng, một biến hay một biểu thức hàm Câu sơ cấp : là một hằng vị từ với n ngôi theo sau bởi n thành phần ( mỗi thành phần là một mục ) đặt trong dấu ( ), cách nhau bởi dấu ‘, ’ và kết thúc với dấu ‘. ’ Trị chân lý true, false là những câu sơ cấp. Câu sơ cấp còn được gọi là : biểu thức sơ cấp ( atomic expression ), nguyên tử ( atom ) hay mệnh đề ( proposition ) VD : friends ( helen, marry ). likes ( hellen, mary ). likes ( helen, sister ( mary ) ). likes ( X, ice-cream ). Ký hiệu vị từ trong những câu này là friends, likes. C2 – Phép tính vị từ Phép TínhVị Từ ( 3 ) Câu : được tạo ra bằng cách phối hợp những câu sơ cấp sử dụng : Các phép liên kết logic : , , , , = Các lượng tử biến : Lượng tử thông dụng : dùng để chỉ một câu là đúng với mọi giá trị của biến lượng giá VD : X likes ( X, ice-cream ). Lượng tử sống sót : dùng để chỉ một câu là đúng với một số ít giá trị nào đó của biến lượng giá. VD : Y friends ( Y, tom ). VD : likes ( helen, chocolat ) likes ( bart, chocolat ). X foo ( X, two, plus ( two, three ) ) equal ( plus ( three, two ), five ) ( foo ( two, two, plus ( two, three ) ) ) ( equal ( plus ( three, two ), five ) = true ). C2 – Phép tính vị từ Ngữ Nghĩa của Phép Tính Vị Từ Sự thông dịch của một tập hợp những câu phép tính vị từ : là một sự gán những thực thể trong miền của yếu tố đang đề cập cho mỗi ký hiệu hằng, biến, vị từ và hàm. Giá trị chân lý của một câu sơ cấp được xác lập qua sự thông dịch. Đối với những câu không phải là câu sơ cấp, sử dụng bảng chân lý cho cho những phép nối kết, và : Giá trị của câu X là true nếu là T cho tổng thể những phép gán hoàn toàn có thể được cho X. Giá trị của câu X là true nếu sống sót một phép gán cho X làm cho có giá trị T. C2 – Phép tính vị từ Phép Tính Vị Từ Bậc Nhất Phép tính vị từ bậc nhất được cho phép những biến lượng giá tham chiếu đến những đối tượng người tiêu dùng trong miền của yếu tố đang đề cập nhưng KHÔNG được tham chiếu đến những vị từ và hàm. VD không hợp lệ : ( Likes ) Likes ( helen, ice-cream ) VD hợp lệ : Nếu ngày mai trời không mưa, tom sẽ đi biển. weather ( rain, tomorrow ) go ( tom, sea ) Tất cả những cầu thủ bóng rổ đều cao. X ( basketball_player ( X ) tall ( X ) ) Có người thích coca-cola X person ( X ) likes ( X, coca-cola ) Không ai thích thuế X likes ( X, taxes ) C2 – Phép tính vị từ Ví dụ về phép tính vị từ Cho trước : mother ( eve, abel ) mother ( eve, cain ) father ( adam, abel ) father ( adam, cain ) X Y father ( X, Y ) mother ( X, Y ) parent ( X, Y ) X Y Z parent ( Z, X ) parent ( Z, Y ) sibling ( X, Y ) Có thể suy luận : parent ( eve, abel ) parent ( eve, cain ) parent ( adam, abel ) parent ( adam, cain ) sibling ( abel, cain ) sibling ( cain, abel ) sibling ( abel, abel ) sibling ( cain, cain ) ! không có nghĩa C2 – Phép tính vị từ Các luật suy diễn Luật Modus Ponens ( MP ) : P Q P Q Luật Modus Tolens ( MT ) : P Q Q P Luật triển khai phổ cập ( Universal Instantiation ) : X P. ( X ) a thuộc miền xác lập của X P ( a ) C2 – Phép tính vị từ Ví Dụ “ Tất cả mọi người đều chết và Socrates là người, do đó Socrates sẽ chết ” => X man ( X ) mortal ( X ) ( 1 ) man ( socrates ) ( 2 ) Từ ( 1 ), ( 2 ) bằng luật UI, ta có : man ( socrates ) mortal ( socrates ) ( 3 ) Từ ( 3 ) và ( 2 ) bằng luật MP, ta có : mortal ( bill ) ( 4 ) C2 – Phép tính vị từ Đối sánh mẫu và phép hợp nhất Để vận dụng những luật như MP, một hệ suy diễn phải có năng lực xác lập khi nào thì hai biểu thức là một hay còn gọi là đối sánh tương quan ( match ). Phép hợp nhất là một giải thuật dùng để xác lập những phép thế ( substitution ) thiết yếu để làm cho hai biểu thức vị từ đối sánh tương quan nhau. Một biến hoàn toàn có thể sửa chữa thay thế bởi một mục bất kể : C2 – Phép tính vị từ Biến Hằng Biểu thức hàm hoàn toàn có thể chứa những biến khác Biến khác Thay thế bởi Biến đã kết buộc ( bound ) Biến chưa kết buộc ( unbound ) “ Giải thuật ” Đối Sánh Mẫu Hằng / hằng đối sánh tương quan : chỉ khi chúng giống hệt nhau VD : tom không đối sánh tương quan với jerry Hằng a / biến X đối sánh tương quan : Biến chưa kết buộc : biến trở thành kết buộc với hằng => Khi đó ta có phép thế { a / X } Biến đã kết buộc : xem ( 1 ) Biến X / biến Y đối sánh tương quan : Hai biến chưa kết buộc : luôn luôn đối sánh tương quan => Khi đó ta có phép thế { X / Y } Một biến kết buộc và một biến chưa kết buộc : xem ( 2 ) Hai biến kết buộc : xem ( 1 ) Biểu thức / biểu thức đối sánh tương quan : chỉ khi những tên hàm hoặc vị từ, số ngôi giống nhau thì vận dụng đối sánh tương quan từng đối số một. VD : goo ( X ) – không đối sánh tương quan với foo ( X ) hay goo ( X, Y ) – đối sánh tương quan với goo ( foo ( Y ) ) với phép thế { foo ( Y ) / X } C2 – Phép tính vị từ Phạm vi của một biến Phạm vi của một biến là một câu. Một khi biến đã bị kết buộc, những phép hợp nhất theo sau và những suy luận sau đó phải giữ sự kết buộc này VD : man ( X ) => mortal ( X ) Nếu ta thế X bởi socrates thì ta được : man ( socrates ) => mortal ( socrates ) C2 – Phép tính vị từ Ví dụ : Biểu thức đối sánh tương quan Hãy xác lập xem foo ( X, a, goo ( Y ) ) có đối sánh tương quan với những biểu thức sau hay không ? Nếu có thì cho biết phép thế tương ứng : foo ( X, b, foo ( Y ) ) foo ( fred, a, goo ( Z ) ) foo ( X, Y ) moo ( X, a, goo ( Y ) ) foo ( Z, a, goo ( moo ( Z ) ) ) foo ( W, a, goo ( jack ) ) Cho biết tác dụng có được khi hợp nhất p ( a, X ) với : p ( Y, Z ) => q ( Y, Z ) q ( W, b ) => r ( W, b ) C2 – Phép tính vị từ Thủ tục hợp nhất “ Unify ” Ghi chú : p ( a, b ) ~ ( p a b ) p ( f ( a ), g ( X, Y ) ~ ( p ( f a ) ( g x Y ) ) C2 – Phép tính vị từ Tích những phép thế hợp nhất ( Composition ) Nếu S và S ’ là hai tập hợp phép thế, thì tích của S và S ’ được xác lập bằng cách vận dụng S ’ cho những thành phần của S và bổ trợ tác dụng này vào S. VD : { X / Y, W / X }, { V / X }, { a / V, f ( b ) / W } => { a / Y, f ( b ) / Z } C2 – Phép tính vị từ Hợp tử tổng quát nhất ( Most General Unifier ) Yêu cầu của giải thuật hợp nhất là hợp tử ( unifier ) càng tổng quát càng tốt : đó là hợp tử tổng quát nhất tìm thấy cho hai biểu thức. VD : Khi hợp nhất p ( X ) và p ( Y ) : không nên chọn { fred / X, fred / Y } vì fred không phải là hợp tử tổng quát nhất nên chọn { Z / Y, Z / Y } C2 – Phép tính vị từ Ứng Dụng : Hệ tư vấn kinh tế tài chính ( 1 ) Hệ tư vấn kinh tế tài chính hoạt động giải trí theo những nguyên tắc sau : Các cá thể không đủ tiền tiết kiệm chi phí nên tăng tiền tiết kiệm ngân sách và chi phí, bất kể thu nhập là bao nhiêu. Các cá thể có đủ tiền tiết kiệm ngân sách và chi phí và đủ thu nhập nên xem xét việc góp vốn đầu tư vào sàn chứng khoán. Các cá thể với thu nhập thấp nhưng đủ tiền tiết kiệm ngân sách và chi phí hoàn toàn có thể chia phần thu nhập thêm vào tiết kiệm chi phí và sàn chứng khoán. Với : tiết kiệm ngân sách và chi phí đủ là 5000 USD / người phụ thuộc vào Thu nhập đủ 15000 $ + ( 4000 USD / người phụ thuộc vào ) C2 – Phép tính vị từ Ứng Dụng : Hệ tư vấn kinh tế tài chính ( 2 ) Xâu dựng mạng lưới hệ thống logic với những câu vị từ như sau : savings_account ( inadequate ) investment ( saving ) savings_account ( adequate ) income ( adequate ) investment ( stocks ) savings_account ( adequate ) income ( inadequate ) investment ( combination ) X amount_saved ( X ) Y ( dependents ( Y ) greater ( X, minsavings ( Y ) ) ) savings_account ( adequate ) X amount_saved ( X ) Y ( dependents ( Y ) greater ( X, minsavings ( Y ) ) ) savings_account ( inadequate ) X earning ( X, steady ) Y ( dependents ( Y ) greater ( X, minincome ( Y ) ) ) income ( adequate ) X earning ( X, steady ) Y ( dependents ( Y ) greater ( X, minincome ( Y ) ) ) income ( inadequate ) X earning ( X, unsteady ) income ( inadequate ) With : minavings ( X ) = 5000 * X minincome ( X ) = 15000 + ( 4000 * X ) C2 – Phép tính vị từ Ứng Dụng : Hệ tư vấn kinh tế tài chính ( 3 ) Một nhà góp vốn đầu tư với thực trạng như sau : amount_saved ( 22000 ) earnings ( 25000, steady ) dependents ( 3 ) investment ( ? ) Dùng phép hợp nhất và luật Modus Ponens, suy ra : income ( inadequate ) savings_account ( adequate ) investment ( combination ) C2 – Phép tính vị từ Bài Tập Chương 2 Chương 3 – Cấu trúc và kế hoạch cho TK – KGTT Khi màn biểu diễn một yếu tố như thể một đồ thị khoảng trống trạng thái, tất cả chúng ta hoàn toàn có thể sử dụng kim chỉ nan đồ thị để nghiên cứu và phân tích cấu trúc và độ phức tạp của những yếu tố cũng như những thủ tục tìm kiếm. C 3 – Tìm kiếm khoảng trống trạng thái Hệ thống cầu thành phố Konigsberg và trình diễn đồ thị tương ứng Nội dung chương 3 Định nghĩa Không Gian Trạng Thái Các kế hoạch tìm kiếm trên khoảng trống trạng thái : TK hướng từ tài liệu ( data – driven ) TK hướng từ tiềm năng ( goal – driven ). Tìm kiếm trên khoảng trống trạng thái : TK rộng ( breath – first search ) TK sâu ( depth – first search ) TK sâu bằng cách đào sâu nhiều lần ( depth – first search with iterative deepening ) Sử dụng khoảng trống trạng thái để biễu diễn suy luận với phép tính vị từ : Đồ thị Và / Hoặc ( And / Or Graph ) C 3 – Tìm kiếm khoảng trống trạng thái ĐN : KHÔNG GIAN TRẠNG THÁI Một KGTT ( state space ) là 1 bộ [ N, A, S, GD ] trong đó : N ( node ) là những nút hay những trạng thái của đồ thị. A ( arc ) là tập những cung ( hay những link ) giữa những nút. S ( solution ) là một tập chứa những trạng thái đích của bài toán. ( S N S ) Các trạng thái trong GD ( Goal Description ) được miêu tả theo một trong hai đặc tính : Đặc tính hoàn toàn có thể thống kê giám sát được những trạng thái gặp trong quy trình tìm kiếm. VD : Tic-tac-toe, 8 – puzzle, … Đặc tính của đường đi được hình thành trong quy trình tìm kiếm. VD : TSP Đường đi của giải thuật ( solution path ) là một con đường đi qua đồ thị này từ một nút thuộc S đến một nút thuộc GD. C 3 – Tìm kiếm khoảng trống trạng thái Một phần KGTT tiến hành trong Tic-tac-toe Đồ thị có hướng không tái diễn ( directed acyclic graph – DAG ) C 3 – Tìm kiếm khoảng trống trạng thái Trò đố 8 ô hay 15 ô Trạng thái khởi đầu Trạng thái đích Trò đố 15 ô Trò đố 8 ô Cần màn biểu diễn KGTT cho bài toán này như thế nào ? C 3 – Tìm kiếm khoảng trống trạng thái KGTT của 8 – puzzle sinh ra bằng phép “ chuyển dời ô trống ” C 3 – Tìm kiếm khoảng trống trạng thái Có năng lực xảy ra vòng lặp không ? Một ví dụ của bài toán TSP Cần màn biểu diễn KGTT cho bài toán này như thế nào ? C 3 – Tìm kiếm khoảng trống trạng thái KGTT của bài toán TSP Mỗi cung được lưu lại bằng tổng giá của con đường từ nút mở màn đến nút hiện tại. C 3 – Tìm kiếm khoảng trống trạng thái Các Chiến Lược cho TK-KGTT TK hướng từ tài liệu ( Data-driven Search ) Suy diễn tiến ( forward chaining ) TK hướng từ tiềm năng ( Goal-driven Search ) Suy diễn lùi ( backward chaining ) C 3 – Tìm kiếm khoảng trống trạng thái TK Hướng từ Dữ Liệu Việc tìm kiếm đi từ tài liệu đến tiềm năng Thích hợp khi : Tất cả hoặc một phần tài liệu được cho từ đầu. Có nhiều tiềm năng, nhưng chỉ có 1 số ít ít những phép toán hoàn toàn có thể vận dụng cho một trạng thái bài toán. Rất khó đưa ra một tiềm năng hoặc giả thuyết ngay lúc đầu. C 3 – Tìm kiếm khoảng trống trạng thái TK Hướng Từ Mục Tiêu Việc tìm kiếm đi từ tiềm năng trở lại tài liệu. Thích hợp khi : Có thể đưa ra tiềm năng hoặc giả thuyết ngay lúc đầu. Có nhiều phép toán hoàn toàn có thể vận dụng trên 1 trạng thái của bài toán => sự bùng nổ số lượng những trạng thái. Các tài liệu của bài toán không được cho trước, nhưng mạng lưới hệ thống phải đạt được trong quy trình tìm kiếm. C 3 – Tìm kiếm khoảng trống trạng thái Các giải pháp tìm kiếm trên đồ thị KGTT : Phát triển từ giải thuật quay lui ( back – tracking ) : Tìm kiếm rộng ( breath-first search ) Tìm kiếm sâu ( depth-first search ) TK sâu bằng cách đào sâu nhiều lần ( depth-first search with iterative deepening ) C 3 – Tìm kiếm khoảng trống trạng thái Tìm Kiếm Rộng Open = [ A ] ; closed = [ ] Open = [ B, C, D ] ; closed = [ A ] Open = [ C, D, E, F ] ; closed = [ B, A ] Open = [ D, E, F, G, H ] ; closed = [ C, B, A ] Open = [ E, F, G, H, I, J ] ; closed = [ D, C, B, A ] Open = [ F, G, H, I, J, K, L ] ; closed = [ E, D, C, B, A ] Open = [ G, H, I, J, K, L, M ] ; ( vì L đã có trong open ) ; closed = [ F, E, D, C, B, A ] … C 3 – Tìm kiếm khoảng trống trạng thái Tìm kiếm Sâu Open = [ A ] ; closed = [ ] Open = [ B, C, D ] ; closed = [ A ] Open = [ E, F, C, D ] ; closed = [ B, A ] Open = [ K, L, F, C, D ] ; closed = [ E, B, A ] Open = [ S, L, F, C, D ] ; closed = [ K, E, B, A ] Open = [ L, F, C, D ] ; closed = [ S, K, E, B, A ] Open = [ T, F, C, D ] ; closed = [ L, S, K, E, B, A ] Open = [ F, C, D ] ; closed = [ T, L, S, K, E, B, A ] … C 3 – Tìm kiếm khoảng trống trạng thái Tìm Kiếm Sâu hay Rộng ? ( 1 ) Có thiết yếu tìm một đường đi ngắn nhất đến tiềm năng hay không ? Sự phân nhánh của khoảng trống trạng thái Tài nguyên về khoảng trống và thời hạn sẵn có Khoảng cách trung bình của đường dẫn đến trạng thái tiềm năng. Yêu cầu đưa ra tổng thể những giải thuật hay chỉ là lời giải tìm được tiên phong. C 3 – Tìm kiếm khoảng trống trạng thái Tìm kiếm sâu bằng cách đào sâu nhiều lần ( depth-first iterative deepening ) Độ sâu số lượng giới hạn ( depth bound ) : giải thuật TK sâu sẽ quay lui khi trạng thái đang xét đạt đến độ sâu số lượng giới hạn đã định. TK Sâu bằng cách đào sâu nhiều lần : TK sâu với độ sâu số lượng giới hạn là 1, nếu thất bại, nó sẽ lặp lại GT TK sâu với độ sâu là 2, … GT liên tục cho đến khi tìm được tiềm năng, mỗi lần lặp lại tăng độ sâu lên 1. GT này có độ phức tạp về thời hạn cùng bậc với TK Rộng và TK Sâu. C 3 – Tìm kiếm khoảng trống trạng thái Trò chơi ô đố 8 – puzzle The 8 – puzzle searched by a production system with loop detection and depth bound 5 C 3 – Tìm kiếm khoảng trống trạng thái Đồ thị Và / Hoặc Sử dụng KGTT để biễu diễn suy luận với phép tính vị từ Là phươ
Slide-chuong8.doc
