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

Bài giảng Trí tuệ nhân tạo: Bài 5 Tìm kiếm có định hướng cung cấp cho người học những kiến thức như: Tìm kiếm mù vs Tìm kiếm có định hướng; Tìm kiếm theo tốt nhất (best-first search; Tìm kiếm tham lam (greedy best-first search); Thuật toán A*. Mời các bạn cùng tham khảo! | TRÍ TUỆ NHÂN TẠO Bài 5 Tìm kiếm có định hướng Nội dung 1. Tìm kiếm mù vs Tìm kiếm có định hướng 2. Tìm kiếm theo tốt nhất best-first search 3. Tìm kiếm tham lam greedy best-first search 4. Thuật toán A Trương Xuân Nam - Khoa CNTT 2 Phần 1 Tìm kiếm mù vs Tìm kiếm có định hướng TRƯƠNG XUÂN NAM 3 Tìm kiếm mù vs Tìm kiếm có định hướng Nhắc lại hoạt động của thuật toán tìm kiếm mù Duy trì một tập các trạng thái đang xem xét tập S ban đầu chỉ chứa điểm xuất phát Chọn ngẫu nhiên trạng thái N trong S mở rộng tập S kết nạp các trạng thái con của N Dừng nếu đến điểm đích goal hoặc hết trạng thái xem xét Hoạt động của tìm kiếm mù bản chất là mở rộng không gian tìm kiếm ngày càng lan xa dần điểm xuất phát nếu không gian tìm kiếm là hữu hạn thuật toán sẽ đến đích vào một thời điểm nào đó hoặc xét hết các trạng thái Vấn đề không gian trạng thái mở rộng một cách ngẫu nhiên bùng nổ số trạng thái TRƯƠNG XUÂN NAM 4 Tìm kiếm mù vs Tìm kiếm có định hướng Làm thế nào để tránh việc mở rộng một cách ngẫu nhiên sử dụng thông tin bổ sung trong quá trình mở rộng Thay vì mở rộng ngẫu nhiên có thể xây dựng cơ chế nào đó ưu tiên các trạng thái mà theo kinh nghiệm thì có nhiều cơ hội đến đích hơn Bài toán di chuyển trên bản đồ thì nên ưu tiên theo hướng đi Đi từ Hà Nội vào Đà Nẵng thì tới Nam Định tốt hơn là tới Yên Bái hoặc Thái Nguyên TRƯƠNG XUÂN NAM 5 Tìm kiếm mù vs Tìm kiếm có định hướng Trong tình huống khác ta có thể ưu tiên các dấu hiệu đi biển nếu đi càng xa bờ thì nước càng xanh thẫm hơn Chơi cờ vua nên chọn nước ăn quân hậu hơn là nước ăn quân tốt hoặc quân tượng Chơi trò 8-mảnh ưu tiên những trạng thái có nhiều mảnh đặt đúng vị trí cuối cùng của nó Tất cả những cơ chế này đều có tính kinh nghiệm không phải lúc nào cũng đúng thậm chí nhiều lúc còn là lựa chọn tệ nhất TRƯƠNG XUÂN NAM 6 Phần 2 Tìm kiếm theo tốt nhất best- first search TRƯƠNG XUÂN NAM 7 Tìm kiếm theo tốt nhất Thay vì lấy ngẫu nhiên một trạng thái khỏi tập quan sát S ta chọn trạng thái mà ta đánh giá là tốt nhất Xây dựng