Giáo trình Trí tuệ nhân tạo (Phần 1)

), vμ có độ phức tạp không gian lμ O(biểu diễn) (nh− tìm kiếm theo độ sâu). Nói 
chung, chúng ta nên áp dụng tìm kiếm sâu lặp cho các vấn đề có không gian trạng thái 
lớn vμ độ sâu của nghiệm không biết tr−ớc. 
38 
IV. Quy vấn đề về các vấn đề con 
Chúng ta đã nghiên cứu việc biểu diễn vấn đề thông qua các trạng thái vμ các toán tử. 
Khi đó việc tìm nghiệm của vấn đề đ−ợc quy về việc tìm đ−ờng trong không gian trạng 
thái. Trong mục nμy chúng ta sẽ nghiên cứu một ph−ơng pháp luận khác để giải quyết 
vấn đề, dựa trên việc quy vấn đề về các vấn đề con. Quy vấn đề về các vấn đề con (còn 
gọi lμ rút gọn vấn đề) lμ một ph−ơng pháp đ−ợc sử dụng rộng rãi nhất để giải quyết các 
vấn đề. Trong đời sống hμng ngμy, cũng nh− trong khoa học kỹ thuật, mỗi khi gặp một 
vấn đề cần giải quyết, ta vẫn th−ờng cố gắng tìm cách đ−a nó về các vấn đề đơn giản 
hơn. Quá trình rút gọn vấn đề sẽ đ−ợc tiếp tục cho tới khi ta dẫn tới các vấn đề con có 
thể giải quyết đ−ợc dễ dμng. Sau đây chúng ta xét một số vấn đề. 
 Vấn đề tính tích phân bất định 
Giả sử ta cần tính một tích phân bất định, chẳng hạn ∫(xex + x3) dx. Quá trình chúng ta 
vẫn th−ờng lμm để tính tích phân bất định lμ nh− sau. Sử dụng các quy tắc tính tích 
phân (quy tắc tính tích phân của một tổng, quy tắc tính tích phân từng phần...), sử dụng 
các phép biến đổi biến số, các phép biến đổi các hμm (chẳng hạn, các phép biến đổi 
l−ợng giác),... để đ−a tích phân cần tính về tích phân của các hμm số sơ cấp mμ chúng 
ta đã biết cách tính. Chẳng hạn, đối với tích phân ∫(xex + x3) dx, áp dụng quy tắc tích 
phân của tổng ta đ−a về hai tích phân ∫xexdx vμ ∫x3dx. áp dụng quy tắc tích phân từng 
phần ta đ−a tích phân ∫xexdx về tích phân ∫exdx. Quá trình trên có thể biểu diễn bởi đồ 
thị trong hình 3.5. 
Hình 3.5 Quy một số tích phân về tích phân cơ bản 
Các tích phân ∫exdx vμ ∫x3dx lμ các tích phân cơ bản đã có trong bảng tích phân. Kết 
hợp các kết quả của các tích phân cơ bản, ta nhận đ−ợc kết quả của tích phân đã cho. 
Chúng ta có thể biểu diễn việc quy một vấn đề về các vấn đề con cơ bởi các trạng thái 
vμ các toán tử. ở đây, bμi toán cần giải lμ trạng thái ban đầu. Mỗi cách quy bμi toán về 
các bμi toán con đ−ợc biểu diễn bởi một toán tử, toán tử A→B, C biểu diễn việc quy 
bμi toán A về hai bμi toán B vμ C. Chẳng hạn, đối với bμi toán tính tích phân bất định, 
ta có thể xác định các toán tử dạng: 
∫(f1 + f2) dx → ∫f1 dx, ∫f2 dx vμ ∫u dv → ∫v du 
Các trạng thái kết thúc lμ các bμi toán sơ cấp (các bμi toán đã biết cách giải). Chẳng 
hạn, trong bμi toán tính tích phân, các tích phân cơ bản lμ các trạng thái kết thúc. Một 
39 
điều cần l−u ý lμ, trong không gian trạng thái biểu diễn việc quy vấn đề về các vấn đề 
con, các toán tử có thể lμ đa trị, nó biến đổi một trạng thái thμnh nhiều trạng thái khác. 
 Vấn đề tìm đ−ờng đi trên bản đồ giao thông 
Bμi toán nμy đã đ−ợc phát triển nh− bμi toán tìm đ−ờng đi trong không gian trạng thái 
(xem 3.1), trong đó mỗi trạng thái ứng với một thμnh phố, mỗi toán tử ứng với một con 
đ−ờng nối, nối thμnh phố nμy với thμnh phố khác. Bây giờ ta đ−a ra một cách biểu diễn 
khác dựa trên việc quy vấn đề về các vấn đề con. 
Hình 3.6 
Giả sử ta có bản đồ giao thông trong một vùng lãnh thổ (xem hình 3.6). Giả sử ta cần 
tìm đ−ờng đi từ thμnh phố A tới thμnh phố B. Có con sông chảy qua hai thμnh phố E vμ 
G vμ có cầu qua sông ở mỗi thμnh phố đó. Mọi đ−ờng đi từ A đến B chỉ có thể qua E 
hoặc G. Nh− vậy bμi toán tìm đ−ờng đi từ A đến B đ−ợc quy về: 
1) Bμi toán tìm đ−ờng đi từ A đến B qua E (hoặc) 
2) Bμi toán tìm đ−ờng đi từ A đến b qua G. 
Mỗi một trong hai bμi toán trên lại có thể phân nhỏ nh− sau 
1) Bμi toán tìm đ−ờng đi từ A đến B qua E đ−ợc quy về: 
1.1 Tìm đ−ờng đi từ A đến E (vμ) 
1.2 Tìm đ−ờng đi từ E đến B. 
2) Bμi toán tìm đ−ờng đi từ A đến B qua G đ−ợc quy về: 
2.1 Tìm đ−ờng đi từ A đến G (vμ) 
2.2 Tìm đ−ờng đi từ G đến B. 
Quá trình rút gọn vấn đề nh− trên có thể biểu diễn d−ới dạng đồ thị (đồ thị vμ/hoặc) 
trong hình 3.7. ở đây mỗi bμi toán tìm đ−ờng đi từ một thμnh phố tới một thμnh phố 
khác ứng với một trạng thái. Các trạng thái kết thúc lμ các trạng thái ứng với các bμi 
toán tìm đ−ờng đi, chẳng hạn từ A đến C, hoặc từ D đến E, bởi vì đã có đ−ờng nối A 
với C, nối D với E. 
40 
Hình 3.7 Đồ thị vμ/hoặc của vấn đề tìm đ−ờng đi 
V. đồ thị 
Không gian trạng thái mô tả việc quy vấn đề về các vấn đề con có thể biểu diễn d−ới 
dạng đồ thị định h−ớng đặc biệt đ−ợc gọi lμ đồ thị vμ/hoặc. Đồ thị nμy đ−ợc xây dựng 
nh− sau: 
Mỗi bμi toán ứng với một đỉnh của đồ thị. Nếu có một toán tử quy một bμi toán về một 
bμi toán khác, chẳng hạn R : a → b, thì trong đồ thị sẽ có cung gán nhãn đi từ đỉnh a 
tới đỉnh b. Đối với mỗi toán tử quy một bμi toán về một số bμi toán con, chẳng hạn R : 
a → b, c, d ta đ−a vμo một đỉnh mới a1, đỉnh nμy biểu diễn tập các bμi toán con {b, c, 
d} vμ toán tử R : a → b, c, d đ−ợc biểu diễn bởi đồ thị hình 3.8. 
Hình 3.8 Đồ thị biểu diễn toán tử R : a → b, c, d 
Ví dụ: Giả sử chúng ta có không gian trạng thái sau: 
 Trạng thái ban đầu (bμi toán cần giải) lμ a. 
 Tập các toán tử gồm: 
R1 : a → d, e, f 
R2 : a → d, k 
R3 : a → g, h 
R4 : d → b, c 
41 
R5 : f → i 
R6 : f → c, g 
R7 : k → e, l 
R8 : k → h 
• Tập các trạng thái kết thúc (các bμi toán sơ cấp) lμ T = {b, c, e, g}. 
Không gian trạng thái trên có thể biểu diễn bởi đồ thị vμ/hoặc trong hình 3.9. Trong đồ 
thị đó, các đỉnh chẳng hạn a, f, k hoặc a1, a2, a3 đ−ợc gọi lμ đỉnh. Lý do lμ, đỉnh a1 biểu 
diễn tập các bμi toán {d, e, f} vμ a1 đ−ợc giải quyết nếu d vμ e vμ f đ−ợc giải quyết. 
Còn tại đỉnh a, ta có các toán tử R1, R2, R3 quy bμi toán a về các bμi toán con khác 
nhau, do đó a đ−ợc giải quyết nếu hoặc a1 = {d, e, f}, hoặc a2 = {d, k}, hoặc a3 = {g, 
h} đ−ợc giải quyết. 
Hình 3.9 Một đồ thị vμ/hoặc 
Ng−ời ta th−ờng sử dụng đồ thị vμ/hoặc ở dạng rút gọn. Chẳng hạn, đồ thị vμ/hoặc 
trong hình 3.9 có thể rút gọn thμnh đồ thị trong hình 3.10. Trong đồ thị rút gọn nμy, ta 
sẽ nói chẳng hạn d, e, f lμ các đỉnh kề đỉnh a theo toán tử R1, còn d, k lμ các đỉnh kề a 
theo toán tử R2. 
Khi đã có các toán tử rút gọn vấn đề, thì bằng cách áp dụng liên tiếp các toán tử, ta có 
thể đ−a bμi toán cần giải về một tập các bμi toán con. Chẳng hạn, trong ví dụ trên nếu 
ta áp dụng các toán tử R1, R4, R6, ta sẽ quy bμi toán a về tập các bμi toán con {b, c, e, 
g}, tất cả các bμi toán con nμy đều lμ sơ cấp. Từ các toán tử R1, R4 vμ R6 ta xây dựng 
đ−ợc một cây trong hình 1.11a, cây nμy đ−ợc gọi lμ cây nghiệm. Cây nghiệm đ−ợc 
định nghĩa nh− sau: 
Cây nghiệm lμ một cây, trong đó: 
 Gốc của cây ứng với bμi toán cần giải. 
 Tất cả các lá của cây lμ các đỉnh kết thúc (đỉnh ứng với các bμi toán sơ cấp). 
42 
 Nếu u lμ đỉnh trong của cây, thì các đỉnh con của u lμ các đỉnh kề u theo một toán 
tử nμo đó. 
Các đỉnh của đồ thị vμ/hoặc sẽ đ−ợc gắn nhãn giải đ−ợc hoặc không giải đ−ợc. 
Hình 3.10 Đồ thị rút gọn của đồ thị trong hình 3.9 
Hình 3.11 Các cây nghiệm 
Các đỉnh giải đ−ợc đ−ợc xác định đệ quy nh− sau: 
 Các đỉnh kết thúc lμ các đỉnh giải đ−ợc. 
 Nếu u không phải lμ đỉnh kết thúc, nh−ng có một toán tử R sao cho tất cả các đỉnh 
kề u theo R đều giải đ−ợc thì u giải đ−ợc. 
Các đỉnh không giải đ−ợc đ−ợc xác định đệ quy nh− sau: 
 Các đỉnh không phải lμ đỉnh kết thúc vμ không có đỉnh kề, lμ các đỉnh không giải 
đ−ợc. 
 Nếu u không phải lμ đỉnh kết thúc vμ với mọi toán tử R áp dụng đ−ợc tại u đều có 
một đỉnh v kề u theo R không giải đ−ợc, thì u không giải đ−ợc. 
Ta có nhận xét rằng, nếu bμi toán a giải đ−ợc thì sẽ có một cây nghiệm gốc a, vμ ng−ợc 
lại nếu có một cây nghiệm gốc a thì a giải đ−ợc. Hiển nhiên lμ, một bμi toán giải đ−ợc 
có thể có nhiều cây nghiệm, mỗi cây nghiệm biểu diễn một cách giải bμi toán đó. 
Chẳng hạn trong ví dụ đã nêu, bμi toán a có hai cây nghiệm trong hình 3.11. 
Thứ tự giải các bμi toán con trong một cây nghiệm lμ nh− sau. Bμi toán ứng với đỉnh u 
chỉ đ−ợc giải sau khi tất cả các bμi toán ứng với các đỉnh con của u đã đ−ợc giải. 
43 
Chẳng hạn, với cây nghiệm trong hình 3.11a, thứ tự giải các bμi toán có thể lμ b, c, d, 
g, f, e, a. ta có thể sử dụng thủ tục sắp xếp topo để sắp xếp thứ tự các bμi toán trong 
một cây nghiệm. Đ−ơng nhiên ta cũng có thể giải quyết đồng thời các bμi toán con ở 
cùng một mức trong cây nghiệm. 
Vấn đề của chúng ta bây giờ lμ, tìm kiếm trên đồ thị vμ/hoặc để xác định đ−ợc đỉnh 
ứng với bμi toán ban đầu lμ giải đ−ợc hay không giải đ−ợc, vμ nếu nó giải đ−ợc thì xây 
dựng một cây nghiệm cho nó. 
 Tìm kiếm trên đồ thị vμ/hoặc 
Ta sẽ sử dụng kỹ thuật tìm kiếm theo độ sâu trên đồ thị vμ/hoặc để đánh dấu các đỉnh. 
Các đỉnh sẽ đ−ợc đánh dấu giải đ−ợc hoặc không giải đ−ợc theo định nghĩa đệ quy về 
đỉnh giải đ−ợc vμ không giải đ−ợc. Xuất phát từ đỉnh ứng với bμi toán ban đầu, đi 
xuống theo độ sâu, nếu gặp đỉnh u lμ đỉnh kết thúc thì nó đ−ợc đánh dấu giải đ−ợc. 
Nếu gặp đỉnh u không phải lμ đỉnh kết thúc vμ từ u không đi tiếp đ−ợc, thì u đ−ợc đánh 
dấu không giải đ−ợc. Khi đi tới đỉnh u, thì từ u ta lần l−ợt đi xuống các đỉnh v kề u 
theo một toán tử R nμo đó. Nếu đánh dấu đ−ợc một đỉnh v không giải đ−ợc thì không 
cần đi tiếp xuống các đỉnh v còn lại. Tiếp tục đi xuống các đỉnh kề u theo một toán tử 
khác. Nếu tất cả các đỉnh kề u theo một toán tử nμo đó đ−ợc đánh dấu giải đ−ợc thì u 
sẽ đ−ợc đánh dấu giải đ−ợc vμ quay lên cha của u. Còn nếu từ u đi xuống các đỉnh kề 
nó theo mọi toán tử đều gặp các đỉnh kề đ−ợc đánh dấu không giải đ−ợc, thì u đ−ợc 
đánh dấu không giải đ−ợc vμ quay lên cha của u. 
Ta sẽ biểu diễn thủ tục tìm kiếm theo độ sâu vμ đánh dấu các đỉnh đã trình bμy trên bởi 
hμm đệ quy Solvable(u). Hμm nμy nhận giá trị true nếu u giải đ−ợc vμ nhận giá trị 
false nếu u không giải đ−ợc. Trong hμm Solvable(u), ta sẽ sử dụng: 
 Biến Ok. Với mỗi toán tử R áp dụng đ−ợc tại u, biến Ok nhận giá trị true nếu tất cả 
các đỉnh v kề u theo R đều giải đ−ợc, vμ Ok nhận giá trị false nếu có một đỉnh v kề 
u theo R không giải đ−ợc. 
 Hμm Operator(u) ghi lại toán tử áp dụng thμnh công tại u, tức lμ Operator(u) = R 
nếu mọi đỉnh v kề u theo R đều giải đ−ợc. 
function Solvable(u); 
begin 
1. if u lμ đỉnh kết thúc then 
{Solvable(u) ←true; stop}; 
2. if u không lμ đỉnh kết thúc vμ không có đỉnh kề then 
{Solvable(u) ← false; stop}; 
3. for mỗi toán tử R áp dụng đ−ợc tại u do (1) 
{Ok ← true; 
for mỗi v kề u theo R do (2) 
if Solvable(v) = false then {Ok ← false; exit}; // thoát for (2) 
if Ok then 
44 
{Solvable(u) ← true; Operator(u) ← R; stop} 
} 
4. Solvable(u) ← false; 
end; 
 Nhận xét 
Hoμn toμn t−ơng tự nh− thuật toán tìm kiếm theo độ sâu trong không gian trạng thái 
(mục III.2), thuật toán tìm kiếm theo độ sâu trên đồ thị vμ/hoặc sẽ xác định đ−ợc bμi 
toán ban đầu lμ giải đ−ợc hay không giải đ−ợc, nếu cây tìm kiếm không có nhánh vô 
hạn. Nếu cây tìm kiếm có nhánh vô hạn thì ch−a chắc thuật toán đã dừng, vì có thể nó 
bị xa lầy khi đi xuống nhánh vô hạn. Trong tr−ờng hợp nμy ta nên sử dụng thuật toán 
tìm kiếm sâu lặp (mục III.4). Nếu bμi toán ban đầu giải đ−ợc, thì bằng cách sử dụng 
hμm Operator ta sẽ xây dựng đ−ợc cây nghiệm. 
VI. Bμi tập 
1. Tính số trạng thái tối đa phải l−u khi duyệt một cây theo bề rộng có độ sâu lμ 5 vμ 
hệ số nhánh lμ 4 
2. Viết ch−ơng trình minh họa tìm kiếm theo bề rộng vμ độ sâu của bμi toán 8 số với 
các yêu cầu sau 
a) Trạng thái ban đầu của bμi toán có các số ở vị trí ngẫu nhiên 
b) Trình bμy tất cả trạng thái trong quá trình tìm trạng thái đích 
3. Viết ch−ơng trình minh họa bμi toán nhμ triệu phú vμ kẻ c−ớp với số nhμ triệu phú 
vμ kẻ c−ớp tuỳ ý 
4. Viết ch−ơng trình giải bμi toán tích phân ∫(xex + x3) dx 
45 
Ch−ơng IV 
Các chiến l−ợc tìm kiếm kinh nghiệm 
Trong ch−ơng III, chúng ta đã nghiên cứu việc biểu diễn vấn đề trong không gian trạng 
thái vμ các kỹ thuật tìm kiếm mù. Các kỹ thuật tìm kiếm mù rất kém hiệu quả vμ trong 
nhiều tr−ờng hợp không thể áp dụng đ−ợc. Trong ch−ơng nμy, chúng ta sẽ nghiên cứu 
các ph−ơng pháp tìm kiếm kinh nghiệm (tìm kiếm heuristic), đó lμ các ph−ơng pháp sử 
dụng hμm đánh giá để h−ớng dẫn sự tìm kiếm. 
I. Hμm đánh giá vμ tìm kiếm kinh nghiệm 
Trong nhiều vấn đề, ta có thể sử dụng kinh nghiệm, tri thức của chúng ta về vấn đề để 
đánh giá các trạng thái của vấn đề. Với mỗi trạng thái u, chúng ta sẽ xác định một giá 
trị số h(u), số nμy đánh giá “sự gần đích” của trạng thái u. Hμm h(u) đ−ợc gọi lμ hμm 
đánh giá. Chúng ta sẽ sử dụng hμm đánh giá để h−ớng dẫn sự tìm kiếm. Trong quá 
trình tìm kiếm, tại mỗi b−ớc ta sẽ chọn trạng thái để phát triển lμ trạng thái có giá trị 
hμm đánh giá nhỏ nhất, trạng thái nμy đ−ợc xem lμ trạng thái có nhiều hứa hẹn nhất 
h−ớng tới đích. 
Các kỹ thuật tìm kiếm sử dụng hμm đánh giá để h−ớng dẫn sự tìm kiếm đ−ợc gọi 
chung lμ các kỹ thuật tìm kiếm kinh nghiệm (heuristic search). Các giai đoạn cơ bản 
để giải quyết vấn đề bằng tìm kiếm kinh nghiệm nh− sau: 
1. Tìm biểu diễn thích hợp mô tả các trạng thái vμ các toán tử của vấn đề. 
2. Xây dựng hμm đánh giá. 
3. Thiết kế chiến l−ợc chọn trạng thái để phát triển ở mỗi b−ớc. 
 Hμm đánh giá 
Trong tìm kiếm kinh nghiệm, hμm đánh giá đóng vai trò cực kỳ quan trọng. Chúng ta 
có xây dựng đ−ợc hμm đánh giá cho ta sự đánh giá đúng các trạng thái thì tìm kiếm 
mới hiệu quả. Nếu hμm đánh giá không chính xác, nó có thể dẫn ta đi chệch h−ớng vμ 
do đó tìm kiếm kém hiệu quả. 
Hμm đánh giá đ−ợc xây dựng tùy thuộc vμo vấn đề. Sau đây lμ một số ví dụ về hμm 
đánh giá: 
• Trong bμi toán tìm kiếm đ−ờng đi trên bản đồ giao thông, ta có thể lấy độ dμi của 
đ−ờng chim bay từ một thμnh phố tới một thμnh phố đích lμm giá trị của hμm đánh giá. 
• Bμi toán 8 số. Chúng ta có thể đ−a ra hai cách xây dựng hμm đánh giá. 
Hμm h1: Với mỗi trạng thái u thì h1(u) lμ số quân không nằm đúng vị trí của nó trong 
trạng thái đích. 
Chẳng hạn trạng thái đích ở bên phải hình 4.1, vμ u lμ trạng thái ở bên trái hình 4.1, thì 
h1(u) = 4, vì các quân không đúng vị trí lμ 3, 8, 6 vμ 1. 
46 
Hình 4.1 Đánh giá trạng thái u 
Hμm h2: h2(u) lμ tổng khoảng cách giữa vị trí của các quân trong trạng thái u vμ vị trí 
của nó trong trạng thái đích. ở đây khoảng cách đ−ợc hiểu lμ số ít nhất các dịch 
chuyển theo hμng hoặc cột để đ−a một quân tới vị trí của nó trong trạng thái đích. 
Chẳng hạn với trạng thái u vμ trạng thái đích nh− trong hình 2.1, ta có: 
h2(u) = 2 + 3 + 1 + 3 = 9 
Vì quân 3 cần ít nhất 2 dịch chuyển, quân 8 cần ít nhất 3 dịch chuyển, quân 6 cần ít 
nhất 1 dịch chuyển vμ quân 1 cần ít nhất 3 dịch chuyển. 
Hai chiến l−ợc tìm kiếm kinh nghiệm quan trọng nhất lμ tìm kiếm tốt nhất - đầu tiên 
(best-first search) vμ tìm kiếm leo đồi (hill-climbing search). Có thể xác định các 
chiến l−ợc nμy nh− sau: 
Tìm kiếm tốt nhất đầu tiên = Tìm kiếm theo bề rộng + Hμm đánh giá 
Tìm kiếm leo đồi = Tìm kiếm theo độ sâu + Hμm đánh giá 
Chúng ta sẽ lần l−ợt nghiên cứu các kỹ thuật tìm kiếm nμy trong các mục sau. 
II. Tìm kiếm tốt nhất - đầu tiên 
Tìm kiếm tốt nhất - đầu tiên (best-first search) lμ tìm kiếm theo bề rộng đ−ợc h−ớng 
dẫn bởi hμm đánh giá. Nh−ng nó khác với tìm kiếm theo bề rộng ở chỗ, trong tìm kiếm 
theo bề rộng ta lần l−ợt phát triển tất cả các đỉnh ở mức hiện tại để sinh ra các đỉnh ở 
mức tiếp theo, còn trong tìm kiếm tốt nhất - đầu tiên ta chọn đỉnh để phát triển lμ đỉnh 
tốt nhất đ−ợc xác định bởi hμm đánh giá (tức lμ đỉnh có giá trị hμm đánh giá lμ nhỏ 
nhất), đỉnh nμy có thể ở mức hiện tại hoặc ở các mức trên. 
47 
Hình 4.2 Đồ thị không gian trạng thái 
Ví dụ: Xét không gian trạng thái đ−ợc biểu diễn bởi đồ thị trong hình 4.2, trong đó 
trạng thái ban đầu lμ A, trạng thái kết thúc lμ B. Giá trị của hμm đánh giá lμ các số ghi 
cạnh mỗi đỉnh. Quá trình tìm kiếm tốt nhất - đầu tiên diễn ra nh− sau: Đầu tiên phát 
triển đỉnh A sinh ra các đỉnh kề lμ C, D vμ E. Trong ba đỉnh nμy, đỉnh D có giá trị hμm 
đánh giá nhỏ nhất, nó đ−ợc chọn để phát triển vμ sinh ra F, I. Trong số các đỉnh ch−a 
đ−ợc phát triển C, E, F, I thì đỉnh E có giá trị đánh giá nhỏ nhất, nó đ−ợc chọn để phát 
triển vμ sinh ra các đỉnh G, K. Trong số các đỉnh ch−a đ−ợc phát triển thì G tốt nhất, 
phát triển G sinh ra B, H. 
Đến đây ta đã đạt tới trạng thái kết thúc. Cây tìm kiếm tốt nhất - đầu tiên đ−ợc biểu 
diễn trong hình 4.3. 
Hình 4.3 Cây tìm kiếm tốt nhất - đầu tiên 
Sau đây lμ thủ tục tìm kiếm tốt nhất - đầu tiên. Trong thủ tục nμy, chúng ta sử dụng 
danh sách L để l−u các trạng thái chờ phát triển, danh sách đ−ợc sắp theo thứ tự tăng 
dần của hμm đánh giá sao cho trạng thái có giá trị hμm đánh giá nhỏ nhất ở đầu danh 
sách. 
48 
procedure Best_First_Search; 
begin 
1. Khởi tạo danh sách L chỉ chứa trạng thái ban đầu; 
2. loop do 
2.1 if L rỗng then 
{thông báo thất bại; stop}; 
2.2 Loại trạng thái u ở đầu danh sách L; 
2.3 if u lμ trạng thái kết thúc then 
{thông báo thμnh công; stop} 
2.4 for mỗi trạng thái v kề u do 
Xen v vμo danh sách L sao cho L đ−ợc sắp theo thứ tự tăng dần của hμm 
đánh giá; 
end; 
III. Tìm kiếm leo đồi 
Tìm kiếm leo đồi (hill-climbing search) lμ tìm kiếm theo độ sâu đ−ợc h−ớng dẫn bởi 
hμm đánh giá. 
Song khác với tìm kiếm theo độ sâu, khi ta phát triển một đỉnh u thì b−ớc tiếp theo, ta 
chọn trong số các đỉnh con của u, đỉnh có nhiều hứa hẹn nhất để phát triển, đỉnh nμy 
đ−ợc xác định bởi hμm đánh giá. 
Ví dụ: Ta lại xét đồ thị không gian trạng thái trong hình 2.2. Quá trình tìm kiếm leo 
đồi đ−ợc tiến hμnh nh− sau. Đầu tiên phát triển đỉnh A sinh ra các đỉnh con C, D, E. 
Trong các đỉnh nμy chọn D để phát triển, vμ nó sinh ra các đỉnh con B, G. Quá trình 
tìm kiếm kết thúc. Cây tìm kiếm leo đồi đ−ợc cho trong hình 4.4. 
Trong thủ tục tìm kiếm leo đồi đ−ợc trình bμy d−ới đây, ngoμi danh sách L l−u các 
trạng thái chờ đ−ợc phát triển, chúng ta sử dụng danh sách L1 để l−u giữ tạm thời các 
trạng thái kề trạng thái u, khi ta phát triển u. Danh sách L1 đ−ợc sắp xếp theo thứ tự 
tăng dần của hμm đánh giá, rồi đ−ợc chuyển vμo danh sách L sao trạng thái tốt nhất kề 
u đứng ở danh sách L. 
Hình 4.4 Cây tìm kiếm leo đồi 
49 
procedure Hill_Climbing_Search; 
begin 
1. Khởi tạo danh sách L chỉ chứa trạng thái ban đầu; 
2. loop do 
2.1 if L rỗng then 
{thông báo thất bại; stop}; 
2.2 Loại trạng thái u ở đầu danh sách L; 
2.3 if u lμ trạng thái kết thúc then 
{thông báo thμnh công; stop}; 
2.4 for mỗi trạng thái v kề u do đặt v vμo L1; 
2.5 Sắp xếp L1 theo thứ tự tăng dần của hμm đánh giá; 
2.6 Chuyển danh sách L1 vμo đầu danh sách L; 
end; 
IV. Tìm kiếm beam 
Tìm kiếm beam (beam search) giống nh− tìm kiếm theo bề rộng, nó phát triển các đỉnh 
ở một mức rồi phát triển các đỉnh ở mức tiếp theo. Tuy nhiên, trong tìm kiếm theo bề 
rộng, ta phát triển tất cả các đỉnh ở một mức, còn trong tìm kiếm beam, ta hạn chế chỉ 
phát triển k đỉnh tốt nhất (các đỉnh nμy đ−ợc xác định bởi hμm đánh giá). Do đó trong 
tìm kiếm beam, ở bất kỳ mức nμo cũng chỉ có nhiều nhất k đỉnh đ−ợc phát triển, trong 
khi tìm kiếm theo bề rộng, số đỉnh cần phát triển ở mức d lμ bd (b lμ nhân tố nhánh). 
Ví dụ: Chúng ta lại xét đồ thị không gian trạng thái trong hình 4.2. Chọn k = 2. Khi đó 
cây tìm kiếm beam đ−ợc cho nh− hình 4.5. Các đỉnh đ−ợc gạch d−ới lμ các đỉnh đ−ợc 
chọn để phát triển ở mỗi mức. 
Hình 4.5 Cây tìm kiếm beam 
50 
V. Bμi tập 
1. Trong tìm kiếm tốt nhất - đầu tiên nếu giá trị của hμm đánh giá của các trạng thái 
thay đổi sau mỗi b−ớc chọn thì thủ tục tìm kiếm tốt nhất - đầu tiên cần thay đổi 
nh− thế nμo ? 
2. Viết ch−ơng trình minh họa tìm kiếm tốt nhất - đầu tiên vμ leo đồi vμ beam của bμi 
toán 8 số với các yêu cầu sau 
a) Trạng thái ban đầu của bμi toán có các số ở vị trí ngẫu nhiên 
b) Trình bμy tất cả trạng thái trong quá trình tìm trạng thái đích 
3. Viết giải thuật tỡm kiếm beam (dựng mó giả) 
4. Cho đồ thị không gian trạng thái: 
Để tìm đ−ờng đi từ A tới K, hãy vẽ cây tìm kiếm của tìm kiếm tốt nhất-đầu tiên, tìm 
kiếm leo đồi vμ tìm kiếm beam có k = 2