Nội dung của tiểu luận trình bày tìm kiếm theo chiều sâu; tìm kiếm theo chiều sâu; tìm kiếm theo chiều rộng; tìm kiếm theo giá thành thống nhất; tìm kiếm sâu dần; tìm kiếm leo đồi; Simulated annealing search. | Báo cáo môn Trí tuệ nhân tạo Tìm hiểu một số giải thuật môn học Trí tuệ nhân tạo Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo GVHD Ngô Hồ Anh Khôi TÌM HIỂU MỘT SỐ GIẢI THUẬT MÔN HỌC TRÍ TUỆ NHÂN TẠO GVHD Ngô Hồ Anh Khôi Sinh viên thực hiện Nguyễn Lập An Khương 1. Tìm kiếm theo chiều rộng. Tìm kiếm theo chiều rộng BFS là một thuật toán tìm kiếm trong đồ thị trong đó việc tìm kiếm chỉ bao gồm 2 thao tác a cho trước một đỉnh của đồ thị b thêm các đỉnh kề với đỉnh vừa cho vào danh sách có thể hướng tới tiếp theo. Có thể sử dụng thuật toán tìm kiếm theo chiều rộng cho hai mục đích tìm kiếm đường đi từ một đỉnh gốc cho trước tới một đỉnh đích và tìm kiếm đường đi từ đỉnh gốc tới tất cả các đỉnh khác. Trong đồ thị không có trọng số thuật toán tìm kiếm theo chiều rộng luôn tìm ra đường đi ngắn nhất có thể. Thuật toán BFS bắt đầu từ đỉnh gốc và lần lượt nhìn các đỉnh kề với đỉnh gốc. Sau đó với mỗi đỉnh trong số đó thuật toán lại lần lượt nhìn trước các đỉnh kề với nó mà chưa được quan sát trước đó và lặp lại. Xem thêm thuật toán tìm kiếm theo chiều sâu trong đó cũng sử dụng 2 thao tác trên nhưng có trình tự quan sát các đỉnh khác với thuật toán tìm kiếm theo chiều rộng. giải thuật tìm kiếm theo chiều rộng duyệt từ A tới B tới E tới F sau đó tới C tới G và cuối cùng tới D. Giải thuật này tuân theo qui tắc Qui tắc 1 Duyệt tiếp tới đỉnh liền kề mà chưa được duyệt. Đánh dấu đỉnh mà đã được duyệt. Hiển thị đỉnh đó và đẩy vào trong một hàng đợi queue . Qui tắc 2 Nếu không tìm thấy đỉnh liền kề thì xóa đỉnh đầu tiên trong hàng đợi. Qui tắc 3 Lặp lại Qui tắc 1 và 2 cho tới khi hàng đợi là trống. Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo GVHD Ngô Hồ Anh Khôi Ứng dụng Thuật toán tìm kiếm theo chiều rộng được dùng để giải nhiều bài toán trong lý thuyết đồ thị chẳng hạn như Tìm tất cả các đỉnh trong một thành phần liên thông Tìm đường đi ngắn nhất giữa hai đỉnh u và v với chiều dài đường đi tính bằng số cung Kiểm tra xem một đồ thị có là đồ thị hai .
