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ìmkiếm.
Nội dung trích xuất từ tài liệu:
Trí tuệ nhân tạo - Chương 3Chương 3 - Cấu trúc và chiến lược cho TK - KGTT Khi biểu diễn một vấn đề như là một đồ thị không gian trạng thái, chúng ta có thể sử dụng lý thuyết đồ thị để phân tích cấu trúc và độ phức tạp của các vấn đề cũng rb1 như các thủ tục tìm kiếm. b2 b4 Riverbank1 b3 b1 i2 4 i1 2 3 1 Island 2 Island 1 b6 b7 b5 6 5 7 rb2 Riverbank 2 Hệ thống cầu thành phố Konigsberg và biểu diễn đồ thị tương ứng TTNT. p.41C 3 – Tìm kiếm không gian trạng thái 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) TTNT. p.42C 3 – Tìm kiếm không gian trạng thái ĐN: KHÔNG GIAN TRẠNG THÁIMộ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  N  S  ) 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. TTNT. p.43 C 3 – Tìm kiếm không gian trạng thái Một phần KGTT triển khai trong Tic-tac-toeĐồ thị có hướng khônglặp lại (directed acyclic graph - DAG) TTNT. p.44C 3 – Tìm kiếm không gian trạng thái Trò đố 8 ô hay 15 ô Trạng thái ban đầu Trạng thái đích đố Trò 11 14 4 7 1 2 3 4 15 ô 10 6 5 12 13 14 5 1 2 13 15 11 15 6 9 12 8 3 10 9 8 7 đố Trò 2 8 1 2 3 3 5 7 8 4 8ô 6 2 1 7 6 5 Cần biểu diễn KGTT cho bài toán này như thế nào? TTNT. p.45C 3 – Tìm kiếm không gian trạng tháiKGTT của 8-puzzle sinh ra bằng phép “di chuyển ô trống” Có khả năng xảy ra vòng lặp không? TTNT. p.46C 3 – Tìm kiếm không gian trạng thái Một ví dụ của bài toán TSP Cần biểu diễn KGTT cho bài toán này như thế nào? TTNT. p.47C 3 – Tìm kiếm không gian trạng thái KGTT của bài toán TSP Mỗi cung được đánh dấu bằng tổng giá của con đường từ nút bắt đầu đến nút hiện tại. ...