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

Chia sẻ: Huy Đạt | Ngày: | Loại File: PDF | Số trang:3

Thêm vào BST

Báo xấu

780
lượt xem 51
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: CÀI ĐẶT THUẬT TOÁN AKT CHO BÀI TOÁN THÁP HÀ NỘI

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 3.1 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. } 3.2 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[0..k] là tập đỉnh sau O[t] không nằm trong O. Với mỗi S1[i]: i=0..k Nếu nO>MAX Thoat = 2 Thuật giải dừng, không đủ không gian để tìm lời giải. Đưa S1[i] vào O nO++ 2
Tài liệu hướng dẫn thực hành O[nO-1] ← S1[i] O[nO-1].TrangThai = 0 O[nO-1].DinhTruoc = t Nếu S1[i] là đích thì Nho = nO-1 Thoat = 1 Thuật giải dừng, thành công } Nếu Thoat = 1 Dựa vào thông tin đỉnh trước in ra các cách biến đổi Ngược lại Không tìm được lời giải } 4. Mở rộng Dùng cấu trúc dữ liệu động (danh sách liên kết). Xây dựng 1 template về danh sách liên kết, gọi là List Định nghĩa lại cấu trúc dữ liệu: typedef struct { char Dia[MAXDIA]; int SoDia; }COT; typedef struct { List DinhSau; DINH *DinhTruoc; }CANH; typedef struct { COT Cot[MAXCOT]; int SoCot; int TrangThai; List Canh; }DINH; List O Tối ưu cách lưu 1 đỉnh. 3