Thuật toán tìm kiếm leo đồi
N.V.T
Trong lập trình giải toán, các thuật toán tìm kiếmđóng một vai trò cực kỳ quan trọng và rất
quen thuộc đối với chúng ta. Trongbài viết này, xin trình bày với bạn đọc một trong số các
thuật toán tìm kiếmphổ biến: "Thuật toán leo đồi (Hill Climbing Search).
Trước hết, ta nghiên cứu bài toán sau: Trò chơi n
2
-1số (n ∈ N, n > 1).
Bài toán: Có n
2
-1 số mangcác giá trị từ 1 tới n
2
-1 được sắp xếp vào một lưới các ô vuông
kíchthước n x n. Mỗi số đó được gọi là một quân cờ và lướiô đó được gọi là bàn cờ. Có
một vị trí của bàn cờ bỏ trống. Mỗi lần di chuyểnquân, người chơi được phép chuyển một
quân ở vị trí ô tiếp giáp cạnh với ôtrống vào ô trống.
Yêucầu: Từ mộttrạng thái ban đầu (sự sắp xếp ban đầu của các quân trên bàn cờ), hãy thực
hiệncác nước đi hợp lệ để thu được trạng thái kết thúc (trạng thái đích cần đạtđược).
Vídụ: với trò chơi 8 số ta minh họa trạng thái ban đầu và trạng thái kết thúcqua các hình vẽ
dưới đây:
Đểgiải bài toán này, chúng ta sẽ nghĩ ngay tới việc xây dựng một cây tìm kiếm màgốc của
cây tương ứng với trạng thái xuất phát của bàn cờ. Các đỉnh khác củacây tương ứng với
các trạng thái thu được do việc thực hiện các nước đi hợp lệ(các nước đi được phép thực
hiện là: lên trên, xuống dưới, sang trái và sangphải). Với ví dụ trên, ta có cây tìm kiếm sau:
Tiếpđó, ta chỉ việc áp dụng các thuật toán thông dụng như: thuật toán tìm kiếm theochiều
rộng hoặc thuật toán tìm kiếmtheo chiều sâu để tìm ra lời giải.
Việcsuy nghĩ như trên xem ra có tính khả thi (đơn giản, dễ cài đặt), tuy nhiên, dễnhận thấy
rằng nếu số n lớn hơn, ta sẽ phải phát triển một số quá lớn các trạngthái trước khi phát hiện
ra trạng thái đích. Những hạn chế về mặt thời gian và dung lượng bộ nhớ không cho
phépthực hiện điều đó.
Trongthực tế, có nhiều bài toán mà số các trạng thái của nó là rất lớn (như cờ vua,cờ

Phầntiếp theo sẽ trình bày cụ thể thuật toán để giải bài toán trên. Trong bài toánnày, ta sẽ
sử dụng hàm đánh giá ký hiệu là h với ý nghĩa: h(u) cho biết số cácchữ số trong trạng thái
u không trùng với vị trí của nó trong trạng thái đích.Trạng thái có tiềm năng dẫn tới đích
nhanh nhất (được ưu tiên phát triển trước)là trạng thái có hàm đánh giá h đạt giá trị min.
Thuậttoán cho trò chơi n
2
-1 số được mô tả như sau :
Input: Trạng thái ban đầu u
0
và trạng thái đích u
t
1. P:={u
0
} ;{P để lưu các trạng thái chờphát triển được tổ chức dưới dạng Stack }
Q:=Φ ;{để lưu các trạng thái đãphát triển được tổ chức dưới dạng hàng đợi Queue}
P:= Φ ;{P để lưu tạm thời các trạngthái kề với trạng thái đang xét}
found:=false;
2. While (P # y) and (not found) do
2.1.Loại bỏ trạng thái u ở đỉnh stack P và đặt nó vào hàng đợi Q:
Pop(P,u);
Ađ(u,Q);
2.2.if u=u
t
then found:= true
else
For v ẻ kề (u) do
if(v ẽ P U Q) and (h(v)<= max {h(w)| w ờ P U Q } then
Begin
father (v):=u;
Ađ (v,P?);

. Anh ta
chọn một đỉnh cao nhất trong số các đỉnhmà anh ta có thể đến được (từ vị trí đang đứng)