Tìm hiểu giải thuật A* , ứng dụng giải bài toán 8-puzzle
Nội dung
Giao diện
Sử dụng A* vào bài toán
Giải thuật A*
Phân tích bài toán
Giới thiệu bài toán N-puzlle
Bài toán 8-puzzle

Bài toán gồm một bảng 3×3 với các ô số được đánh từ 1->8 và một ô trống. Ở trạng thái bắt đầu, các ô được sắp đặt ngẫu
nhiên, và nhiệm vụ của người giải là tìm cách di chuyển các ô sao cho các con số về đúng thứ tự, bài toán đặt ra ở đây là tìm
phương án tối ưu sao cho số lần di chuyển là ít nhất. Trạng thái đầu Trạng thái đích
1 5 7
2 3 6
4 8
1 2 3
4 5 6
7 8
Bài toán 8-puzzle

Điều đầu tiên cần phải quan tâm để giải bài toán này là xác định trạng thái đích. Trạng thái đích được xác định dựa trên trạng
thái đầu. Vậy trạng thái đích được xác định như thế nào.
1 5 7
2 3 6
4 8

4 8
Tổng quan về A*

Trong khoa học máy tính, A* (đọc là A sao) là một thuật toán tìm kiếm trong đồ thị.

Thuật toán này tìm một đường đi từ một nút khởi đầu tới một nút đích cho trước (hoặc tới một nút thỏa
mãn một điều kiện đích.

Thuật toán này sử dụng một "đánh giá heuristic" để xếp loại từng nút theo ước lượng về tuyến đường tốt
nhất đi qua nút đó. Thuật toán này duyệt các nút theo thứ tự của đánh giá heuristic này. Do đó, thuật toán
A* là một ví dụ của tìm kiếm theo lựa chọn tốt nhất (best-first search).
Tổng quan về A*

Sử dụng hàm đánh giá f(n) = g(n) + h(n) trong đó :

g(n) = chi phí từ nút gốc cho đến nút hiện tại n

h(n) = chi phí ước lượng từ nút hiện tại n tới đích

f(n) = chi phí tổng thể ước lượng của đường đi qua nút hiện tại n đến đích.

Giải thuat A với hàm heuristic h(n) luôn luôn giá trị thực đi từ n đến goal.
≤
Tổng quan về A*
Tổng quan về A*
Tổng quan về A*
Tổng quan về A*
Tổng quan về A*
Tổng quan về A*
Tổng quan về A*

1 2 3
4 5 6
7 8
Trong bảng số 3×3 trên, để di chuyển ô số 5 vào đúng vị trí ta cần di chuyển nó 1 lần, để di chuyển ô số 7 về đúng vị trí ta cần
cần 4 lần (qua 4 ô khác).
| row1 - row2| + |column1 – column2|
Với :
RowIndex=Index/m
ColIndex=Index% m
Tổng quan về A*

Ví dụ ô số 7 có thứ tự trong bảng là 6 (tính từ 0 với m là cạnh) ta có row = 6 / 3 = 2, col = 6 % 3 = 0.

h = 0+1+4+2+2+0+1+1+1 = 12
Không gian trạng thái*
Cảm ơn các bạn đã lắng nghe!