tailieunhanh - CÀI ĐẶT THUẬT TOÁN AKT CHO BÀI TOÁN THÁP HÀ NỘI

Mở đỉnh đầu tiên S, gán g(S) = 0 Sử dụng tri thức bổ sung để ước tính hàm h(S) Tính f(S) = g(S) + h(S) Bước 2 Chọn đỉnh mở có f là nhỏ nhất và gọi đỉnh đó là N Nếu N là đích: đường đi từ đỉnh ban đầu đến đỉnh N là ngắn nhất và bằng g(N). Dừng (Success). Nếu không tồn tại đỉnh mở nào: cây biểu diễn vấn đề không tồn tại đường đi tới mục tiêu. Dừng (Fail). Nếu có 2 đỉnh mở trở lên có cùng giá trị f nhỏ nhất: ta. | Tài liệu hướng dẫn thực hành CÀI ĐẶT THUẬT TOÁN AKT CHO BÀI TOÁN THÁP HÀ NỘI 1. Thuật toán AKT Bước 1 Mở đỉnh đầu tiên S gán g S 0 Sử dụng tri thức bổ sung để ước tính hàm h S Tính f S g S h S Bước 2 Chọn đỉnh mở có f là nhỏ nhất và gọi đỉnh đó là N Nếu N là đích đường đi từ đỉnh ban đầu đến đỉnh N là ngắn nhất và bằng g N . Dừng Success . Nếu không tồn tại đỉnh mở nào cây biểu diễn vấn đề không tồn tại đường đi tới mục tiêu. Dừng Fail . Nếu có 2 đỉnh mở trở lên có cùng giá trị f nhỏ nhất ta phải kiểm tra xem những đỉnh đó có đỉnh nào là đích hay không. Nếu có Đường đi từ đỉnh ban đầu đến đỉnh N là ngắn nhất và bằng g N . Dừng. Nếu không có chọn ngẫu nhiên một trong các đỉnh đó và gọi đó là đỉnh N. Bước 3 Đóng đỉnh N mở mọi đỉnh sau N. Với mỗi đỉnh sau N tính g S g N gt S- N Sử dụng tri thức bổ sung để tính h S . f S g S h S . Bước 4 Quay lại Bước 2. 2. Cấu trúc dữ liệu typedef struct char Dia MAXDIA int SoDia COT typedef struct COT Cot MAXCOT int SoCot int TrangThai int DinhTruoc int g h DINH DINH O MAX int nO Ý nghĩa O Là tập các đỉnh trên cây tìm kiếm. nO Số lượng đỉnh trên cây tìm kiếm. DINH. Cot Sự phân phối các đĩa trên tháp. DINH. SoCot Số tháp ban đầu. DINH. TrangThai 1 Tài liệu hướng dẫn thực hành 0 Nếu là đỉnh mở. 1 Nếu là đỉnh đóng. DINH. DinhTruoc Trả về thứ tự của đỉnh trước đó. DINH. g h Lượng giá 1 đỉnh. 3. Hướng dẫn cài đặt Hàm lượng giá Dữ liệu vào 1 đỉnh P trên cây tìm kiếm. Dữ liệu ra Giá trị H của đỉnh P. int TinhH DINH P Trả về giá trị h của 1 đỉnh. Hàm tìm kiếm void Solve DINH O MAXDINH int nO int Thoat Thoat 1 Tìm thành công. Thoat 2 Tìm thất bại. Thoat 3 Không có lời giải. Thoat 0 Đang trong quá trình tìm kiếm Khởi tạo mảng đỉnh O O 0 .Cot O 0 .SoCot O 0 .DinhTruoc -1 O 0 .TrangThai 0 O 0 . g 0 O 0 . h TinhH O 0 nO 1 Thoat 0 while Thoat 0 t chỉ số đỉnh mở trong O có f lấy g h nhỏ nhất. Nếu không tìm được t thì Thoat 3 Thuật giải dừng không có lời giải cho bài toán Đóng đỉnh O t . O t .TrangThai 1 Gọi S1 là tập đỉnh sau O t không