›
›

Cơ sở trí tuệ nhân tạo - Chương 2: Thuật toán, thuật giải một số phương pháp giải quyết vấn đề - Phạm Thi Vương

pdf 106 trang Gia Huy 17/05/2022 2100
Download
Bạn đang xem 20 trang mẫu của tài liệu "Cơ sở trí tuệ nhân tạo - Chương 2: Thuật toán, thuật giải một số phương pháp giải quyết vấn đề - Phạm Thi Vương", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfco_so_tri_tue_nhan_tao_chuong_2_thuat_toan_thuat_giai_mot_so.pdf

Nội dung text: Cơ sở trí tuệ nhân tạo - Chương 2: Thuật toán, thuật giải một số phương pháp giải quyết vấn đề - Phạm Thi Vương

  1. THUẬT TOÁN, THUẬT GIẢI MỘT SỐ PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
  2. Nội dung • Vấn đề, giải quyết vấn đề • Khái niệm về thuật toán, thuật giải • Các nguyên lý của thuật giải heuristic • Các chiến lược tìm kiếm vàThuật giải A* 06/10/2009 Nhập môn Trí tuệ nhân tạo 2
  3. Vấn đề? Những vướng mắc khó khăn cần giải quyết Một yêu cầu tìm kiếm xử lý trong một ngữ cảnh cụ thể Bao gồm: - các sự kiện - các thông tin - những ràng buộc nhất định. vấn đề = bài toán 06/10/2009 Nhập môn Trí tuệ nhân tạo 3
  4. Mô hình vấn đề A B A: giả thiết, điều kiện ban đầu B: kết luận cần đạt đến : suy luận hay giải pháp cần xác định = một số hữu hạn bước 06/10/2009 Nhập môn Trí tuệ nhân tạo 4
  5. Phân loại vấn đề • Xác định rõ - A, B đều rõ • Chưa rõ - A rõ, B chưa rõ - A chưa rõ, B rõ - A, B đều chưa rõ 06/10/2009 Nhập môn Trí tuệ nhân tạo 5
  6. Thuật toán • Thuật toán là giải pháp viết dưới dạng thủ tục và thỏa 3 tiêu chuẩn Xác định : không mập mờ và có thể thực thi được Hữu hạn Đúng Thuật toán là một dãy hữu hạn các bướckhông mập mờ và có thể thực thi được, quá trình hành động theo các bước này phải dừng và cho kết quả mong muốn. 06/10/2009 Nhập môn Trí tuệ nhân tạo 6
  7. Thuật toán • Tính tổng các số nguyên dương lẻ từ 1 n – B1: S=0; – B2: i=1 – B3: Nếu i=n+1i>n thì sang bước 7, ngược lại sang bước 4 – B4: S=S+i – B5: i=i+2 – B6: Quay lại 3 – B7: Tổng cần tìm là S 06/10/2009 Nhập môn Trí tuệ nhân tạo 7
  8. Thuật toán Thuật toán có thể được thể hiện qua: Ngôn ngữ tự nhiên Lưu đồ Mã giả NN lập trình Ngoài ra thuật toán còn phải đạt hiệu quả cao hay có độ phức tạp thấp 06/10/2009 Nhập môn Trí tuệ nhân tạo 8
  9. Thuật toán O(log n)  2 O(n) O(nlog2 n) ®é phøc t¹p ®a thøc chÊp nhËn ®­îc 2 O(n ) k On()  O(2n )  ®é phøc t¹p cao khã chÊp nhËn n!  06/10/2009 Nhập môn Trí tuệ nhân tạo 9
  10. Một số ví dụ về bài toán có độ phức tạp cao • Bài toán phân công công việc Một đề án gồm n công việc và các việc sẽ đưọc thực hiên bởi m máy như nhau. Giả sử biết thời gian để 1 máy thực hiện viêc thứ j là tj Yêu cầu: Tìm phương án phân công sao cho thời gian hoàn thành toàn bộ công việc là thấp nhất. Mẫu số liệu n=10, m=3 tj = 4 9 5 2 7 6 10 8 7 5 06/10/2009 Nhập môn Trí tuệ nhân tạo 10
  11. Một số ví dụ về bài toán có độ phức tạp cao • Bài toán tô màu Giả sử ta có bản đồ các 9 quốc gia trên thế giới, ta 1 6 muốn tô màu các quốc gia này sao cho các nước khác nhau được tô khác 0 2 5 7 màu. 8 3 Yêu cầu tìm cách tô sao 4 cho số màu sử dụng là ít nhất. 06/10/2009 Nhập môn Trí tuệ nhân tạo 11
  12. 06/10/2009 Nhập môn Trí tuệ nhân tạo 12
  13. Một số ví dụ về bài toán có độ phức tạp cao Bài toán người đưa thư • Giả sử có một đồ thị có trọng số dương, tìm đường đi ngắn nhất qua tất cả các đỉnh của đồ thị rồi trở về đỉnh ban đầu A 5 1 E 3 B 2 7 3 2 4 4 06/10/2009 Nhập môn Trí tuệ nhân tạoD 1 C 13
  14. Thuật giải • Thuật giải: giải pháp được viết dưới dạng thủ tục tương tự như thuật toán nhưng không đòi hỏi các tiêu chuẩn như thuật toán. Tính đúng: chấp nhận các thuật giải đơn giản có thể cho kết quả đúng hay gần đúng nhưng có khả năng thành công cao hơn. 06/10/2009 Nhập môn Trí tuệ nhân tạo 14
  15. Thuật giải heuristic Để có thể được chấp nhận thuật giải phải thể hiện một giải pháp hợp lý nhất có thể trong tình huống hiện tại bằng cách: Tận dụng mọi thông tin hữu ích Sử dụng tri thức, kinh nghiệm trực giác của con người Tự nhiên đơn giản nhưng cho kết quả chấp nhận được Thuật giải Heuristic 06/10/2009 Nhập môn Trí tuệ nhân tạo 15
  16. Thuật giải heuristic Đặc tính • Thường tìm được lời giải tốt, mặc dù không phải là tốt nhất • Thực hiện dễ dàng nhanh chóng so với thuật giải tối ưu • Khá tự nhiên gần gũi với cách giải của con người 06/10/2009 Nhập môn Trí tuệ nhân tạo 16
  17. Các nguyên lý của thuật giải heuristic • Vét cạn thông minh • Nguyên lý thứ tự • Nguyên lý tham lam • Hàm heuristic 06/10/2009 Nhập môn Trí tuệ nhân tạo 17
  18. Các nguyên lý của thuật giải heuristic Vét cạn thông minh Hạn chế vùng không gian tìm kiếm và có sự định hướng để nhanh chóng tìm đến mục tiêu. Tạo miền D’ rất nhỏ so với D Vét cạn trên D’ 06/10/2009 Nhập môn Trí tuệ nhân tạo 18
  19. Các nguyên lý của thuật giải heuristic • Nguyên lý thứ tự Trong quá trình hành đông để thực hiện việc chọn lọc các cách làm các trạng thái ta có thể dựa trên một thứ tự hợp lý để giải pháp đạt tính hiệu quả cao 06/10/2009 Nhập môn Trí tuệ nhân tạo 19
  20. Các nguyên lý của thuật giải heuristic • Nguyên lý tham lam Trong nhiều vấn đề cần phải đạt đến một 1 mục tiêu tối ưu toàn cục mà không nhìn thấy được toàn bộ quá trình hành động, hơn nữa trong từng bước ta phải lựa chọn hành động dựa trên những thông tin cục bộ. Khi đó trong từng bước của quá trình hành động người ta dựa trên mục tiêu tối ưu toàn cục để định ra mục tiêu cục bộ và dựa theo đó chọn lựa hành động 06/10/2009 Nhập môn Trí tuệ nhân tạo 20
  21. Các nguyên lý của thuật giải heuristic • Hàm heuristic Là hàm ứng với mỗi trạng thái hay mỗi sự chọn lựa một giá trị có ý nghĩa đối với vấn đề để dựa vào giá trị hàm này ta chọn lựa hành động. 06/10/2009 Nhập môn Trí tuệ nhân tạo 21
  22. Ví dụ 1 • Giải xấp xỉ nghiệm của phương trình f(x)=0 liên tục trên [a,b] với f(a)f(b)<0. • Với điều kiện f(a)f(b)<0 và f liên tục trên a,b ta biết f(x) có nghiệm thuộc [a,b]. phương pháp vét cạn như sau: – Gọi c là trung điểm của [a,b] – Nếu f(a)f(c)<0 thì b=c, ngược lại a=c 06/10/2009 Nhập môn Trí tuệ nhân tạo 22
  23. Ví dụ 2 Thuật giải cho bài toán phân công đơn giản Chọn việc J chưa phân công có thời gian thực hiện cao nhất phân công cho máy có thời gian làm việc thấp nhất for(k=0;k<n;k++) { Chọn việc J chưa phân công có thời gian thực hiện cao nhất. Chọn máy M có thời gian làm việc thấp nhất Bố trí việc J cho máy M. } 06/10/2009 Nhập môn Trí tuệ nhân tạo 23
  24. Ví dụ 2 n=10, m=3 tj = 4 9 5 2 7 6 10 8 7 5 2 máy, 5 công việc (3,3,2,2,2) 06/10/2009 Nhập môn Trí tuệ nhân tạo 24
  25. Ví dụ 3 • Bài toán tô màu – QT1: Chọn đỉnh có số đỉnh chưa tô ở cạnh nó là lớn nhất (bậc lớn nhất) – QT2: Chọn màu:Với một đỉnh N đang xét, trước tiên thử tô bằng những màu đã tô, nếu không được thì sử dụng màu mới – Sau khi tô màu cho đỉnh N thì ta xóa các cạnh có nối đến N và đánh dấu các đỉnh kế bên không được tô màu vừa tô cho N 06/10/2009 Nhập môn Trí tuệ nhân tạo 25
  26. 9 1 6 0 2 5 7 8 3 06/10/2009 Nhập môn Trí tuệ nhân tạo4 26
  27. Ví dụ 3 • Có một cuộc hội thảo khoa học với 9 chủ đề khác nhau: A, B, C • Các chủ đề sau không được đồng thời; AE, BC, ED, ABD, AHI, BHI, DFI, DHI, FGH. • Xây dựng lịch sao cho số buổi tổ chức là ít nhất 06/10/2009 Nhập môn Trí tuệ nhân tạo 27
  28. Ví dụ 4 Bài toán người đưa thư A • thuật giải GST(Greedy 5 1 Traveling Saleman): Ở mỗi bước chọn cạnh E 3 B 2 ngắn nhất tiếp theo để 7 đi 3 2 4 4 Tạo ra lịch từ p thành phố xuất phát riêng biệt. Tìm p chu trình qua n thành phố D 1 C Chỉ chu trình tốt nhất trong p chu trình được giữ lại. 06/10/2009 Nhập môn Trí tuệ nhân tạo 28
  29. Ví dụ 5 • Có 1 trạm cấp nước và N điểm dân cư. Hãy xây dựng chương trình thiết kế tuyến đường ống nước cung cấp đến mọi nhà sao cho tổng chiều dài đường ống phải dùng là ít nhất. Giả sử rằng các đường ống chỉ được nối giữa 2 điểm dân cư hoặc giữa trạm cấp nước với điểm dân cư. 06/10/2009 Nhập môn Trí tuệ nhân tạo 29
  30. Ví dụ 5 1 6 3 7 5 1 2 8 5 4 4 2 6 2 3 06/10/2009 Nhập môn Trí tuệ nhân tạo 30
  31. Ví dụ 5 • Sắp xếp các cạnh theo thứ tự tăng của trọng số • for(i=0;i<n;i++) lấy cạnh ej nhỏ nhất thêm vào T sao cho T không có chu trình • Kết thúc ta có T là cây khung nhỏ nhất 06/10/2009 Nhập môn Trí tuệ nhân tạo 31
  32. Bài toán tìm kiếm Vấn đề = Tìm kiếm mục tiêu 06/10/2009 Nhập môn Trí tuệ nhân tạo 32
  33. Không gian trạng thái • Không gian trạng thái: tập tất cả các trạng thái có thể có của bài toán. 06/10/2009 Nhập môn Trí tuệ nhân tạo 33
  34. Các ví dụ 2 8 3 1 2 3 1 6 4 8 4 7 5 7 6 5 06/10/2009 Nhập môn Trí tuệ nhân tạo 34
  35. 06/10/2009 Nhập môn Trí tuệ nhân tạo 35
  36. • Bài toán đổ nước • Bài toán người quỷ qua sông 06/10/2009 Nhập môn Trí tuệ nhân tạo 36
  37. Không gian trạng thái • Giữa các trạng thái có sự liên hệ gọi là chuyển trạng thái hay toán tử chuyển trạng thái. 06/10/2009 Nhập môn Trí tuệ nhân tạo 37
  38. Ví dụ 2 8 3 1 2 3 1 6 4 8 4 7 5 7 6 5 • Trạng thái đầu và cuối của bài toán 8 số • Các toán tử: qua trái, phải, lên trên, xuống dưới 06/10/2009 Nhập môn Trí tuệ nhân tạo 38
  39. • Biểu diễn trạng thái bằng (a, b, k) Với a, b là số người và quỷ ở bên bờ phải k=1 là thuyền ở bờ phải, k=0 thuyền ở bờ trái Không gian trạng thái Trạng thái ban đầu (3, 3, 1) Các toán tử: chở 1 người, 1 quỷ, 2 người, 2 quỷ, 1người và 1 quỷ Trạng thái kết thúc (0, 0, 0) 06/10/2009 Nhập môn Trí tuệ nhân tạo 39
  40. 3, 3, 1 3, 2, 0 3, 1, 0 2, 2, 0 06/10/2009 Nhập môn Trí tuệ nhân tạo 40
  41. Không gian trạng thái • Không gian trạng thái này có thể được biểu biễn bằng đồ thị • Đồ thị trang thái xác định khi: – Biết trạng thái đầu – Biết hàm next(S)(tập hợp toán tử) trả về các trạng thái kế của S. – Biết trạng thái kết thúc (tập trạng thái kết thúc) 06/10/2009 Nhập môn Trí tuệ nhân tạo 41
  42. Cây tìm kiếm A D B C I F E G K 06/10/2009 Nhập môn Trí tuệ nhân tạo 42
  43. Cây tìm kiếm A B C D I G E F C F G G K K 06/10/2009 Nhập môn Trí tuệ nhân tạo 43
  44. Phát biểu bài toán • Trên một đồ thị có trọng số dương ta muốn tìm đường đi ngắn nhất từ một đỉnh xuất phát S0 đến một đỉnh mục tiêu G. Giả sử ta có thêm thông tin như sau: tại mỗi đỉnh S ta biết ước tính quãng đường từ S đến mục tiêu là h(S). 06/10/2009 Nhập môn Trí tuệ nhân tạo 44
  45. Các đặc điểm của bài toán(vấn đề) • Khả năng phân rã ? • Khả năng lờ đi và quay lui. • Khả năng dự đoán toàn cục. • Mục tiêu là trạng thái hay con đường. • Lượng tri thức cần để giải bài toán. • Có cần sự can thiệp của con người trong quá trình giải không? 06/10/2009 Nhập môn Trí tuệ nhân tạo 45
  46. Khả năng phân rã x2 + 3x + sin 2 x.cos 2 x dx x2 dx 3x dx sin22 x.cos x dx (1 - cos22x )cos xdx cos2 xdx cos4 xdx 06/10/2009 Nhập môn Trí tuệ nhân tạo 46
  47. Khả năng lờ đi và quay lui – Có thể lờ đi : như BT chứng minh định lý. • Vì: định lý vẫn đúng sau một vài bước áp dụng các luật. – Có thể quay lui: như BT 8-puzzle. • Vì: có thể di chuyển theo hướng ngược lại để về TT trước. – Không thể quay lui: như BT chơi cờ. • Vì: game over! 06/10/2009 Nhập môn Trí tuệ nhân tạo 47
  48. Khả năng dự đoán của bài toán: – Có thể dự đoán được: như BT 8 puzzle. • có thể đề ra 1 chuổi nước đi và tự tin vào kết qua sẽ xãy ra. – Không thể dự đoán được: như các game có đối kháng. • Cần theo đuổi nhiều kế hoạch. • Có chiến lược/đánh giá để chọn kế hoạch tốt. 06/10/2009 Nhập môn Trí tuệ nhân tạo 48
  49. Lời giải là trạng thái hay con đường: 06/10/2009 Nhập môn Trí tuệ nhân tạo 49
  50. Vai trò của tri thức là gì? – Cần ít tri thức: • Như bài toán: “chơi cờ”. • Tri thức = luật để di chuyển hợp lệ, cơ chế điều khiển, chiến lược điều khiển để tăng tốc tìm kiếm. – Cần nhiều tri thức: • Như bài toán: Hiểu câu chuyện trên tạp chí. • Tri thức: nhiều, cả những cái đã ghi tường minh và cả những cái không được ghi trong chính câu chuyện. 06/10/2009 Nhập môn Trí tuệ nhân tạo 50
  51. Công việc có cần tương tác với con người? – Không cần tương tác: CT nhận mô tả bài toán, sinh ra lời giải mà không cần sự tương tác với con người trong quá trình giải để nhận thêm thông tin hay để giải thích các bước. • Như BT: chứng minh định lý (với yêu cầu đơn giản là vào đlý– ra là lời giải). – Cần tương tác: CT cần tương tác với con người để nhận thêm thông tin, để giải thích, để nhận được hướng dẫn cần thiết. • Như BT: xây dựng các hệ chuẩn đoán bệnh. – Sự phân biệt này cũng có tính tương đối. Như việc chứng minh đlý nói trên, đôi lúc CT cũng được yêu cầu để giải thích từng bước chứng minh hay đôi cũng cần phải nhận hướng dẫn để bắt đầu từ điềm nào. – Xác định được CT có cần tương tác hay không sẽ giúp chọn ra phương pháp giải thích hợp. 06/10/2009 Nhập môn Trí tuệ nhân tạo 51
  52. Các vấn đề trong thiết kế các CT tìm kiếm • Xác định hướng tìm (forward hay backward reasoning). • Cách lựa chọn luật để áp dụng (matching) • Cách biểu diễn NODE của quá trình tìm (knowledge representation problem, frame problem). • Các NODE trong đồ thị có thể được phát sinh nhiều lần, và có thể đã được xem xét trước đó trong quá trình duyệt cần loại bỏ những NODE lặp lại. cần lưu lại các NODE đã xét. 06/10/2009 Nhập môn Trí tuệ nhân tạo 52
  53. Lý thuyết đồ thị - Review • Đồ thị: là một cấu trúc bao gồm: – Tập các nút N1, N2, Nn, Không hạn chế – Tập các cung nối các cặp nút, có thể có nhiều cung trên một cặp nút A B A B C E D D C Nút: {A,B,C,D,E} E Cung: {(a,d), (a,b), (a,c), (b,c), (c,d), (c,e), 06/10/2009(d,e) } Nhập môn Trí tuệ nhân tạo 53
  54. Đặc tính đồ thị • Đồ thị có hướng: là đồ thị với các cung có định hướng, nghĩa là cặp nút có quan hệ thứ tự trước sau theo từng cung. Cung (Ni,Nj) có hướng từ Ni đến Nj, Khi đó Ni là nút cha và Nj là nút con. • Nút lá: là nút không có nút con. • Path: là chuổi có thứ tự các nút mà 2 nút kế tiếp nhau tồn tại một cung. 06/10/2009 Nhập môn Trí tuệ nhân tạo 54
  55. Đặc tính đồ thị • Đồ thị có gốc: Trên đồ thị tồn tại nút X sao cho tất cả các path đều đi qua nút đó. X là gốc - Root • Vòng : là một path đi qua nút nhiều hơn một lần • Cây: là graph mà không có path vòng • Hai nút nối nhau :nếu có một path đi qua 2 nút đó 06/10/2009 Nhập môn Trí tuệ nhân tạo 55
  56. Các chiến lược tìm kiếm • Tìm kiếm mù • Tìm kiếm tốt nhất • Tìm kiếm heuristic Mục tiêu: tìm ra một solution path và/hay solution path tốt nhất 06/10/2009 Nhập môn Trí tuệ nhân tạo 56
  57. Tìm kiếm mù • Tìm kiếm theo chiều sâu • Tìm kiếm theo chiều rộng • Tìm kiếm sâu dần 06/10/2009 Nhập môn Trí tuệ nhân tạo 57
  58. • O = {S}; C={}; • While O khác rỗng • { Lấy p trong O Duyệt p Bỏ p vào C Với mỗi q kề p, q không thuộc C: bỏ q vào O • } 06/10/2009 Nhập môn Trí tuệ nhân tạo 58
  59. Tìm kiếm theo chiều sâu • Tìm kiếm sâu trong không gian bài toán được bắt đầu từ một nút rồi tiếp tục cho đến khi hoặc đến ngõ cụt hoặc đến đích • Tại mỗi nút có luật trọng tài 06/10/2009 Nhập môn Trí tuệ nhân tạo 59
  60. Tìm kiếm theo chiều sâu • O = {S}; C={}; • While O khác rỗng • { Lấy p từ đầu O Duyệt p Bỏ p vào C Với mỗi q kề p, q không thuộc C: bỏ q vào đầu O • } 06/10/2009 Nhập môn Trí tuệ nhân tạo 60
  61. A D B C I F E G K 06/10/2009 Nhập môn Trí tuệ nhân tạo 61
  62. A B C D I G E F C F G G K K 06/10/2009 Nhập môn Trí tuệ nhân tạo 62
  63. Tìm kiếm theo chiều rộng • Tìm kiếm trên tất cả các nút của một mức trong không gian bài toán trước khi chuyển sang các nút của mức tiếp theo 06/10/2009 Nhập môn Trí tuệ nhân tạo 63
  64. Tìm kiếm theo chiều rộng • O = [S]; C={}; • While O khác rỗng • { Lấy p từ đầu O Duyệt p Bỏ p vào C Với mỗi q kề p, q không thuộc C: bỏ q vào cuối O • } 06/10/2009 Nhập môn Trí tuệ nhân tạo 64
  65. A D B C I F E G K 06/10/2009 Nhập môn Trí tuệ nhân tạo 65
  66. A B C D I G E F C F G G K K 06/10/2009 Nhập môn Trí tuệ nhân tạo 66
  67. • Bài tập 3. Đại dương được xem như là một mặt phẳng toạ độ trên đó có n hòn đảo với toạ độ lần lượt là (x1, y1), (x2, y2), , (xn, yn). Một chiếc ca nô xuất phát từ đảo d1 muốn tuần tra đến đảo d2. bình xăng của ca nô chỉ chứa đủ xăng để đi được một quãng đường dài không quá m (km). Trên đường đi ca nô có thể ghé một số đảo nào đó để tiếp thêm xăng, lúc này ca nô được tiếp thêm xăng đầy bình chứa. Hãy chỉ ra một đường đi từ đảo d1 đến đảo d2 sao cho số lần ghé đảo trung gian để tiếp thêm xăng là ít nhất. 06/10/2009 Nhập môn Trí tuệ nhân tạo 67
  68. Tìm kiếm sâu dần • Kỹ thuật tìm kiếm sâu dần là thực hiện việc tìm kiếm với độ sâu ở mức giới hạn d nào đó. Nếu không tìm ra nghiệm ta tăng độ sâu lên d+1 và lại tìm kiếm theo độ sâu tới mức d+1. Quá trình trên được lặp lại với d lần lượt là 1, 2, đến độ sâu max nào đó 06/10/2009 Nhập môn Trí tuệ nhân tạo 68
  69. Tìm kiếm tốt nhất • Dùng tri thức về bài toán để hướng dẫn • Tại mỗi nút được xem xét: tìm kiếm tiếp tục theo nhánh nào tin tưởng sẽ dẫn đến lời giải. 06/10/2009 Nhập môn Trí tuệ nhân tạo 69
  70. Tìm kiếm đường đi có giá thành cực tiểu Thuật toán AT (1) Mỗi đỉnh tương ứng với 1 số g(n): giá thành đi từ đỉnh ban đầu tới n C : đỉnh đóng O : đỉnh mở Bước 1: O= {S} C={} g(S)=0 Bước 2: While (O≠{}) 2.1 Chọn N thuộc O có g(N) nhỏ nhất N: mục tiêu dừng, thông báo kết quả Nếu không tồn tại N dừng 2.2 Chuyển N qua C, và mở các Q sau N g(Q) = g(N)+cost(N,Q) Bước 3: Không có kết quả. 06/10/2009 Nhập môn Trí tuệ nhân tạo 70
  71. 1 2 2 2 1 2 4 3 0 3 4 4 7 3 1 7 6 5 5 6 06/10/2009 Nhập môn Trí tuệ nhân tạo 71
  72. 2 4 4 7 2 5 5 1 1 5 1 5 3 3 7 6 06/10/2009 Nhập môn Trí tuệ nhân tạo 72
  73. Tìm kiếm đường đi có giá thành cực tiểu Thuật toán AT (2) Mỗi đỉnh tương ứng với 1 số g(n): giá thành đi từ đỉnh ban đầu tới n C : đỉnh đóng O : đỉnh mở Bước 1: O= {S} C={} g(S)=0 Bước 2: While (O≠{}) 2.1 Chọn N thuộc O có g(N) nhỏ nhất N: mục tiêu dừng, thông báo kết quả Nếu không tồn tại N dừng 2.2 Chuyển N qua C, và mở cácQ sau N g(Q) = g(N)+cost(N,Q) Bước 3: Không có kết quả. 06/10/2009 Nhập môn Trí tuệ nhân tạo 73
  74. Tìm kiếm đường đi có giá thành cực tiểu Thuật toán AT (3) Mỗi đỉnh tương ứng với 1 số g(n): giá thành đi từ đỉnh ban đầu tới n C : đỉnh đóng O : đỉnh mở Bước 1: O= {S} C={} g(S)=0 Bước 2: While (O≠{}) 2.1 Chọn N thuộc O có g(N) nhỏ nhất N: mục tiêu dừng, thông báo kết quả Nếu không tồn tại N dừng 2.2 Chuyển N qua C, và mở các Q sau N Bước 3: Không có kết quả. 06/10/2009 Nhập môn Trí tuệ nhân tạo 74
  75. Tìm kiếm đường đi có giá thành cực tiểu Thuật toán AT (3) • 2.2 Chuyển N qua C, và mở các Q sau N 2.2.1 Nếu Q đã có trong O nếu g(Q)> g(N)+cost(N,Q) g(Q) = g(N)+cost(N,Q) prev(Q)=N 2.2.2 Nếu Q chưa có trong O g(Q) = g(N)+cost(N,Q) prev(Q)=N 06/10/2009 Nhập môn Trí tuệ nhân tạo 75
  76. Thuật toán AKT Mỗi đỉnh tương ứng với 1 số g(n): giá thành đi từ đỉnh ban đầu tới n C : đỉnh đóng O : đỉnh mở Bước 1: O= {S} C={} g(S)=0, f(S) = h(S) Bước 2: While (O≠{}) 2.1 Chọn N thuộc O có f(N) nhỏ nhất N: mục tiêu dừng, thông báo kết quả Nếu không tồn tại N dừng 2.2 Chuyển N qua C, và mở các Q sau N g(Q) = g(N)+cost(N,Q); f(Q)=g(Q)+h(Q); Bước 3: Không có kết quả. 06/10/2009 Nhập môn Trí tuệ nhân tạo 76
  77. Tìm kiếm cực tiểu sử dụng hàm đánh giá - Thuật toán A* Cụ thể trong quá trình lựa chọn đỉnh để duyệt xét các đỉnh kế tiếp thì thuật giải A* dựa vào giá trị sau: f(N) = g(N) + h(N) với g(N) số đo lộ trình từ S tới N f(N) ước tính độ dài từ S đến N 06/10/2009 Nhập môn Trí tuệ nhân tạo 77
  78. Tìm kiếm cực tiểu sử dụng hàm đánh giá - Thuật toán A* Bước 1: C = {}; O = {S}; g(S) = 0; f(S) = h(S); 06/10/2009 Nhập môn Trí tuệ nhân tạo 78
  79. Tìm kiếm cực tiểu sử dụng hàm đánh giá - Thuật toán A* Bước 2: while(O≠{}) { 2.1 Chọn N O có f(N) nhỏ nhất 2.2 Lấy N từ O cho vào C 2.3 if(NG) Dừng. Kết luận: tìm được 06/10/2009 Nhập môn Trí tuệ nhân tạo 79
  80. Tìm kiếm cực tiểu sử dụng hàm đánh giá - Thuật toán A* 2.4 Xét các đỉnh kế S của N TH1: S O và S C if(g(S)>g(N)+w(N,S)) g(S)= g(N)+w(N,S); f(S)=g(S)+h(S); prev(S)=N TH2: S O và S C g(S)= g(N)+w(N,S); f(S)=g(S)+h(S); prev(S)=N } Bước 3: Kết luận 06/10/2009 Nhập môn Trí tuệ nhân tạo 80
  81. A* - Ví dụ 2 8 3 1 2 3 1 6 4 8 4 7 5 7 6 5 • Trạng thái đầu và cuối của bài toán 8 số • Các toán tử: qua trái, phải, lên trên, xuống dưới h(Si) = số nút sai của Si so với G 06/10/2009 Nhập môn Trí tuệ nhân tạo 81
  82. 06/10/2009 Nhập môn Trí tuệ nhân tạo 82
  83. Puzzle – Cài đặt #define UP 1 #define DN 2 #define LT 3 #define RT 4 #define NO 0 06/10/2009 Nhập môn Trí tuệ nhân tạo 83
  84. Puzzle – Cài đặt typedef char TAB[3][3]; struct info{ TAB S; unsigned g,h,f; int d; }; 06/10/2009 Nhập môn Trí tuệ nhân tạo 84
  85. Puzzle – Cài đặt define SIZE 500 typedef struct List{ int n; info e[SIZE]; List(){n=0;} void them(info X); info timfnho(); void xuatlist(); int vitri(info X) }; 06/10/2009 Nhập môn Trí tuệ nhân tạo 85
  86. Puzzle – Cài đặt List O,C,KQ; TAB S0, G; void main() { nhap(); if(Astart()) { timkq(); KQ.xuatlist(); } } 06/10/2009 Nhập môn Trí tuệ nhân tạo 86
  87. Puzzle – Cài đặt void nhap(); unsigned count(TAB S); //h int sobang(TAB S1, TAB S2); void ganbang(TAB S1, TAB S2); //gán S2 cho S1 void timotrong(TAB S, int &k, int &l) void bangke(TAB N, int d, TAB S,int k, int l) //S là bảng kề của N int Astart(); void xulyke(info X, int d, TAB S); void xuat(TAB S); void timkq(); 06/10/2009 Nhập môn Trí tuệ nhân tạo 87
  88. Puzzle – Cài đặt int Astart() { info X; ganbang(X.S,S0); X.g=0; X.h=count(S0); X.f=X.h; X.d=NO; O.them(X); while(O.n>0) { X=O.timfnho(); C.them(X); 06/10/2009 Nhập môn Trí tuệ nhân tạo 88
  89. Puzzle – Cài đặt while(O.n>0) { X=O.timfnho(); C.them(X); if(sobang(X.S,G)) return 1; timotrong(X.S, k, l); if(k>0) { d=UP; bangke(X.S,d,BK,k,l); xulyke(X,d,BK); } 06/10/2009 Nhập môn Trí tuệ nhân tạo 89
  90. Puzzle – Cài đặt if(k 0){ } if(l<2){ } } return 0; } 06/10/2009 Nhập môn Trí tuệ nhân tạo 90
  91. Puzzle – Cài đặt void xulyke(info X, int d, TAB S) { info Y; int k; if(C.vitri(S)==-1) return; if(k=O.vitri(S)==-1) { ganbang(Y.S,S); Y.g=X.g+1; Y.h=count(S); Y.f=Y.g+Y.h; Y.d=d; O.them(Y); } 06/10/2009 Nhập môn Trí tuệ nhân tạo 91
  92. Puzzle – Cài đặt } else if(X.g+1<O.e[k].g) { O.e[k].g=X.g+1; O.e[k].f= O.e[k].g+ O.e[k].h; O.e[k].d=d; } } 06/10/2009 Nhập môn Trí tuệ nhân tạo 92
  93. Chiến lược minimax • Giải thuật tìm kiếm Heuristic với các hàm heuristic chỉ thích hợp cho các bài toán không có tính đối kháng. Như các trò chơi chỉ có một người chơi: Puzzle, tìm lối ra mê cung, bài toán n quân hậu, • Các trò chơi có tính đối kháng cao, thường là các trò chơi 2 người chơi như: tic tac toe, caro, cờ quốc tế, giải thuật trên không có tác dụng vì: Đối phương không bao giờ đi theo con đường cho ta có thể đi đến goal 06/10/2009 Nhập môn Trí tuệ nhân tạo 93
  94. Chiến lược minimax • Cần phải có một giải thuật khác phù hợp hơn. Chiến lược MINIMAX • Chiến lược Minimax (được thể hiện bằng giải thuật minimax) dựa trên 2 giả thiết sau: – Cả 2 đối thủ có cùng kiến thức như nhau về không gian trạng thái của trò chơi – Cả 2 đối thủ có cùng mức cố gắng thắng như nhau 06/10/2009 Nhập môn Trí tuệ nhân tạo 94
  95. Giải thuật minimax Hai đối thủ trong trò chơi có tên là MAX và MIN – Max: biểu diễn cho mục đích của đối thủ này là làm lớn tối đa lợi thế của mình – Min: biểu diễn cho mục đích của đối thủ này là làm nhỏ tối đa lợi thế của đối phương. Trên cây tìm kiếm sẽ phân lớp thành các lớp Max và Min. 06/10/2009 Nhập môn Trí tuệ nhân tạo 95
  96. Giải thuật minimax Với một node n bất kỳ, – Nếu nó thuộc lớp Max thì gán cho nó giá trị Max của các node con – Nếu nó thuộc lớp Min thì gán cho nó giá trị nhỏ nhất của các node con. 06/10/2009 Nhập môn Trí tuệ nhân tạo 96
  97. Minimax – Ví dụ Maximizing ply A -2 Player Minimizing ply B -6 C -2 D -4 Opponent E F G H I J K 9 -6 0 0 -2 -4 -3 06/10/2009 Nhập môn Trí tuệ nhân tạo 97
  98. Giải thuật minimax – ví dụ • Bài toán que diêm Một tập que diêm ban đầu đặt giữa 2 người chơi. Lần lượt đi xen kẽ. Người đến lượt đi phải chia nhóm que diêm theo nguyên tắc: – Chọn nhóm bất kỳ có số que >2 – Chia thành 2 nhóm có số que khác nhau Goal: người nào đến lượt mà không chia được là thua. 06/10/2009 Nhập môn Trí tuệ nhân tạo 98
  99. Giải thuật minimax – ví dụ • Không gian trạng thái của trò chơi được phát triển toàn bộ, các node lá được gán giá trị 1 nếu là MAX thắng và 0 nếu là MIN thắng. • Với một node bất kỳ nếu thuộc lớp MAX gán cho nó giá trị lớn nhất của các node con. Nếu thuộc lớp MIN gán cho nó giá trị nhỏ nhất của các node con. 06/10/2009 Nhập môn Trí tuệ nhân tạo 99
  100. Minimax – bài toán que diêm MIN 7 0 0 1 0 MAX 6-1 5-2 4-3 0 0 1 0 MIN 5-1-1 4-2-1 3-2-2 3-3-1 1 0 1 MAX 4-1-1-1 3-2-1-1 2-2-2-1 1 0 MIN 3-1-1-1-1 2-2-1-1-1 1 MAX 2-1-1-1-1-1 06/10/2009 Nhập môn Trí tuệ nhân tạo 100
  101. Minimax với độ sâu giới hạn • Minimax như đã xét buộc phải có toàn bộ không gian trạng thái đã được triển khai để có thể gán trị cho các nút lá và tính ngược lại Không khả thi với các bài toán lớn vì không gian trạng thái là quá lớn. Giới hạn không gian trạng thái lại theo một độ sâu nào đó và giới hạn các node con theo một qui tắc nào đó. • Đây là chiến lược thông thường của các người chơi cờ: khả năng tính trước bao nhiêu nước. 06/10/2009 Nhập môn Trí tuệ nhân tạo 101
  102. Minimax với độ sâu giới hạn • Khi đó ta chỉ triển khai các nút con đến độ sâu giới hạn. • Đánh giá cho các nút này như là nút lá bằng một hàm lượng giá Heuristic. • áp dụng chiến lược minimax cho việc đánh giá các nút cấp trên. • Kỹ thuật này gọi là nhìn trước K bước với K là độ sâu giới hạn. 06/10/2009 Nhập môn Trí tuệ nhân tạo 102
  103. Ví dụ: Bài toán Tic Tac Toa X O • Hàm lượng giá heuristic h(n) = X(n) – O(n) với – X(n) số khả năng thắng của quân X. – O(n) số khả năng thắng của quân O 06/10/2009 Nhập môn Trí tuệ nhân tạo 103
  104. Ví dụ: Bài toán Tic Tac Toa X có 6 khả năng thắng X X O E(n) = 6 - 5 = 1 O có 5 khả năng thắng O X O Với hàm Heuristic trên X sẽ cố làm cho E(n) lớn nhất (MAX) và O làm cho E(n) nhỏ nhất (MIN) 06/10/2009 Nhập môn Trí tuệ nhân tạo 104
  105. Ví dụ: Bài toán 1Tic Tac Toa MAX X -1 1 -2 MI X X N 1 2 MAX X X X 1 X 0 X 1 X 0 X -1 O O O O O 06/10/2009 Nhập môn Trí tuệ nhân tạo 105
  106. Các đồ án • Mở rộng bài toán phân công • Thuật giải minmax, alpha – beta: trò chơi đối kháng • Tối ưu hoá hệ luật dẫn • Thuật giải di truyền • Mạng noron • SVM • Mô hình Markov ẩn • Điều khiển mờ, Logic mờ • Data mining • Web Mining • Agent • Các bài toán nhận dạng: âm thanh, hình ảnh • Ontology, xây dựng ontology về 1 lĩnh vực • Xây dựng chương trình giải toán, tra cứu kiến thức 06/10/2009• Nhập môn Trí tuệ nhân tạo 106