Chương - Cấu trúc chiến lược cho TK - KGTT  Khi biểu diễn vấn đề đồ thị không gian trạng thái, sử dụng lý thuyết đồ thị để phân tích cấu trúc độ phức tạp vấn đề rb1 thủ tục tìm kiếm b2 Riverbank1 b4 b3 b1 Island1 i2 i1 Island b5 b6 b7 Riverbank rb2 Hệ thống cầu thành phố Konigsberg biểu diễn đồ thị tương ứng C – Tìm kiếm không gian trạng thái TTNT p.41 Nội dung chương   Định nghĩa Không Gian Trạng Thái Các chiến lược tìm kiếm khơng gian trạng thái: – TK hướng từ liệu (data – driven) – TK hướng từ mục tiêu (goal – driven)  Tìm kiếm không gian trạng thái: – TK rộng (breath – first search) – TK sâu (depth – first search) – TK sâu 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 – Tìm kiếm khơng gian trạng thái TTNT p.42 ĐN: KHƠNG GIAN TRẠNG THÁI Một KGTT (state space) [N, A, S, GD] đó:  N (node) nút hay trạng thái đồ thị  A (arc) tập cung (hay liên kết) nút  S (solution) tập chứa trạng thái đích tốn.(S  N  S  )  Các trạng thái GD (Goal Description) mơ tả theo hai đặc tính: – Đặc tính đo lường trạng thái gặp trình tìm kiếm VD: Tic-tac-toe, 8-puzzle,… – Đặc tính đường hình thành q trình tìm kiếm VD: TSP  Đường lời giải (solution path) đường qua đồ thị từ nút thuộc S đến nút thuộc GD C – Tìm kiếm khơng gian trạng thái TTNT p.43 Một phần KGTT triển khai Tic-tac-toe Đồ thị có hướng khơng lặp lại (directed acyclic graph - DAG) C – Tìm kiếm khơng gian trạng thái TTNT p.44 Trị đố hay 15 Trạng thái ban đầu đố 15  Trị  Trị 8ơ 11 14 10 12 13 14 13 15 11 15 12 10 8 đố Trạng thái đích biểu diễn KGTT cho toán nào?  Cần C – Tìm kiếm khơng gian trạng thái TTNT p.45 KGTT 8-puzzle sinh phép “di chuyển trống” Có khả xảy vịng lặp khơng? C – Tìm kiếm khơng gian trạng thái TTNT p.46 Một ví dụ toán TSP biểu diễn KGTT cho toán nào?  Cần C – Tìm kiếm khơng gian trạng thái TTNT p.47 KGTT toán TSP Mỗi cung đánh dấu tổng giá đường từ nút bắt đầu đến nút C – Tìm kiếm khơng gian trạng thái TTNT p.48 Các Chiến Lược cho TK-KGTT  TK hướng từ liệu (Data-driven Search) – Suy diễn tiến (forward chaining)  TK hướng từ mục tiêu (Goal-driven Search) – Suy diễn lùi (backward chaining) C – Tìm kiếm khơng gian trạng thái TTNT p.49 TK Hướng từ Dữ Liệu  Việc tìm kiếm từ liệu đến mục tiêu  Thích hợp khi: – Tất phần liệu cho từ đầu – Có nhiều mục tiêu, có số phép tốn áp dụng cho trạng thái tốn – Rất khó đưa mục tiêu giả thuyết lúc đầu C – Tìm kiếm khơng gian trạng thái TTNT p.50