Tìm hiểu thuật toán Heuristic
Nguyễn Văn Sơn
Đối với nhiều bài toán, hoặc không có lời giải, hoặc độ phức tạp tính toán là hàm mũ, hoặc
là bài toán NP-đầy đủ…, có nghĩa là nó không có lời giải khả thi, thì thông thường thay vì
tìm lời giải tối ưu cho chúng, chúng ta cố gắng tìm lời giải có thể chấp nhận được, đáp ứng
được yêu cầu của thực tế. Các lời giải này chính là các thuật toán heuristic.
Các thuật toán tìm kiếm luôn luôn đóng vai trò quan trọng trong việc giải các bài toán tin
học. Các thuật toán loại này rất phong phú, có thể kể đến như: vét cạn, đệ quy quay lui,
nhánh cận, nhị phân…Tuy nhiên, khi gặp những bài toán có không gian tìm kiếm lớn (đặc
biệt trong các trò chơi cờ) thì các thuật toán tìm kiếm thông thường không cho kết quả
hoặc kết quả không tối ưu (do những hạn chế về thời gian và bộ nhớ). Một hướng tiếp cận
độc đáo có thể đáp ứng được đòi hỏi cho nhiều bài toán loại này là dùng thuật toán
Heuristic.
Thuật ngữ Heuristic xuất phát từ tiếng Hy Lạp là ″heuriskein″ có nghĩa là ″tìm kiếm″ hoặc
″phát minh″. Chắc chắn chúng ta vẫn còn nhớ câu chuyện về nhà bác học Archimedes. Khi
phát hiện ra định luật về trọng lượng riêng, ông đã trần truồng chạy ra đường và kêu lớn
″tôi tìm ra rồi″. Thực ra, lúc đó ông đã kêu lên ″heureka″, về sau này người ta đổi từ này
thành ″eureka″.
Thuật ngữ Heuristic được Feigenbaum Feldman định nghĩa như sau: ″Heuristic là các quy
tắc, phương pháp, chiến lược, mẹo giải hay phương cách nào đó nhằm làm giảm khối
lượng tìm kiếm lời giải trong không gian bài toán cực lớn″.
Tư tưởng chính để giảm khối lượng tìm kiếm là thay vì ″loại bỏ các hướng tìm kiếm chắc
chắn không dẫn đến lời giải″, ta hãy ″chọn đi theo hướng có nhiều khả năng dẫn đến lời
giải″.
Do thuật toán Heuristic được con người sử dụng thường mang đặc trưng của những gợi ý
hay lời khuyên, nên các phương pháp dựa trên Heuristic đôi khi không chỉ ra con đường
trực tiếp để đạt tới mục đích.
Nhiều kết quả nghiên cứu trong trí tuệ nhân tạo cho thấy rằng, tuy có nhiều điểm mạnh nổi
bật, nhưng trong một vài lĩnh vực nghiên cứu nào đó thì các phương pháp Heuristic còn
bộc lộ những điểm yếu nhất định. Điều phức tạp chính là vì mọi chương trình máy tính
phải đảm bảo chắc chắn kết thúc công việc (theo định nghĩa một thuật toán phải đảm bảo

tính đúng và tính dừng). Vì vậy, nếu nói rằng một chương trình nào đó sử dụng Heuristic
thì kết luận về tính dừng chỉ đúng trong đa số các trường hợp. Do đó, trong phần lớn
trường hợp giải quyết bài toán, các chương trình Heuristic có lúc cho kết quả mong đợi,
đôi khi lại không.
Các Heuristic không chỉ tác động đến các chiến lược tìm kiếm, mà còn ảnh hưởng quyết
định tới các chiến lược điều khiển (hướng tìm kiếm trong không gian bài toán và xử lý
cạnh tranh). Đối với những bài toán trí tuệ phức tạp, số khả năng có thể lớn tới mức không
thể có một máy tính nào dầu hiện đại đến mấy đáp ứng nổi. Do vậy, thủ tục duyệt toàn thể
không thể chấp nhận được. Trong phần lớn các bài toán chứng minh định lý sử dụng logic,
số khả năng cần phải xét trở lên vô hạn. Việc lựa chọn một nước đi tốt nhất trong trò chơi
đòi hỏi phải tìm kiếm trong khoảng 10
40
khả năng khác nhau, thậm chí đối với chơi cờ, số
khả năng cỡ 10
120
. Một cách xử lý tốt trong những trường hợp này là sử dụng thao tác rút
gọn các hướng tìm kiếm.
Vấn đề quan trọng là ở chỗ, chúng ta biết khai thác khéo léo thông tin tại mỗi trạng thái để
tìm ra thứ tự ưu tiên và đẩy nhanh quá trình tìm kiếm. Thông thường ta gắn với mỗi trạng
thái của bài toán với một số đo (một hàm đánh giá) nào đó để đánh giá mức độ gần đích
của nó.
Một kỹ thuật Heuristic được coi là hợp lý khi nó cho phép tiến hành đánh giá các khả
năng để làm rõ khả năng nào tốt hơn các khả năng còn lại. Những ví dụ điển hình về các
hàm đánh giá là các ước lượng khoảng cách đường chim bay từ một đỉnh nào tới đỉnh đỉnh
đích trong bài toán xác định đường đi ngắn nhất, hay các đánh giá ước lượng mức độ quan
trọng của các quân cờ trong mỗi thế cờ dựa trên tổ hợp các trọng số của chúng…
Để minh hoạ cho thuật toán Heuristic, chúng ta cùng nghiên cứu bài toán sau đây: bài toán
8-puzzle (đây là một trò chơi được một nhà thiết kế trò chơi nổi tiếng của Mỹ là Sam Loyd
phát minh vào cuối những năm 1870; nó đã trở thành một trò chơi được cực kỳ được ưa
chuộng ở Mỹ vào thời điểm đó).

Bài toán:
Có 8 số mang các giá trị từ 1 tới 8 được sắp xếp vào một bảng các ô vuông kích thước 3x3.
Mỗi số đó được xếp vào một ô, có một ô của bảng bỏ trống. Cho trước hai bảng các con số
(thể hiện cho trạng thái nguồn và trạng thái đích của bài toán), hãy chỉ ra một dãy các phép
chuyển các con số (nếu có) để thu được một một bảng (trạng thái đích) từ bảng còn lại
(trạng thái nguồn). Bạn chỉ được phép chuyển các con số lên trên, xuống dưới, sang trái và
sang phải từ một ô có con số sang ô trống (bài toán này còn có dạng phức tạp hơn là 15-
puzzle).
Rõ ràng, đối với bài toán này nếu dùng phương pháp duyệt toàn bộ thì không hợp lý. Để
giảm không gian tìm kiếm, ta xây dựng một thứ tự ưu tiên để duyệt các hướng đi. Do đó,
khi duyệt thứ tự ưu tiên theo thứ tự giảm dần của khả năng dẫn đến lời giải, ta sẽ có cơ hội
tiếp cận đến lời giải nhanh hơn là duyệt một cách mù quáng!.
Tuy nhiên, điểm mấu chốt là: làm thế nào để đánh giá khả năng dẫn đến lời giải của một
hướng đi? Nếu đánh giá này chính xác, chúng ta sẽ tìm thấy lời giải nhanh hơn còn nếu
không thì trong trường hợp xấu nhất, lại trở về vét cạn toàn bộ.
Trong bài toán này, ta sử dụng hàm đánh giá ký hiệu là h với ý nghĩa: h(u) cho biết số các
chữ số trong trạng thái u không trùng với vị trí của nó trong trạng thái đích. Khi đó, trạng
thái có tiềm năng dẫn tới đích nhanh nhất là trạng thái có hàm đánh giá h đạt giá trị min.
Thuật toán cho trò chơi 8-puzzle:
Một số ký hiệu
- Tập P các trạng thái chờ quyết định được tổ chức dưới dạng stack.
- Tập Q các trạng thái đã phát triển được tổ chức dưới dạng hàng đợi.
- Tập P′ lưu trữ tạm thời các trạng thái kề v của u khi ta phát triển một đỉnh u (v thu được
từ u thông qua một phép di chuyển con số).
- Biến found.
- Hàm father.
Thuật toán:
Input: trạng thái ban đầu u
0
và trạng thái đích u

t
1.P← { u
0
} ; Q ← Φ ; found ← false; P′ ← Φ ;
2.While(P ≠ Φ ) and (not found) do
2.1. Loại trạng thái u ở đỉnh stack P và đặt nó vào Q:
Pop(P,u);
Ađ(u,Q);
2.2. If u=u
t
then found ← true
Else for v thuộc kề(u) do
If v không thuộc P hợp Q then
Begin
father (v) ← u;
Ađ (v,P′);
End;
If P′ ≠ Φ then
Begin
Sắp xếp P′ theo thứ tự tăng của hàm h. Chuyển P′ vào đỉnh stack P sao cho trạng thái nhiều
hứa hẹn nhất (có giá trị hàm h nhỏ nhất) ở đỉnh của P.
End;
(Chú ý: Sau khi chuyển P′ vào đỉnh stack P thì P′ trở thành rỗng.)
Output: Nếu found = false thì bài toán vô nghiệm.
Nếu found = true thì nghiệm là đường đi từ u
0
tới u
t
được xác định bằng cách sử dụng hàm
father.

Cây tìm kiếm được hình thành do sử dụng thuật toán Heuristic ở trên được minh hoạ như
trong hình vẽ dưới (nét đậm thể hướng tìm kiếm), số ghi cạnh các đỉnh là giá trị của hàm h
tại đỉnh đó.
Minh hoạ cây tìm kiếm cho trò chơi 8-puzzle bằng thuật toán Heuristic
Chương trình minh hoạ cho thuật toán Heuristic giải quyết bài toán ở dạng tổng quát được
viết bằng ngôn ngữ Pascal như dưới đây.
Dữ liệu vào cho trong file SO.INP: dòng đầu là một số n (1<N
2
-1)-puzzle). Tiếp theo là hai
nhóm dòng, mỗi nhóm gồm n dòng (gồm các số được ghi cách nhau một dấu cách) lần lượt
minh hoạ cho bảng số nguồn và bảng số đích. Dữ liệu ra được ghi vào file SO.OUT gồm
nhiều nhóm dòng, mỗi nhóm gồm n+1 dòng: bắt đầu là một số chỉ thứ tự của bảng số được
phát triển tính từ bảng số nguồn và n dòng tiếp theo minh hoạ cho bảng số đó. Nếu không
tồn tại lời giải thì ghi một số 0.
Ví dụ:
SO.INP
3
2 6 3
1 6 4
7 0 5
1 2 3
8 0 4
7 6 5
SO.OUT
1
2 8 3
1 4
7 6 5
2
2 3

1 8 4
7 6 5
3
2 3
1 8 4
7 6 5
4
1 2 3
8 4
7 6 5
5
1 2 3
8 4
6 5
Sau đây là toàn văn chương trình:
PROGRAM heuristic;
{$B-}{$M 65000,0,655360}
Uses Crt;
Const Max=6;
fi=′SO.INP′;
fo=′SO.OUT′;
Type Vec=Array[1..Max,1..Max] of byte;
Item=record Ma:vec;Father,child:longint; End;
Pointer =^node; Node=record Infor:item;
Next:pointer; End;
Node1=array[1..4] of vec;Tp=0..10;
Var
U :item; Id :longint;
Front,rear,top:pointer; P :node1;
Dau,dich :vec; Found :boolean;

N :2..10; So_pts :tp;
I,j :tp;
ff:text;
PROCEDURE Vi_tri(a:vec;var k,t:TP);
Var i,j:1..max;
Begin For i:=1 to n do For J:=1 to n do
If a[i,j]=0 then
Begin K:=i; T:=j; Exit; End;
End;
{minh hoa cho cac phep di chuyen so}
PROCEDURE Left(a:vec;var lef:vec;i,j:tp);
Begin A[i,j]:=A[i,j+1];A[i,j+1]:=0; Lef:=A;
End;
PROCEDURE Right(a:vec;var righ:vec;i,j:tp);
Begin A[i,j]:=A[i,j-1]; A[i,j-1]:=0; Righ:=A;
End;
PROCEDURE Up(a:vec;var u:vec;i,j:tp);
Begin A[i,j]:=A[i+1,j]; A[i+1,j]:=0; U:=A;