1.6 Lập trình cấu trúc dữ liệu và giải thuật  (Page 12/46)

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

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.

III.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 OPEN hoặc CLOSE. Khi xét đến một trạng thái Ti bên cạnh việc lưu trữ 3 giá trị cơ bản g,h’, f’ để phản ánh độ tốt của trạng thái đó, A* còn lưu trữ thêm hai thông số sau :

1. Trạng thái cha của trạng thái Ti (ký hiệu là Cha(Ti) : cho biết trạng thái dẫn đến trạng thái Ti. Trong trường hợp có nhiều trạng thái dẫn đến Ti thì chọn Cha(Ti) sao cho chi phí đi từ trạng thái khởi đầu đến Ti là thấp nhất, nghĩa là :

g(Ti) = g(Tcha) + cost(Tcha, Ti) là thấp nhất.

2. Danh sách các trạng thái kế tiếp của Ti : danh sách này lưu trữ các trạng thái kế tiếp Tk của Ti sao cho chi phí đến Tk thông qua Ti từ trạng thái ban đầu là thấp nhất. Thực chất thì danh sách này có thể được tính ra từ thuộc tính Cha của các trạng thái được lưu trữ. Tuy nhiên, việc tính toán này có thể mất nhiều thời gian (khi tập OPEN, CLOSE được mở rộng) nên người ta thường lưu trữ ra một danh sách riêng. Trong thuật toán sau đây, chúng ta sẽ không đề cập đến việc lưu trữ danh sách này. Sau khi hiểu rõ thuật toán, bạn đọc có thể dễ dàng điều chỉnh lại thuật toán để lưu trữ thêm thuộc tính này.

1. Đặt OPEN chỉ chứa T0. Đặt g(T0) = 0, h’(T0) = 0 và f’(T0) = 0. Đặt CLOSE là tập hợp rỗng.

2. Lặp lại các bước sau cho đến khi gặp điều kiện dừng.

2.a. Nếu OPEN rỗng : bài toán vô nghiệm, thoát.

2.b. Ngược lại, chọn Tmax trong OPEN sao cho f’(Tmax) là nhỏ nhất

2.b.1. Lấy Tmax ra khỏi OPEN và đưa Tmax vào CLOSE.

2.b.2. Nếu Tmax chính là TG thì thoát và thông báo lời giải là Tmax.

2.b.3. Nếu Tmax không phải là TG. Tạo ra danh sách tất cả các trạng thái kế tiếp của Tmax. Gọi một trạng thái này là Tk. Với mỗi Tk, làm các bước sau :

2.b.3.1. Tính g(Tk) = g(Tmax) + cost(Tmax, Tk).

2.b.3.2. Nếu tồn tại Tk’ trong OPEN trùng với Tk.

Nếu g(Tk)<g(Tk’) thì

Đặt g(Tk’) = g(Tk)

Tính lại f’(Tk’)

Đặt Cha(Tk’) = Tmax

2.b.3.3. Nếu tồn tại Tk’ trong CLOSE trùng với Tk.

Nếu g(Tk)<g(Tk’) thì

Đặt g(Tk’) = g(Tk)

Tính lại f’(Tk’)

Đặt Cha(Tk’) = Tmax

Lan truyền sự thay đổi giá trị g, f’ cho tất cả các trạng thái kế tiếp của Ti (ở tất cả các cấp) đã được lưu trữ trong CLOSE và OPEN.

2.b.3.4. Nếu Tk chưa xuất hiện trong cả OPEN lẫn CLOSE thì :