tailieunhanh - Bài giảng Trí tuệ nhân tạo: Bài 4 - Trương Xuân Nam

Bài giảng Trí tuệ nhân tạo: Bài 4 Tìm kiếm mù cung cấp cho người học những kiến thức như: Khái niệm tìm kiếm mù; Thuật toán; Các biến thể; Tìm kiếm theo chiều rộng (BFS); Tìm kiếm theo chi phí đồng nhất (UCS); Tìm kiếm theo chiều sâu (DFS); Tìm kiếm giới hạn chiều sâu (DLS); Tìm kiếm sâu dần (IDS); Tìm kiếm hai chiều (BS). | TRÍ TUỆ NHÂN TẠO Bài 4 Tìm kiếm mù Nội dung 1. Khái niệm tìm kiếm mù 2. Thuật toán 3. Các biến thể 1. Tìm kiếm theo chiều rộng BFS 2. Tìm kiếm theo chi phí đồng nhất UCS 3. Tìm kiếm theo chiều sâu DFS 4. Tìm kiếm giới hạn chiều sâu DLS 5. Tìm kiếm sâu dần IDS 6. Tìm kiếm hai chiều BS 4. Bài tập và câu hỏi Trương Xuân Nam - Khoa CNTT 2 Phần 1 Khái niệm tìm kiếm mù TRƯƠNG XUÂN NAM 3 Nhắc lại quan điểm AI là tìm kiếm Hình trạng Trạng thái state Bước chuyển path operator Chi phí bước chuyển path cost Hình trạng đích goal states - GS Hình trạng xuất phát start state - SS Lời giải Các bước chuyển từ SS đến GS Tìm lời giải Tìm đường đi Tìm càng nhanh thì càng thông minh Trương Xuân Nam - Khoa CNTT 4 Bài toán tìm đường đi Hình trạng là gì Bước chuyển Chi phí bước chuyển Hình trạng đích Hình trạng xuất phát Kích thước không gian Trương Xuân Nam - Khoa CNTT 5 Bài toán 8-mảnh Hình trạng là gì Bước chuyển Chi phí bước chuyển Hình trạng đích Hình trạng xuất phát Kích thước không gian Trương Xuân Nam - Khoa CNTT 6 Bài toán Nhóm người sang sông Có 4 người A B C D đang đứng ở bên bờ sông và muốn sang bên bờ kia Có 1 chiếc phao cho 2 người 1 người dùng vẫn được Muốn qua sông nhất thiết phải dùng phao Thời gian qua sông của mỗi người là khác nhau. Nếu 2 người cùng dùng phao thì tính theo thời gian của người bơi chậm hơn A bơi qua sông mất 1 phút B mất 2 phút C mất 5 phút D mất 10 phút Nhóm cần ít nhất bao nhiêu phút để qua sông Trương Xuân Nam - Khoa CNTT 7 Khái niệm tìm kiếm mù Xuất phát từ hình trạng ban đầu START và tìm các bước chuyển để đến một hình trạng đích GOAL Thông tin duy nhất là chi phí của từng bước chuyển không có thông tin bổ sung Chính vì không có thông tin bổ sung nên ta không có định hướng cho việc tìm kiếm dẫn đến hệ quả là ta tìm không theo trật tự nào cả như người mù Bản chất Xuất phát từ START lần lượt DUYỆT qua các hình trạng liên quan cho đến khi gặp GOAL Trương Xuân Nam - Khoa CNTT 8 Phần 2 Thuật toán TRƯƠNG XUÂN NAM 9 Thuật toán function SEARCH START .