Bài giảng Các hệ thống thông minh nhân tạo và ứng dụng - Chương 3: Bài toán tìm kiếm 1 có nội dung trình bày tổng quan về bài toán tìm kiếm, cây tìm kiếm, các thuật toán tìm kiếm mù, . Mời các bạn cùng tham khảo chi tiết nội dung bài giảng! | CÁC HỆ THỐNG THÔNG MINH NHÂN TẠO amp ỨNG DỤNG Bài toán tìm kiếm I THS. BÙI THỊ DANH KHOA CNTT Nội dung chính Tổng quan bài toán tìm kiếm Cây tìm kiếm Các thuật toán tìm kiếm mù 2 Bài toán tìm kiếm Bài toán tìm đường đi Tìm đường ngắn nhất Tìm đường nhanh nhất Tìm đường có nhiều cảnh đẹp nhất Các hành động Đi thẳng Rẽ trái Rẽ phải 3 Bài toán tìm kiếm Giải bài toán puzzle Tìm cách đạt đến cấu hình xác định Các hành động Di chuyển các miếng ghép 4 Bài toán tìm kiếm Một bài toán tìm kiếm gồm 5 thành phần Không gian trạng thái S Tập các hành động Action s Trạng thái bắt đầu start Hàm kiểm tra trạng thái đích IsGoal s Hàm xác định trạng thái kế tiếp Successor s Thường đi kèm với hành động và chi phí tương ứng Một lời giải của bài toán tìm kiếm là một chuỗi các hành động để di chuyển từ trạng thái bắt đầu đến trạng thái đích. 5 Không gian trạng thái Trạng thái state là tập các chi tiết thông tin cần thiết cho việc ra quyết định. Không gian trạng thái là tập tất cả các trạng thái có thể có. Kích thước của không gian trạng thái được tính như sau Mỗi trạng thái có N chi tiết Mỗi chi tiết có miền giá trị là Kích thước của không gian trạng thái 1 2 6 Bài toán tìm đường đi Trạng thái tên địa điểm S tất cả các địa điểm trên bản đồ Start điểm xuất phát IsGoal s Có phải điểm muốn đến không Successor s các trạng thái có thể đi đến được từ s. Câu hỏi Kích thước không gian trạng thái là bao nhiêu 7 Bài toán tìm đường đi Tìm đường đi ngắn nhất từ thành phố 1 đến thành phố n. Biết rằng chỉ được di chuyển từ thành phố có chỉ số nhỏ hơn đến thành phố có chỉ số lớn hơn. Không được viếng thăm quá 2 thành phố lẻ Câu hỏi trạng thái gồm các chi tiết gì Từ đó xác định các thành phần của bài toán Trạng thái thành phố hiện tại thành phố trước là lẻ true false Actions s đi từ thành phố sang thành phố khác IsGoal s s có phải là thành phố n không Successor s các trạng thái s Thành_phố Là_lẻ . Trong đó Thành_phố chỉ số của thành phố đi đến được tức ℎà ℎ_ ℎố Là_lẻ true nếu s .
