intTypePromotion=3

Bài giảng Trí tuệ nhân tạo - Chương 2: Biểu diễn bài toán & tìm lời giải

Chia sẻ: Đinh Gấu | Ngày: | Loại File: PDF | Số trang:35

0
41
lượt xem
3
download

Bài giảng Trí tuệ nhân tạo - Chương 2: Biểu diễn bài toán & tìm lời giải

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

Chương 2: Biểu diễn bài toán & tìm lời giải trong "Bài giảng Trí tuệ nhân tạo" giới thiệu đến các bạn những nội dung: Bài toán, biểu diễn bài toán, tìm kiếm, các chiến lược điều khiển, các đặc trưng của bài toán, vấn đề trong thiết kế CT tìm kiếm. Mời các bạn tham khảo nội dung chi tiết.

Chủ đề:
Lưu

Nội dung Text: Bài giảng Trí tuệ nhân tạo - Chương 2: Biểu diễn bài toán & tìm lời giải

  1. Chương 2: Biểu diễn bài toán & tìm lời giải 1
  2. Nội dung  Bài toán  Biểu diễn bài toán  Tìm kiếm  Các chiến lược ñiều khiển  Các ñặc trưng của bài toán  Vấn ñề trong thiết kế CT tìm kiếm 2
  3. Mô hình ứng dụng của TTNT TTNT = Presentation & Search Tri Thức Tìm kiếm Knowledge Search Engineering Suy luận Heurictic 3
  4. Bài toán  Giải bài toán bằng cách tìm kiếm, gồm:  Cấu trúc bài toán: tìm ñường ñi trên ñồ thị  Biểu diễn bài toán bằng không gian trạng thái  Giải bài toán = Tìm ra một trạng thái/con ñường trong không gian trạng thái (trạng thái ñầu -> trạng thái ñích)  Trạng thái  Biểu diễn một bước nào ñó của bài toán  Trong trò chơi, như tic-tac-toe, mỗi bàn cờ có thể là trạng thái X O O Trạng thái Trạng thái Trạng thái 4
  5. Bài toán (tt)  Chuyển trạng thái, luật chuyển  Biểu diễn cho sự có thể của việc chuyển từ trạng thái nào ñó ñến trạng thái khác.  Ví dụ: trong trò chơi, ñó là luật chơi của game. O O O 5
  6. Bài toán (tt)  Trạng thái ñầu  Trạng thái xuất phát của bài toán  Một bài toán có thể có nhiều trạng thái khởi ñầu  Ví dụ: game tic-tac-toe, trạng thái rỗng  Trạng ñích  Trạng thái mà bài toán ñã ñược giải  Một bài toán có thể có nhiều trạng thái ñích O X  Ví dụ: game tic-tac-toe, trạng thái ñích là: X X O 6
  7. Bài toán (tt)  Không gian trạng thái: một hệ thống gồm 4 thành phần [N,A,S,G]  N là tập nút của Graph. Mỗi nút là một trạng thái của quá trình giải quyết vấn ñề  A: Tập các cung nối giữa các nút N. Mỗi cung là một bước trong giải quyết vấn ñề. Cung có thể có hướng  S: Tập các trạng thái bắt ñầu. S khác rỗng.  G: Tập các trạng thái ñích. G Không rỗng  Không gian trạng thái sẽ ñược xây dựng DẦN khi chương trình chạy  Với bài toán lớn, không ñủ thời gian, không gian ñể ñặc tả cho từng trạng thái cụ thể, và ñường chuyển cụ thể 7
  8. Bài toán (tt)  Các vấn ñề khó khăn trong tìm kiếm với các bài toán TTNT  ðặc tả vấn ñề phức tạp  Không gian tìm kiếm lớn  ðặc tính ñối tượng tìm kiếm thay ñổi  ðáp ứng thời gian thực  Khó khăn về kỹ thuật  Bộ nhớ và tốc ñộ truy xuất 8
  9. Bài toán (tt) State Space Database  Không gian tìm kiếm thường là  Không gian tìm kiếm là một graph một list hay tree  Mục tiêu tìm kiếm là một path  Tìm kiếm một record/nút  Phải lưu trữ toàn bộ không gian  Phần tử ñã duyệt qua là không còn dùng tới trong quá trình tìm kiếm  Không gian tìm kiếm là cố  Không gian tìm kiếm biến ñộng ñịnh trong quá trình tìm liên tục trong quá trình tìm kiếm kiếm  ðặc tính của trạng thái/nút là  Thuộc tính của một phức tạp & biến ñộng record/nút là cố ñịnh 9
  10. Bài toán: Tic tac toe ðồ thị có hướng không lặp lại (directed acyclic graph - DAG) 10
  11. Bài toán: 8 puzzle Có khả năng xảy ra vòng lặp không? 11
  12. Chiến lược ñiều khiển  Sự cần thiết của chiến lược ñiều khiển  ðể giải ñược và giải nhanh bài toán  Các yêu cầu của 1 chiến lược tốt  Tạo ra sự thay ñổi  Có tính hệ thống.  Chọn luật radom -> tốt hơn so với trường hợp ñầu, nhưng quá trình giải có thể dài hơn  -> Cần xây dựng khả năng duyệt một cách có hệ thống  Hai cách duyệt có hệ thống: Breadth-First_Search – BrFS và Depth-First-Search (DFS) ñược trình bày sau 12
  13. Breadth-First-Search  Tạo biến Open.  ðưa TT bắt ñầu vào Open.  Lặp: (ñến khi gặp TT ñích) OR (Open trống):  E = RemoveFirst(Open).  Với mỗi luật so trùng ñược với E:  Áp dụng luật ñể sinh TT mới.  Nếu TT mới là TT ñích thì thoát, trả về TT này.  Ngược lại: ðưa TT mới vào CUỐI của Open. 13
  14. Breadth-First-Search (tt) Procedure Breath_first_search; BEGIN Open :=[start]; Close:=[ ]; WHILE (Open [ ]) do BEGIN remove X which is the leftmost of Open; IF (X=goal) THEN return (Success) ELSE BEGIN generate children of X; Put X to Close; remove children of X which is in Open or Close; Put remain children on RIGHT end of Open; END; END; Return (FAIL); END; 14
  15. Breadth-First-Search (tt) A B C D Laàn laëp X Open Close E F G 0 [A ] [] 1 A [B C D ] [A] 2 B [C D E F ] [A B] H I J 3 C [D E F G ] [A B C ] 4 D [E F G ] [A B C D ] 5 E [F G H I ] [A B C D E ] 6 F [G H I J ] [A B C D E F ] 7 G [H I J ] [A B C D E F ] 15
  16. Depth-First-Search  Nếu TT ñầu là ñích -> dừng, trả về success  Ngược lại: Lặp ñến khi gặp succes hay gặp error  Phát sinh TT con của TT bắt ñầu, gọi là E. Nếu không có con nào thì báo error  Gọi DFS với E như TT bắt ñầu  Nếu success ñược trả về thì trả về success. Ngược lại: tiếp tục lặp 16
  17. Depth-First-Search (tt) Procedure depth_first_search; Begin Open :=[start]; Close:=[ ]; While (Open [ ]) do begin remove X which is the leftmost of Open; If (X=goal) the return (Success) else begin generate children of X; Put X to Close; remove children of X which is in Open or Close; Put remain children on LEFT end of Open; End; End; Return (FAIL); End; 17
  18. Depth-First-Search (tt) A Laàn laëp X Open Close B C D 0 [A] [] 1 A [B C D ] [A] E G 2 B [E F C D ] [A B] F 3 E [H I F C D ] [A B E ] 4 H [I F C D ] [A B E H ] H I J 5 I [F C D ] [A B E H I ] 6 F [J C D ] [A B E H I F ] 7 J [C D ] [A B E H I F J ] 8 C [GD] [A B E H I F J C 9 G ] 18
  19. Breath First vs Depth First  Breath First: open ñược tổ chức dạng FIFO (Queue)  Depth First: open ñược tổ chức dạng LIFO (Stack)  ðặc tính  Breath First search hiệu quả khi lời giải nằm gần gốc của cây tìm kiếm, tìm nhiều lời giải, luôn tìm ra nghiệm có số cung nhỏ nhất  Depth First search hiệu quả khi lời giaỉ nằm sâu trong cây tìm kiếm và có một phương án chọn hướng ñi chính xác  Kết quả  Breath First search chắc chắn tìm ra kết quả nếu có  Depth First có thể sa lầy vào ñường quá dài  Bùng nổ tổ hợp là khó khăn lớn nhất cho các giải thuật này 19
  20. Depth first search có giới hạn  Depth first search có khả năng lặp vô tận do các trạng thái con sinh ra liên tục. ðộ sâu tăng vô tận  Khắc phục bằng cách giới hạn ñộ sâu của giải thuật  Sâu bao nhiêu thì vừa?  Chiến lược giới hạn:  Cố ñịnh một ñộ sâu MAX, như các danh thủ chơi cờ tính trước ñược số nước nhất ñịnh  Theo cấu hình resource của máy tính  Meta knowledge trong việc ñịnh giới hạn ñộ sâu  Giới hạn ñộ sâu => co hẹp không gian trạng thái => có thể mất nghiệm 20

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản