Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Hình 6.14 Phân biệt khái niệm g và h’ Kết hợp g và h’ thành f’ (f’ = g + h’) sẽ thể hiện một ước lượng về "tổng chi phí" cho con đường từ trạng thái bắt đầu đến trạng thái kết thúc dọc theo con đường đi qua trạng thái hiện hành. Để thuận tiện cho thuật giải, ta quy ước là g và h’ đều không âm và càng nhỏ nghĩa là càng tốt | Hình 6.14 Phân biệt khái niệm g và h Kết hợp g và h thành f f g h sẽ thể hiện một ước lượng về tổng chi phí cho con đường từ trạng thái bắt đầu đến trạng thái kết thúc dọc theo con đường đi qua trạng thái hiện hành. Để thuận tiện cho thuật giải ta quy ước là g và h đều không âm và càng nhỏ nghĩa là càng tốt. III.5. Thuật giải AT Thuật giải AT là một phương pháp tìm kiếm theo kiểu BFS với độ tốt của nút là giá trị hàm g - tổng chiều dài con đường đã đi từ trạng thái bắt đầu đến trạng thái hiện tại. o Thuật giải AT 1. Đặt OPEN chứa trạng thái khởi đầu. 2. Cho đến khi tìm được trạng thái đích hoặc không còn nút nào trong OPEN thực hiện 2.a. Chọn trạng thái Tmax có giá trị g nhỏ nhất trong OPEN và xóa Tmax khỏi OPEN 2.b. Nếu Tmax là trạng thái kết thúc thì thoát. 2.c. Ngược lại tạo ra các trạng thái kế tiếp Tk có thể có từ trạng thái Tmax. Đối với mỗi trạng thái kế tiếp Tk thực hiện g Tk g Tmax cost Tmax Tk Thêm Tk vào OPEN. Vì chỉ sử dụng hàm g mà không dùng hàm ước lượng h fsđể đánh giá độ tốt của một trạng thái nên ta cũng có thể xem AT chỉ là một thuật toán. 111.6. Thuật giải AKT Algorithm for Knowlegeable Tree Search Thuật giải AKT mở rộng AT bằng cách sử dụng thêm thông tin ước lượng h . Độ tốt của một trạng thái f là tổng của hai hàm g và h . o Thuật giải AKT 1. Đặt OPEN chứa trạng thái khởi đầu. 2. Cho đến khi tìm được trạng thái đích hoặc không còn nút nào trong OPEN thực hiện 2.a. Chọn trạng thái Tmax có giá trị f nhỏ nhất trong OPEN và xóa Tmax khỏi OPEN 2.b. Nếu Tmax là trạng thái kết thúc thì thoát. 2.c. Ngược lại tạo ra các trạng thái kế tiếp Tk có thể có từ trạng thái Tmax. Đối với mỗi trạng thái kế tiếp Tk thực hiện g Tk g Tmax cost Tmax Tk Tính h Tk f Tk g Tk h Tk Thêm Tk vào OPEN. 111.7. Thuật giải A A là một phiên bản đặc biệt của AKT áp dụng cho trường hợp đồ thị. Thuật giải A có sử dụng thêm tập hợp CLOSE để lưu trữ những trường hợp đã được xét đến. A mở rộng AKT bằng cách bổ sung cách giải quyết trường hợp khi mở một nút mà nút này đã có sẵn trong
