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

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!
Nội dung trích xuất từ tài liệu:
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ÁC HỆ THỐNG THÔNG MINH NHÂN TẠO & ỨNG DỤNG Bài toán tìm kiếm I THS. BÙI THỊ DANH BM.KHMT, KHOA CNTT, ĐH.KHTN TP.HCM 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 là thành phố lẻ hoặc chi tiết s.Là_lẻ là true. 8 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. ◦ Cần viếng thăm ít nhất 3 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? 9 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. ◦ Cần viếng thăm số thành phố lẻ nhiều hơn số thành phố chẵn. 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? 10 Bài toán Puzzle Câu hỏi: Cho biết trạng thái gồm các chi tiết gì? Liệt kê các thành phần của bài toán? 11 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ù 12 Đồ thị trạng thái Đồ thị trạng thái (state graph): một cách biểu diễn hình học cho bài toán tìm kiếm. ◦ Mỗi đỉnh đồ thị tương ứng với một trạng thái ◦ Mỗi cạnh đồ thị nối trạng thái với một trạng thái kế của nó. ◦ Hàm kiểm tra trạng thái đích chính là tập các đỉnh tương ứng với trạng thái đích Trong đồ thị trạng thái, mỗi trạng thái chỉ xuất hiện duy nhất một lần Thường không xây dựng đồ thị trạng thái đầy đủ trên bộ nhớ máy tính vì rất lớn. 13 Đồ thị trạng thái 14 Cây tìm kiếm Cây tìm kiếm (search tree) là cấu trúc cây thể hiện các hành động và kết quả tương ứng của hành động. ◦ Node gốc tương ứng với trạng thái bắt đầu ◦ Các node con tương ứng với trạng thái kế tiếp của node cha. ◦ Node lá tương ứng với trạng thái đích ◦ Mỗi lời giải tương ứng với một đường đi từ gốc đến node lá Mỗi trạng thái có thể xuất hiện nhiều hơn 1 lần. Thường không xây dựng đầy đủ cây tìm kiếm trong bộ nhớ vì rất lớn 15 Đồ thị trạng thái vs Cây tìm kiếm 16 Câu hỏi Giả sử trạng thái bắt đầu là Faragas, hãy vẽ cây tìm kiếm cho đồ thị trạng thái dưới đây? Eforie Pitesti Vaslui Sibiu Craiova Arad Faragas Lugoj Zerind Oradea 17 Cây tìm kiếm Câu hỏi: có bao nhiêu node trên cây tìm kiếm tương ứng với đồ thị trạng thái sau? 18 Thuật toán tìm ...