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

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.
Nội dung trích xuất từ tài liệu:
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ảiChương 2: Biểu diễn bài toán & tìm lời giải 1Nộ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 2Mô 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 3Bà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 4Bà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 5Bà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 6Bà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ể 7Bà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 8Bà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 9Bài toán: Tic tac toeðồ thị có hướng khônglặp lại (directed acyclic graph - DAG) 10Bài toán: 8 puzzle Có khả năng xảy ra vòng lặp không? 11Chiế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 12Breadth-First-Search Tạo biến Open. ðưa TT bắt ñầu vào Ope ...