Đề tài:

GVHD: Phạm Văn Hải
Đề tài:

GVHD: Phạm Văn Hải
BÀI TẬP LỚN AI
Áp dụng thuật toán A* vào trò chơi PUZZLE
Áp dụng thuật toán A* vào trò chơi PUZZLE
I.Giới thiệu thuật giải A*
A
*
là một giải thuật tìm kiếm sử dụng tri thức thức bổ sung để gán giá trị nhãn cho mỗi nút
•
Nếu không gian các trạng thái là hữu hạn và có giải pháp để tránh việc xét lại các trạng thái thì
A *
là hoàn chỉnh nhưng không đảm bảo tối ưu.
•
Nếu không gian các trạng thái là hữu hạn và không có giải pháp để tránh việc xét lại các trạng
thái thì A* là không hoàn chỉnh.
•
Nếu không gian các trạng thái là vô hạn thì A* là không hoàn chỉnh.
I.Giới thiệu thuật giải A*
•
Độ phức tạp và hiệu quả của giải thuật A* phụ thuộc rất nhiều vào hàm heuristic.
•
Độ phức tạp thời gian tính toán của A* trong trường hợp xấu nhất là một hàm mũ, nhưng nó sẽ
là một hàm đa thức nếu hàm heuristic thỏa mãn điều kiên:
|h(n)-h*(n)| ≤ O(log(h*(n)))
Trong đó h*(n) là chí phí thực tế đi từ nút n đến nút đích
II. Ví dụ bài toán n-puzzle

g =2
h =4
f =6
g=2
h=2
f=4
3 1 2
4 7 5
6 8
g =2
h =4
f =6
II. Ví dụ Bài toán n-puzzle
3 1 2
4 5
6 7 8
3 2
4 1 5
6 7 8
3 1 2
4 5
6 7 8
1 2
3 4 5
6 7 8
g=3
h=1
f=4
g=3
h=3

Bước 2 : cài đặt A*
- Tạo hai trạng bắt đầu và kết thúc beginState, endState
- Để lưu trữ không gian trạng thái ta dùng một ArrayList <State> arrayState
- Ở mỗi bước lặp chúng ta chọn ra trạng thái có giá trị cost nhỏ nhất, đây là giá trị được tính bằng hàm lượng
giá, sau đó sinh ra các trạng thái con của nó rồi nạp vào arrayState
III. Áp dụng A* vào trò chơi Puzzle
3. Hàm lượng giá
Một hàm luợng giá h1(n) đuợc xem là ưu thế hơn hàm lựơng giá h2(n) khi h1(n), h2(n) đều là
các hàm ước lượng chấp nhận được và h1(n) ≥h2(n) đối với nút n. Hàm lượng giá h(n) là chấp nhận
được khi h(n)<h*(n) trong dó h*(n) là chí phí thực tế đi từ nút n đến nút đích
Trong trò chơi này chúng tôi đề xuất ba hàm heuristic như sau:
III. Áp dụng A* vào trò chơi Puzzle
3. Hàm lượng giá

h1(n)= số ô nằm sai vị trí so với trạng thái đích
Ví dụ:
III. Áp dụng A* vào trò chơi Puzzle
3. Hàm lượng giá

h2(n) = tổng khoảng cách ngắn nhất của các ô đến vị trí đúng của nó
ví dụ:
III. Áp dụng A* vào trò chơi Puzzle
3. Hàm lượng giá

Nếu ta lưu giá trị các ô của trạng thái vào mảng một chiều theo thứ tự từ trái sang phải và từ trên xuống
dưới như sau:

Khí đó ta có hàm lượng giá được tính như sau:

trong đó size là kích thước của lưới ô vuông.