Môn: Trí tuệ nhân tạo Lớp TH2006/01,02 Bài tập thực hành 3 Thuật toán A* Nội dung Cài đặt thuật toán tìm kiếm đường đi A* áp dụng trên bài toán đồ thị. Mục tiêu - Sinh viên nắm được cơ chế vận hành của thuật toán tìm kiếm đường đi A*, áp dụng lên một dạng bài toán tìm kiếm cụ thể là tìm kiếm trên đồ thị. - Sinh viên có sự quan sát và so sánh các thuật toán đã học: UCS (tìm kiếm với chi phí g), Greedy (tìm kiếm với heuristic h) và A* (kết hợp g và h). Yêu cầu Cho một bản đồ có N thành phố và các đường đi có thể có giữa các thành phố.Chi phi di chuyển giữa hai thành phố kế cận nhau là w (w > 0), các đường đi có thể là 2 chiều (A đến được B thì B cũng đến được A), hoặc 1 chiều (chỉ có A đến được B). Cho trước thành phố xuất phát và thành phố đích. Hãy tìm đường đi giữa hai thành phố được chỉ định bằng thuật toán A* với h = khoảng cách Eulicde từ thành phố đang xét đến thành phố đích. Nếu tồn tại đường đi: xuất ra màn hình thứ tự đường đi. Nếu không tồn tại đường đi: thông báo không có đường đi. Định dạng dữ liệu đầu vào: ¾ Dòng 1: Số thành phố trên bản đồ ¾ Dòng 2: Thành phố xuất phát và thành phố đích ¾ N dòng tiếp theo: tọa độ (x, y) của các thành phố (x, y > 0) ¾ N dòng tiếp theo: ma trận kề của đồ thị với quy ước: 9 M[i][j] = w: có đường nối trực tiếp từ i đến j với chi phí là w (w > 0) 9 M[i][j] = 0: không có đường nối trực tiếp từ i đến j Các thành phố được đánh chỉ số từ 0 Thời gian: 1 tuần (03/10/2008 – 09/10/2008) Quy định nộp: Nộp bài qua Moodle theo thời hạn đã chỉ định, bài nộp không bao gồm các vấn đề nêu trong mục Các vấn đề khác. GVHDTH: Nguyễn Ngọc Thảo, Võ Đình Phong, Lê Ngọc Thành, Trần Ngọc Trung 1 Môn: Trí tuệ nhân tạo Lớp TH2006/01,02 Ví dụ Lưu ý: giá trị h trong hình chỉ mang tính minh họa và không có sẵn trong dữ liệu đầu vào. Các vấn đề khác Vấn đề so sánh hiệu quả của các dạng thuật toán tìm kiếm: sinh viên cần có sự quan sát và so sánh các thuật toán tìm kiếm đã được học, các đại diện bao gồm: UCS (chỉ sử dụng chi phí g), Greedy (sử dụng heuristic h), và A* (kết hợp g và h). Hiệu quả thuật toán xét trên các tiêu chí: số đỉnh mở, đường đi tối ưu hay không, thời gian thực hiện (với bài toán có số trạng thái lớn). Cần thực hiện trên các dạng bài toán khác nhau để nắm vững hơn ý tưởng của bài toán tìm kiếm, ví dụ: bài toán tìm đường đi trên đồ thị, n-puzzle, n-Queens, tháp Hà Nội… Với những bài toán dùng A* để tính toán mà có thể có nhiều hàm h khác nhau, cần tìm hiểu và thử lý giải bằng lý thuyết và thực nghiệm để chứng tỏ hiệu quả của từng dạng hàm h khác nhau khi đưa vào bài toán cụ thể. Điều này tạo cơ sở cho việc lập luận vững chắc khi cần quyết định chọn hay tự thiết kế một công thức tính h cho bài toán mà mình cần giải quyết. Cài đặt mở rộng liên hệ với thuật toán A*: - Cài đặt thuật toán Greedy: đây là khởi nguyên của thuật toán tìm kiếm dựa trên heuristic. Hãy nhận xét xem Greedy có nhược điểm gì so với A*? - Cài đặt IDA*: với cách lặp sâu dần, IDA* nhằm giải quyết vấn đề về bộ nhớ. Hãy nhận xét xem hiệu quả của IDA* có tốt hơn A* không? GVHDTH: Nguyễn Ngọc Thảo, Võ Đình Phong, Lê Ngọc Thành, Trần Ngọc Trung 2