Bai tap tin hoc

Giới thiệu và cải tiến giải thuật A*
Giới thiệu thuật giải Best First Search (A*)

Cải tiến thuật giải A* với Fibonacy heap và AVL Tree.

Demo với chương trình giải trò chơi “8 puzzle”
1.Giới thiệu thuật giải Best First Search (A*)
Best First Search có 3 thuật giải con: AT, AKT và A*. Trong đó A* là thuật giải tốt nhất và tiêu biểu nhất.
Mô tả thụât giải A*:
A* duy trì 2 danh sách Open và Close.
Khi bắt đầu chạy, node đầu tiên được đặt vào Open. Các node trong Open này luôn đuợc sắp xếp theo thứ tự từ tốt đến xấu dựa trên giá trị Heuristic của từng node. Do đó Open được gọi là một Hàng đợi có ưu tiên (priority queue).
1.Giới thiệu thuật giải Best First Search (A*) (tt)
Qua mỗi bước, bestNode được lấy ra khỏi Open (bestNode luôn là phần tử đầu của Open). Nếu bestNode là node goal, thuật toán kết thúc. Ngược lại ta phát sinh ra các trạng thái con có thể có của bestNode rồi sau đó đưa bestNode vào danh sách Close.
Các trạng thái con vừa được sinh ra sẽ được đưa vào Open nếu:
Trạng thái con chưa tồn tại trong Open hoặc trong Close.
Trạng thái con đã tồn tại trong Open hoặc Close nhưng nó có Heuristic tốt hơn.
Procedure Best_First_Search;
Begin
open:=[start]; close:=[];
While (open<>[]) Do
Begin
Lấy phần tử đầu tiên X khỏi Open
If X là goal then return path từ start đến X
sinh ra các nút con của X;
For mỗi nút con Y của X Do
Case Y không có trong open hay close:
gán giá trị heuristic cho Y;
đưa Y vào open
Case Y đã có trong Open:
if đến được Y bằng một path ngắn hơn then gán path ngắn hơn này cho Y trên Open
Case Y đã có trong close:
if đến được Y bằng một path ngắn hơn then
xóa Y khỏi danh sách Close;
thêm Y vào danh sách Open;
EndIf;
EndFor
Đưa X vào close;
Xếp thứ tự các trạng thái trên Open theo giá trị Heuristic
EndWhile
return failure;
EndProc;
2.Cải tiến thuật toán A* với Fibonacy heap và AVL Tree.
Chúng ta có thể nâng cấp giải thuật A* trên bằng cách áp dụng Fib heap cho Open và AVL tree cho Close thay cho danh sách liên kết thường.
Đối với Fib heap, chi phí thêm phần tử là Const và chi phí lấy phần tử tốt nhất là O(log n) trong khi priority queue thường tốn O(n) để thêm phần tử và tốn Const để lấy phần tử tốt nhất.
Đối với AVL tree thì chi phí tìm kiếm và thêm phần tử đều chỉ tốn O(log n) trong khi priority queue thường tốn đến O(n) cho 2 tác vụ trên.
3.Demo với chương trình giải trò chơi “8 puzzle”
Một số đề bài mẫu để demo:
Dễ:
[164][583][720] => [164][503][782] độ sâu 2
[134][805][726] => [123][804][765] độ sâu 6

Trung bình:
[231][708][654] => [123][804][765] độ sâu 14

Khó:
[240][185][367] => [123][456][780] độ sâu 26
[876][105][234] => [123][804][765] độ sâu 28

Cực khó:
[876][041][253] => [012][345][678] độ sâu 31
[806][547][231] => [012][345][678] độ sâu 31