TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

KHOA CÔNG NGHỆ THÔNG TIN

TRÍ TUỆ NHÂN TẠO

BÀI 2: CÁC CHIẾN LƯỢC TÌM KIẾM MÙ

THÁI NGUYÊN, THÁNG 07 NĂM 2024

 BÀI 2: CÁC CHIẾN LƯỢC TÌM KIẾM MÙ
1. Mục tiêu:
• Hiểu được vấn đề tìm kiếm trong không gian trạng thái
• Nghiên cứu các chiến lược tìm kiếm mù (blind search):
• Tìm kiếm theo bề rộng (breadth-first search)
• Tìm kiếm theo độ sâu (depth-first search).
• Hiệu quả của các phương pháp tìm kiếm này.
2. Nội dung
• Hiểu được các chiến lược tìm kiếm mù
• Sử dụng chiến lược tìm kiếm mù giải bài toán cụ thể
3. Hiểu được các chiến lược tìm kiếm mù
• Giải quyết vấn đề bằng tìm kiếm
• Biểu diễn vấn đề trong không gian trạng thái
• Các chiến lược tìm kiếm
 BÀI 2: CÁC CHIẾN LƯỢC TÌM KIẾM MÙ
4. Sử dụng chiến lược tìm kiếm mù giải bài toán cụ thể
4.1 Các chiến lược tìm kiếm mù
• Tìm kiếm theo chiều rộng
• Tìm kiếm theo độ sâu
• Các trạng thái lặp
• Tìm kiếm sâu lặp
4.2 Quy vấn đề về các vấn đề con. Tìm kiếm trên đồ thị and/or.
• Quy vấn đề về các vấn đề con:
• Đồ thị and/or
• Tìm kiếm trên đồ thị and/or
•5. Giao nhiệm vụ tự học
• Làm bài tập trắc nghiệm trên hệ thống LMS
• Bài tập kỹ năng
Trường ĐH Công nghệ thông tin và truyền thông
 2.1. Biểu diễn vấn đề trong không gian trạng thái.
Để giải quyết vấn đề:
1. Phát biểu chính xác bài toán
• Hiện trạng ban đầu,
• Kết quả mong muốn,..
2. Phân tích bài toán.
3. Thu thập và biểu diễn dữ liệu, tri thức cần thiết để giải bài toán.
4. Lựa chọn kỹ thuật giải quyết thích hợp.
=> Để giải quyết một vấn đề nào đó bằng tìm kiếm đầu tiên ta phải xác định không
gian tìm kiếm.

4
 2.1. Biểu diễn vấn đề trong không gian trạng thái.
• Khi biểu diễn một vấn đề như là một đồ thị không gian trạng thái, chúng ta có
thể sử dụng lý thuyết đồ thị để phân tích cấu trúc và độ phức tạp của các vấn đề
cũng như các thủ tục tìm kiếm.

Bài toán 7 cây cầu thành phố Konigsberg và biểu diễn đồ thị tương ứng (Leonhard Euler )

5
 2.1. Biểu diễn vấn đề trong không gian trạng thái.

Khái niệm về Không gian trạng thái

• Một KGTT (state space) là 1 bộ [U, , R, T] trong đó:
• U là không gian trạng thái.
• : Trạng thái ban đầu, ( ∈ U).
• R: Một tập hợp các toán tử: Trong đó mỗi toán tử mô tả một hành động hoặc một phép biến đổi
có thể đưa một trạng thái tới một trạng thái khác.
• T: các trạng thái kết thúc (trạng thái đích), T là tập con của không gian U.

• Khi chúng ta biểu diễn một vấn đề thông qua các trạng thái và các toán tử, thì việc tìm
nghiệm của bài toán được quy về việc tìm đường đi từ trạng thái ban đầu tới trạng thái đích.

6
2.1. Biểu diễn vấn đề trong không
gian trạng thái

• Biểu diễn một vấn đề thông qua các trạng thái và

các toán tử, thì việc tìm nghiệm của bài toán
được quy về việc tìm đường đi từ trạng thái ban
đầu tới trạng thái đích.
• Biểu diễn không gian trạng thái bằng đồ thị định hướng:
• Mỗi đỉnh của đồ thị tương ứng với một trạng thái.
• Nếu có toán tử R biến đổi trạng thái u thành trạng thái v, thì có
cung gán nhãn R đi từ đỉnh u tới đỉnh v.
• Khi đó một đường đi trong không gian trạng thái sẽ là một đường
đi trong đồ thị này.

7
2.1. Biểu diễn vấn đề trong không gian trạng thái.
• Trò đố 8 ô (8 Puzzle ) hay 15 ô
Trạng thái ban đầu Trạng thái đích
•Trò đố 15 ô 11 14 4 7 1 2 3 4
10 6 5 12 13 14 5
1 2 13 15 11 15 6
9 12 8 3 10 9 8 7

2 8 1 2 3
3 5 7 8 4
•Trò đố 8 ô
6 2 1 7 6 5

• Cần biểu diễn KGTT cho bài toán này như thế nào?

8
2.1. Biểu diễn vấn đề trong không gian trạng thái.

• Bài toán người đưa thư Trung Hoa: “Một

người đưa thư xuất phát từ bưu điện phải
đến một số con đường để phát thư rồi
quay trở về điểm xuất phát, hỏi người đó
phải đi như thế nào để số đường đi là ít
nhất”.
• Bài toán người đưa thư Trung Hoa tương
đương với bài toán tìm chu trình ngắn nhất đi
qua tất cả các cạnh của một đồ thị cho trước.
2.1. Biểu diễn vấn đề trong không gian trạng thái.

Mỗi cạnh được đánh

dấu bằng tổng giá
của con đường từ
nút bắt đầu đến nút
hiện tại.

10
 Có khả năng xảy ra
vòng lặp không?
2.1. Biểu diễn vấn đề trong
không gian trạng thái.

• Không gian trạng thái

của bài toán 8 ô số
sinh ra bằng phép
“di chuyển ô trống”
2.1. Biểu diễn vấn đề trong không gian trạng thái.

• Các yếu tố xác định không gian trạng thái

1. Trạng thái.
2. Hành động.
3. Kiểm tra trạng thái thoả đích.
4. Chi phí cho mỗi bước chuyển trạng thái.
 2.2. Các chiến lược tìm kiếm

• Để giải quyết một vấn đề bằng tìm kiếm trong không gian trạng thái, cần tìm dạng
thích hợp mô tả các trạng thái của vấn đề và xác định:
• Trạng thái ban đầu.

• Tập các toán tử.

• Tập T các trạng thái kết thúc. (T có thể không được xác định cụ thể gồm các trạng thái nào mà
chỉ được chỉ định bởi một số điều kiện nào đó).

13
 2.2. Các chiến lược tìm kiếm

• Có thể phân các chiến lược tìm CÁC THUẬT TOÁN TÌM KIẾM TRONG AI

kiếm:
• Các chiến lược tìm kiếm mù: Trong các Tìm kiếm mù
Tìm kiếm kinh
nghiệm
Tìm kiếm tối
ưu
Tìm kiếm có
đối thủ
chiến lược tìm kiếm này, không có một sự
hướng dẫn nào cho sự tìm kiếm, mà ta chỉ Tìm kiếm theo Tốt nhất đầu Tìm kiếm
phát triển các trạng thái ban đầu cho tới khi Tìm kiếm A*
chiều rộng tiên Minimax
gặp một trạng thái đích nào đó.
• Tìm kiếm theo bề rộng Tìm kiếm cắt
Tìm kiếm theo Tìm kiếm
Leo đồi cut Alpha -
chiều sâu Nhánh và Cận
• Tìm kiếm theo độ sâu. Beta

• Tìm kiếm kinh nghiệm (tìm kiếm

Tìm kiếm sâu Tìm kiếm
heuristic). Dựa vào sự hiểu biết của chúng hạn chế Beam
ta về vấn đề, dựa vào kinh nghiệm, trực
giác, để đánh giá các trạng thái. Sử dụng sự Tìm kiếm sâu
đánh giá các trạng thái để hướng dẫn sự tìm lặp

kiếm.

14
 2.2. Các chiến lược tìm kiếm

• Tìm kiếm mù, chọn trạng thái để phát triển theo thứ tự mà chúng
được sinh ra

• Tìm kiếm kinh nghiệm ta chọn trạng thái dựa vào sự đánh giá các
trạng thái.

• Cây tìm kiếm: là cây mà các đỉnh được gắn bởi các trạng thái của
không gian trạng thái.
• Gốc của cây tìm kiếm tương ứng với trạng thái ban đầu.

• Nếu một đỉnh ứng với trạng thái u, thì các đỉnh con của nó ứng với các trạng
thái v kề u.

15
 2.3.1. Tìm kiếm theo chiều rộng (Breadth First Search)

• Tại mỗi bước ta sẽ chọn trạng thái để phát triển là

trạng thái được sinh ra trước các trạng thái chờ
phát triển khác
• Chúng ta sử dụng danh sách L để lưu các trạng thái
đã được sinh ra và chờ được phát triển.
• Mục tiêu của tìm kiếm trong không gian trạng thái
là tìm đường đi từ trạng thái ban đầu tới trạng thái
đích, do đó ta cần lưu lại vết của đường đi. Ta có
thể sử dụng hàm father để lưu lại cha của mỗi đỉnh
trên đường đi, father(v) = u nếu cha của đỉnh v là u.

16
 2.3.1. Tìm kiếm theo chiều rộng

Tiếp tục …
17
 Ví dụ
• Cho đồ thị không gian trạng thái với U 0 = A, T = {I, E, K}
• Áp dụng thuật toán tìm kiếm theo chiều rộng:

Lần lặp L= u uT v L

0 A
1 False A False B, C, D B, C D
2 False B False H, I C, D, H, I
3 False C False E, F D, H, I, E, F
4 False D False G H, I, E, F, G
5 False H False I, E, F, G
6 False IT True
 2.3.1. Tìm kiếm theo chiều rộng

• Nhận xét
• Trạng thái nào được sinh ra trước sẽ được phát
triển trước, do đó danh sách L được sử dụng là
hàng đợi (queue - FIFO).
• Trong bước 2.3, ta cần kiểm tra xem u có là
trạng thái kết thúc không.
• Nếu bài toán có nghiệm (tồn tại đường đi từ
trạng thái đầu tới trạng thái kết thúc), thì thuật
toán sẽ tìm được nghiệm.

19
2.3.1. Tìm kiếm theo chiều rộng

• Đánh giá tìm kiếm BFS

• Giả sử rằng, mỗi trạng thái khi được phát triển sẽ sinh ra b trạng thái kề. Ta sẽ gọi b là
nhân tố nhánh. Giả sử rằng, nghiệm của bài toán là đường đi có độ dài d.
• Tính đủ? có (nếu b là hữu hạn).
• Thời gian? Bởi nhiều nghiệm có thể được tìm ra tại một đỉnh bất kỳ ở mức d của cây tìm kiếm, do đó số đỉnh
cần xem xét để tìm ra nghiệm là:
• 1 + b + b2 + ... + bd-1 + k
• Trong đó k có thể là 1, 2, ..., bd. Do đó số lớn nhất các đỉnh cần xem xét là:
• 1 + b + b2 + ... + bd
• Không gian trạng thái? O(bd) (lưu mọi node của cây).

• Nhận xét chung: Không gian lưu trữ hết sức tốn kém là vấn đề lớn nhất đối
với phương pháp tìm kiếm theo chiều rộng!
 2.3.2. Tìm kiếm theo độ sâu

•Tư tưởng: Tại mỗi bước trạng thái được

chọn để phát triển là trạng thái được sinh
ra sau cùng trong số các trạng thái chờ
phát triển.
• Do đó thuật toán tìm kiếm theo độ sâu là hoàn
toàn tương tự như thuật toán tìm kiếm theo bề
rộng, chỉ có một điều khác là, ta xử lý danh
sách L các trạng thái chờ phát triển không phải
như hàng đợi mà như ngăn xếp.

21
Ví dụ

•(Tiếp tục …)
 Ví dụ
• Cho đồ thị không gian trạng thái với U0 = A, T = {I, E, G}

• Áp dụng thuật toán tìm kiếm theo chiều sâu:

Lần lặp L= u uT v L

0 A
1 False A False B, C, D D, C, B Cây tìm kiếm
2 False D False G G, C, B
3 False G True
 2.3.2. Tìm kiếm theo độ sâu
Procedure Depth_First_Search;
begin
1. Khởi tạo danh sách L chỉ chứa trạng thái
ban đầu u0;
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 đầu danh sách L;};
end;
24
 2.3.2. Tìm kiếm theo độ sâu

Nhận xét thuật toán tìm kiếm theo chiều sâu

• Đối BFS: luôn tìm ra nghiệm nếu bài toán có nghiệm.
• Đối với DFS: không phải với bất kỳ bài toán có nghiệm nào thuật toán tìm kiếm theo chiều sâu
cũng tìm ra nghiệm. (với bài toán có nghiệm và không gian tìm kiếm hữu hạn mới tìm được
nghiệm).
• Lý do?
• Trong trường hợp không gian trạng thái là vô hạn, thì có thể nó không tìm ra nghiệm vì ta luôn
đi sâu xuống, nếu ta đi theo nhánh vô hạn mà nghiệm không nằm trên nhánh đó thì thuật toán
sẽ không dừng.

25
 2.3.2. Tìm kiếm theo độ sâu
Đánh giá tìm kiếm DFS
•Tính đủ?
• Không đủ (không gian vô hạn hoặc loop)
• Nếu sửa để tránh trùng lặp → đủ trong không gian hữu hạn.
•Thời gian?
• O(bm)
• Rất xấu nếu m lớn hơn nhiều so với d.
• Nhưng nếu mật độ lời giải trong không gian lớn thì có thể nhanh hơn BFS.
•Không gian trạng thái?
• O(bd)., Độ phức tạp tuyến tính
•Tính tối ưu?
• Không

26
 2.3.3. Các trạng thái lặp
• Cây tìm kiếm có thể chứa nhiều đỉnh
ứng với cùng một trạng thái, các trạng
thái này được gọi là trạng thái lặp.
 Các trạng thái C, E, F là các trạng thái lặp.
 Trong đồ thị biểu diễn không gian trạng
thái, các trạng thái lặp ứng với các đỉnh có
nhiều đường đi dẫn tới nó từ trạng thái
ban đầu.
 Vì vậy trong quá trình tìm kiếm ta cần
tránh phát sinh ra các trạng thái mà ta đã
phát triển.

27
 2.3.3. Các trạng thái lặp
•Chúng ta có thể áp dụng một trong các giải pháp sau đây:
• Khi phát triển đỉnh u, không sinh ra các đỉnh trùng với cha của u.

• Khi phát triển đỉnh u, không sinh ra các đỉnh trùng với một đỉnh nào đó nằm trên đường đi dẫn tới u.

• Không sinh ra các đỉnh mà nó đã được sinh ra, tức là chỉ sinh ra các đỉnh mới.

•Nhận xét:
• Hai giải pháp đầu dễ cài đặt và không tốn nhiều không gian nhớ, tuy nhiên các giải pháp này không tránh được
hết các trạng thái lặp.

• Để thực hiện giải pháp thứ 3 ta cần lưu các trạng thái đã phát triển vào tập Q, lưu các trạng thái chờ phát triển
vào danh sách L. Đương nhiên, trạng thái v lần đầu được sinh ra nếu nó không có trong Q và L. Việc lưu các
trạng thái đã phát triển và kiểm tra xem một trạng thái có phải lần đầu được sinh ra không đòi hỏi rất nhiều
không gian và thời gian.
28
 2.3.4 Tìm kiếm sâu lặp
• Nếu cây tìm kiếm chứa nhánh vô hạn, khi sử dụng tìm kiếm theo độ sâu, ta có thể mắc kẹt ở
nhánh đó và không tìm ra nghiệm.

• Để khắc phục hoàn cảnh đó, ta tìm kiếm theo độ sâu chỉ tới mức d nào đó; nếu không tìm ra
nghiệm, ta tăng độ sâu lên d+1 và lại tìm kiếm theo độ sâu tới mức d+1. Quá trình trên được
lặp lại với d lần lượt là 1, 2, ... dến một độ sâu max nào đó.
• Như vậy, thuật toán tìm kiếm sâu lặp (iterative deepening search) sẽ sử dụng thủ tục tìm kiếm sâu hạn chế
(depth_limited search) như thủ tục con. Đó là thủ tục tìm kiếm theo độ sâu, nhưng chỉ đi tới độ sâu d nào đó rồi
quay lên.

• Trong thủ tục tìm kiếm sâu hạn chế, d là tham số độ sâu, hàm depth ghi lại độ sâu của mỗi đỉnh

29
 2.3.4 Tìm kiếm sâu lặp
Procedure Depth_Limited_Search(d);
begin
1. Khởi tạo danh sách L chỉ chứa trạng thái ban đầu u0;
depth(u0) ← 0;
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. if depth(u) <= d then
for mỗi trạng thái v kề u do
{Đặt v vào đầu danh sách L;
depth(v) ← depth(u) + 1};
end; 30
 2.3.4 Tìm kiếm sâu lặp
Độ sâu giới hạn (depth bound):
Cài đặt thuật toán tìm kiếm sâu lặp
◦ Giải thuật TK sâu sẽ quay lui khi trạng thái đang xét
đạt đến độ sâu giới hạn đã định.
Procedure Depth_Deepening_Search;

Tìm kiếm Sâu bằng cách đào sâu nhiều lần: Begin
◦ Tìm kiếm sâu với độ sâu giới hạn là 1, nếu thất bại,
For d← 0 to max do
nó sẽ lặp lại giải thuật TK sâu với độ sâu là 2,…
◦ Giải thuật tiếp tục cho đến khi tìm được mục tiêu,
{Depth_Limited_Search(d);
mỗi lần lặp lại tăng độ sâu lên 1. If thành công then exit}
Giải thuật này có độ phức tạp về thời gian cùng bậc
End;
với tìm kiếm theo chiều rộng và tìm kiếm theo chiều
sâu.

31
2.3.4 Ví dụ: Tìm kiếm sâu lặp

Với d
=0

Với d
=1

32
 2.3.4 Tìm kiếm sâu lặp
Với d =2

33
 2.3.4 Tìm kiếm sâu lặp

Với d =3

34
2.3.4 Tìm kiếm sâu lặp

Nhận xét về tìm kiếm sâu lặp:

•Số lượng nodes được sinh trong giới hạn độ sâu d với độ phân nhánh b:
NDLS =1 + b + b2 + ... + bd

•Số lượng nodes được sinh trong tìm kiếm sâu dần với độ sâu d độ phân
nhánh b:
NIDS = (d+1)1 + db + (d-1)b2 + ... + 2bd-1 + 1bd

35
 2.4 Quy vấn đề về các vấn đề con. Tìm kiếm trên đồ thị and/or
2.4.1. Quy vấn đề về các vấn đề con
Chia để trị:
• Thông thường, các bài toán được quy về việc tìm đường trong không gian trạng thái.

• Để giải quyết vấn đề, có thể chia nhỏ bài toán thành các vấn đề con. Việc này được
thực hiện lặp lại nhiều lần đến khi các vấn đề này có thể giải quyết được.

36
 2.4.1 Quy vấn đề về các vấn đề con
Ví dụ về phương pháp: Tính tích phân

•Tính tích phân:  (xex + x3) dx

xe 
x
•Để tính được tích phân này có thể sử dụng mô hình sau:  x 3 dx

37
 2.4.1 Quy vấn đề về các vấn đề con
Ví dụ về phương pháp: Tìm đường
• Giả sử có bản đồ một thành phố, cần tìm
đường đi từ A đến B.
• Đường đi từ A đến B qua E,
• Đường đi từ A đến B qua G.

38
 2.4. Đồ thị và/hoặc (and/or graph)
Quy tắc xây dựng đồ thị và/hoặc.
 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, ví dụ R: a→b, thì trong đồ thị 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, ví dụ R: a→b,c,d, ta đưa một đỉnh mới a 1,

đỉnh này biểu diễn tập các bài toán con {b,c,d} và bài
toán R: a→b,c,d được xây dựng như hình bên

39
 2.4.2 Đồ thị và/hoặc
(and/or graph)

Xét bài toán, trạng thái ban đầu (bài toán cần
giải) là a.
•Tập các toán tử quy gồm:
• R1: a→d,e,f
• R2: a→d,k
• R3: a→g,h
• R4: d→b,c
• R5: f→i
• R6: f→c,j
• R7: k→e,l
• R8: k→h
a1, a2, a3 được gọi là đỉnh và
•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,j,l}
a, f, k được gọi là đỉnh hoặc
40
2.4.2 Đồ thị và/hoặc (and/or graph)
Rút gọn đồ thị

41
 2.4.2 Đồ thị và/hoặc (and/or graph)

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).

• 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. 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.
42
 2.4.2 Đồ thị và/hoặc (and/or graph)

 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.
 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.
 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.
 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ó.
43
 2.4.3. Tìm kiếm trên đồ thị và/hoặc

Tư tưởng: 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.
 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.
44
 2.4.3. Tìm kiếm trên đồ thị và/hoặc

 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.

45
2.4.3. Tìm kiếm trên đồ thị và/hoặc
function Solvable(u);
begin
1. if u là đỉnh kết thúc then {Solvable  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
{Ok  true;
for mỗi v kề u theo R do
if Solvable(v) = false then {Ok  false; exit};
if Ok then
{Solvable(u) true; Operator(u) R; stop}}
4. Solvable(u) false; 46
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

Thank
KHOA CÔNG NGHỆ THÔNG TIN

you!

THÁI NGUYÊN, THÁNG 07 NĂM 2024