💡
Tiếp tục với thuật toán A ở bài trước, ở demo này, mình vẫn dùng thuật toán A để mô phỏng cách máy tính tìm ra cách giải cho trò chơi đẩy số.
Ngày bé, hẳn ai trong chúng ta có lẽ cũng đã từng chơi trò chơi này…
Có một bảng số 3×3 ô vuông và 1 ô trống, chúng ta có thể đẩy các ô bên cạnh vào ô trống. Luật chơi là phải làm cách nào đó từ một trạng thái START, di chuyển các ô số bằng cách đẩy vào ô trống để đạt được trạng tại TARGET.
Đây thực chất cũng là một bài toán tìm đường đi:
Khởi đầu từ trạng thái START
Tìm tất cả các con đường đi có thể từ điểm hiện tại (tất cả trạng thái đạt được từ trạng thái hiện tại)
Mỗi trạng thái, ta cập nhật lại khoảng cách và ước lượng (heuristic)
Heuristic được áp dụng ở đây là tổng số ô sai biệt của trạng thái hiện tại so với trạng thái TARGET.