- 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. - 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 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. - 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ể. - 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