tailieunhanh - Trí tuệ nhân tạo - Chương 3

Các trạng thái trong GD (Goal Description) được mô tả theo một trong hai đặc tính: – Đặc tính có thể đo lường được các trạng thái gặp trong quá 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 quá trình tìm kiếm. | Chương 3 - Cấu trúc và chiến lược cho TK - KGTT _ TT 1 V . Ấ J-Ă 1 ly V . J_Ă .1 11 Khi biêu diễn một vân đê như là một đô thị không gian J 1 r A r j1 Ẳ 7 1 1 r j1 Ấ - J. Ầ 1 4-Ẳ trạng thái chúng ta có thê sử dụng lý thuyêt đô thị đê 1 J r 1 Ấ r V J- V 1 r J 7 r k J-Ă phân tích câu trúc và độ phức tạp của các vân đê cũng như Hệ thống cầu thành phố Konigsberg và biêu diễn đô thị tương ứng C 3 - Tìm kiêm không gian trạng thái TTNT. Nội dung chương 3 Định nghĩa Không Gian Trạng Thái Các chiến lược tìm kiếm trên không gian trạng thái - TK hướng từ dữ liệu data - driven - TK hướng từ mục tiêu goal - driven . Tìm kiếm trên không gian 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 không gian 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 không gian trạng thái TTNT. ĐN KHÔNG GIAN TRẠNG THÁI Một KGTT state space là 1 bộ N A S GD trong đó N node là các nút hay các trạng thái của đồ thị. A arc là tập các cung hay các liên kết giữa các nút. S solution là một tập chứa các trạng thái đích của bài toán. S c N A S i 0 Các trạng thái trong GD Goal Description được mô tả theo một trong hai đặc tính - Đặc tính có thể đo lường được các trạng thái gặp trong quá 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 quá trình tìm kiếm. VD TSP Đường đi của lời giải 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 không gian trạng thái TTNT. .