Tài liệu Thuật toán và giải thuật - Hoàng Kiếm Part 6 pptx

Sưu tầm bởi: www.daihoc.com.vn

37

III.10. Ứng dụng A* để giải bài toán Ta-canh

Bài toán Ta-canh đã từng là một trò chơi khá phổ biến, đôi lúc người ta còn gọi đây

là bài toán 9-puzzle. Trò chơi bao gồm một hình vuông kích thứơc 3x3 ô. Có 8 ô có

số, mỗi ô có một số từ 1 đến 8. Một ô còn trống. Mỗi lần di chuyển chỉ được di

chuyển một ô nằm cạnh ô trống về phía ô trống. Vấn đề là từ một trạng thái ban đầu

bất kỳ, làm sao đưa được về trạng thái cuối là trạng thái mà các ô được sắp lần lượt

từ 1 đến 8 theo thứ tự từ trái sang phải, từ trên xuống dưới, ô cuối dùng là ô trống.

Cho đến nay, ngoại trừ 2 giải pháp vét cạn và tìm kiếm Heuristic, người ta vẫn chưa

tìm được một thuật toán chính xác, tối ưu để giải bài toán này. Tuy nhiên, cách giải

theo thuật giải A*

lại khá đơn giản và thường tìm được lời giải (nhưng không phải lúc

nào cũng tìm được lời giải). Nhận xét rằng: Tại mỗi thời điểm ta chỉ có tối đa 4 ô có

thể di chuyển. Vấn đề là tại thời điểm đó, ta sẽ chọn lựa di chuyển ô nào? Chẳng hạn

ở hình trên, ta nên di chuyển (1), (2), (6), hay (7) ? Bài toán này hoàn toàn có cấu

trúc thích hợp để có thể giải bằng A* (tổng số trạng thái có thể có của bàn cờ là n2

!

với n là kích thước bàn cờ vì mỗi trạng thái là một hoán vị của tập n2

con số).

Tại một trạng thái đang xét Tk, đặt d(i,j)là số ô cần di chuyển để đưa con số ở ô (i,j)

về đúng vị trí của nó ở trạng thái đích.

Hàm ước lượng h’ tại trạng thái Tk bất kỳ bằng tổng của các d(i,j) sao cho vị trí (i,j)

không phải là ô trống.

Như vậy đối với trạng thái ở hình ban đầu, hàm f(Tk) sẽ có giá trị là

Fk=2+1+3+1+0+1+2+2=12

III.11. Các chiến lược tìm kiếm lai

Chúng ta đã biết qua 4 kiểu tìm kiếm : leo đèo (LĐ), tìm theo chiều sâu (MC), tìm

theo chiều rộng (BR) và tìm kiếm BFS. Bốn kiểu tìm kiếm này có thể được xem như 4

thái cực của không gian liên tục bao gồm các chiến lược tìm kiếm khác nhau. Để giải

thích điều này rõ hơn, sẽ tiện hơn cho chúng ta nếu nhìn một chiến lược tìm kiếm lời

giải dưới hai chiều sau :