Thuật toán đệ quy cho phép bỏ qua danh sách open trong suốt quá trình thực hiện. Cơ chế mà một ngôn ngữ lập trình sử dụng để cài đặt đệ quy là dùng mẩu tin hoạt động (activation record) cho từng lần gọi đệ quy. Quá trình lần ngược sẽ tác động khi tất cả các con cháu của một trạng thái không phải là đích, làm cho bước đệ quy đó thất bại. Việc thực hiện đệ quy cho phép lập trình viên thu hẹp tầm nhìn của họ vào một trạng thái duy nhất cùng với các con của nó thay vì. | Chương 5: Điều khiển và cài đặt tìm kiếm trong không gian trạng thái Chương V ĐIỀU KHIỂN VÀ CÀI ĐẶT TÌM KIẾM TRONG KHÔNG GIAN TRẠNG THÁI Nội dung chính: Trong chương này, các kỹ thuật sâu hơn cho việc cài đặt các thuật toán tìm kiếm sẽ được trình bày một cách chi tiết. Trước hết là tìm kiếm đệ quy (recursive search) – một phương pháp thực hiện tìm kiếm sâu kèm theo lần ngược với cách thức tự nhiên và ngắn gọn. Tìm kiếm đệ quy được tăng cường nhờ sử dụng sự hợp nhất (unification) để tìm kiếm các không gian trạng thái do các biểu thức của phép tính vị từ sinh ra. Sự kết hợp này cho ta thuật toán tìm kiếm hướng mẫu (pattern – directed search). Phần tiếp theo trong nội dung chương V giới thiệu mô hình hệ sinh (production system) – một cấu trúc tổng quát để giải các bài toán hướng mẫu, nó được sử dụng khá nhiều không những để mô hình hóa việc giải quyết các vấn đề của con người, mà còn để xây dựng các hệ chuyên gia và những ứng dụng Trí tuệ nhân tạo khác. Cuối cùng, một cách giải bài toán trí tuệ nhân tạo khác cũng được đề cập đến – kiến trúc bảng đen (blackboard architecture). Mục tiêu cần đạt : Sau chương này, sinh viên có thể : ¾ Vận dụng thuật toán tìm kiếm đệ quy kết hợp lần ngược trên không gian trạng thái. ¾ Hiểu thuật toán hướng mẫu khi thực hiện việc tìm kiếm trong không gian trạng thái. ¾ Vận dụng hệ sinh cho một bài toán. ¾ Hiểu các ưu điểm của hệ sinh ¾ Hiểu các ứng dụng kiến trúc bảng đen trong GQVĐ. Kiến thức tiên quyết : Lý thuyết đồ thị, Các thuật toán tìm kiếm trên đồ thị, Lý thuyết trò chơi, Tài liệu tham khảo : [1] George F. Luger, William A. Stubblefield – Albuquerque – Artificial Intelligence – Wesley Publishing Company, Inc – 1997 (Chapter 4) [2] Bùi Xuân Toại – Trương Gia Việt (Biên dịch) – Trí tuệ nhân tạo – Các cấu trúc và chiến lược giải quyết vấn đề - NXB Thống kê, 2000 (Phần II) [3] Recursion: [4] Blackboard Architecture: Võ Huỳnh Trâm – Trần Ngân Bình 79
