Tài liệu hướng dẫn thực hành
1
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:
Tài liệu hướng dẫn thực hành
2
= 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ịHcủ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++
Tài liệu hướng dẫn thực hành
3
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 <DINH> DinhSau;
DINH *DinhTruoc;
}CANH;
typedef struct {
COT Cot[MAXCOT];
int SoCot;
int TrangThai;
List <CANH> Canh;
}DINH;
List <DINH> O
¾Tốiưu cách lưu 1 đỉnh.