Ch ng 2ươ
CÁC PH NG PHÁP TÌM KI M L I GI I TRONG ƯƠ Ế Ờ Ả
KHÔNG GIAN TR NG THÁIẠ
Quá trình tìm ki m l i gi i c a bài toán đ c bi u di n trong không gianế ờ ả ủ ượ ể ễ
tr ng thái đ c xem nh quá trình dò tìm trên đ th , xu t phát t tr ng tháiạ ượ ư ồ ị ấ ừ ạ
ban đ u, thông qua các toán t chuy n tr ng thái, l n l t đ n các tr ng tháiầ ử ể ạ ầ ượ ế ạ
ti p theo cho đ n khi g p đ c tr ng thái đích ho c không còn tr ng thái nàoế ế ặ ượ ạ ặ ạ
có th ti p t c đ c n a. Khi áp d ng các ph ng pháp tìm ki m trong khôngể ế ụ ượ ữ ụ ươ ế
gian tr ng thái , ng i ta th ng quan tâm đ n các v n đ sau:ạ ườ ườ ế ấ ề
•K thu t tìm ki m l i gi iỹ ậ ế ờ ả
•Ph ng pháp lu n c a vi c tìm ki mươ ậ ủ ệ ế
•Cách th hiên các nút trong quá trình tìm ki m (mô t tr ng thái bài toán)ể ế ả ạ
•Vi c ch n các toán t chuy n tr ng thái nào đ áp dung và có kh năng sệ ọ ử ể ạ ể ả ử
d ng .ph ng pháp may r i trong quá trình tìm ki m.ụ ươ ủ ế
Tuy nhiên, không ph i các ph ng pháp này có th áp d ng cho t t c cácả ươ ể ụ ấ ả
bài toán ph c t p mà cho t ng l p bài toán. Vi c ch n chi n l c tìm ki mứ ạ ừ ớ ệ ọ ế ượ ế
cho bài toán c th ph thu c nhi u vào các đ c tr ng c a bài toán.ụ ể ụ ộ ề ặ ư ủ
Các th t c tìm ki m đi n hình bao g m:ủ ụ ế ể ồ
-Tìm ki m theo chi u r ng (Breadth – First Search)ế ề ộ
-Tìm ki m theo chi u sâu (Depth – First Search)ế ề
-Tìm ki m sâu d n (Depthwise Search)ế ầ
-Tìm ki m c c ti u hoá giá thành (Cost minimization Search).ế ự ể
-Tìm ki m v i tri th c b sung (Heuristic Search).ế ớ ứ ổ
1. Ph ng pháp tìm ki m theo chi u r ng.ươ ế ề ộ
1.1. K thu t tìm ki m r ng.ỹ ậ ế ộ
23
K thu t tìm ki m rông là tìm ki m trên t t c các nút c a m t m cỹ ậ ế ế ấ ả ủ ộ ứ
trong không gian bài toán tr c khi chuy n sang các nút c a m c ti pướ ể ủ ứ ế
theo.
K thu t tìm ki m r ng b t đ u t m c th nh t c a không gian bàiỹ ậ ế ộ ắ ầ ừ ứ ứ ấ ủ
toán, theo h ng d n c a lu t tr ng tài, ch ng h n “đi t trái sangướ ẫ ủ ậ ọ ẳ ạ ừ
ph i”. N u không th y l i gi i t i m c này, nó chuy n xu ng m c sauả ế ấ ờ ả ạ ứ ể ố ứ
đ ti p t c … đ n khi đ nh v đ c l i gi i n u có.ể ế ụ ế ị ị ượ ờ ả ế
1.2. Gi i thu t.ả ậ
Input:
Cây/Đ th G = (V,E) v i đ nh g c là nồ ị ớ ỉ ố 0 (tr ng thái đ u)ạ ầ
T p đích Goalsậ
Output:
M t đ ng đi p t nộ ườ ừ 0 đ n m t đ nh nế ộ ỉ * ∈ Goals
Method:
S d ng hai danh sách ho t đ ng theo nguyên t c FIFO (queue) MO vàử ụ ạ ộ ắ
DONG
Procedure BrFS; (Breadth First Search)
Begin
Append(MO,no)
DONG=null;
While MO <> null do
begin
n:= Take(MO);
if n∈ DICH then exit;
Append(DONG, n);
For m∈ T(n) and m∉DONG+MO do
Append(MO, m);
end;
24
Write (‘Không có l i gi i’);ờ ả
End;
Chú ý: Th t c Append(MO,nủ ụ 0) b sung m t ph n t vào queue MO.ổ ộ ầ ử
Hàm Take(MO) l y m t ph n t trong queue MO. ấ ộ ầ ử
•N u G là cây thì không c n dùng danh sách DONG.ế ầ
1.3. Đánh giá đ ph c t p c a gi i thu t tìm ki m r ng.ộ ứ ạ ủ ả ậ ế ộ
Gi s r ng, m i tr ng thái khi đ c xét s sinh ra k tr ng thái k ti p.ả ử ằ ỗ ạ ượ ẽ ạ ế ế
Khi đó ta g i k là nhân t nhánh. N u bài toán tìm đ c nghi m theo ph ngọ ố ế ượ ệ ươ
pháp tìm ki m r ng có đ dài d. Nh v y, đ nh đích s n m m c d+1, do đóế ộ ộ ư ậ ỉ ẽ ằ ở ứ
s đ nh c n xét l n nh t là:ố ỉ ầ ớ ấ
1 + k + k2 + . . . + kd.
Nh v y đ ph c t p th i gian c a gi i thu t là O(kư ậ ộ ứ ạ ờ ủ ả ậ d). Đ ph c t pộ ứ ạ
không gian cũng là O(kd), vì t t c các đ nh c a cây tìm ki m m c d+1 đêuấ ả ỉ ủ ế ở ứ
ph i l u vào danh sách.ả ư
1.4. u và nh c đi m c a ph ng pháp tìm ki m r ng.Ư ượ ể ủ ươ ế ộ
1.4.1. u đi m.Ư ể
•K thu t tìm ki m r ng là k thu t vét c n không gian tr ng thái bàiỹ ậ ế ộ ỹ ậ ạ ạ
toán vì v y s tìm đ c l i gi i n u có.ậ ẽ ượ ờ ả ế
•Đ ng đi tìm đ c đi qua ít đ nh nh t.ườ ượ ỉ ấ
1.4.2. Nh c đi m.ượ ể
•Tìm ki m l i gi i theo thu t toán đã đ nh tr c, do v y tìm ki m m tế ờ ả ậ ị ướ ậ ế ộ
cách máy móc; khi không có thông tin h tr cho quá trình tìm ki m,ổ ợ ế
không nh n ra ngay l i gi i.ậ ờ ả
•Không phù h p v i không gian bài oán kích th c l n. Đ i v i lo i bàiợ ớ ướ ớ ố ớ ạ
toán này, ph ng pháp tìm r ng đ i m t v i các nhu c u:ươ ộ ố ặ ớ ầ
-C n nhi u b nh theo s nút c n l u tr .ầ ề ộ ớ ố ầ ư ữ
25
-C n nhi u công s c x lý các nút, nh t là khi các nhánh cây dài, sầ ề ứ ử ấ ố
nút tăng.
-D th c hi n các thao tác không thích h p, th a, đ a đ n vi c tăngễ ự ệ ợ ừ ư ế ệ
đáng k s nút ph i x lý.ể ố ả ử
•Không hi u q a n u l i gi i sâu. Ph ng pháp này không phù h pệ ủ ế ờ ả ở ươ ợ
cho tr ng h p có nhi u đ ng d n đ n k t qu nh ng đ u sâu.ườ ợ ề ườ ẫ ế ế ả ư ề
•Giao ti p v i ng i dùng không thân thi n. Do duy t qua t t c các nút,ế ớ ườ ệ ệ ấ ả
vi c tìm ki m không t p trung vào m t ch đ . ệ ế ậ ộ ủ ề
1.5. Các ví d .ụ
Ví d 1. ụ Bài toán đong n c v i m = 5, n= 4, k =3ướ ớ
M c 1: Tr ng thái đ u (0;0)ứ ạ ầ
M c 2: Các tr ng thái (5;0), (0;4), M c 3: (5;4), (1;4), (4,0)ứ ạ ứ
M c 4: (1;0), (4;4)ứM c 5: (0;1), (5;3)ứ
m c 5 ta g p tr ng thái đích là (5;3) vì v y có đ c l i gi i nh sau:Ở ứ ặ ạ ậ ượ ờ ả ư
(0;0)→ (0;4) → (4;0) → (4;4) → (5;3)
Đ có đ c l i gi i này ta ph i l u l i v t c a đ ng đi, có th trình bày quáể ượ ờ ả ả ư ạ ế ủ ườ ể
trình tìm ki m d i d ng b ng sau:ế ướ ạ ả
i T(i) ↑MO ↓DONG
(0;0)
(0;0) (5;0) (0;4) (5;0) (0;4) (0;0)
(5;0) (5;4) (0;0) (1;4) (0;4) (5;4)
(1;4)
(0;0) (5;0)
(0;4) (5;4) (0;0) (4;0) (5;4) (1;4)
(4;0)
(0;0) (5;0) (0;4)
(5;4) (0;4) (5;0) (1;4) (4;0) (0;0) (5;0) (0;4) (5;4)
(1;4) (5;4) (0;4) (1;0)
(5;0)
(4;0) (1;0) (0;0) (5;0) (0;4) (5;4) (1;4)
(4;0) (5;0) (4;4) (0;0)
(0;4)
(1;0) (4;4) (0;0) (5;0) (0;4) (5;4) (1;4) (4;0)
(1;0) (5;0) (1;4) (0;1) (4;4) (0;1) (0;0) (5;0) (0;4) (5;4) (1;4) (4;0)
(1;0)
(4;4) (5;4) (0;4) (4;0) (0;1) (5;3) (0;0) (5;0) (0;4) (5;4) (1;4) (4;0)
26
(5;3) (1;0) (4;4)
(0;1) (5;1) (0;4) (0;0)
(1;0)
(5;3) (5;1) (0;0) (5;0) (0;4) (5;4) (1;4) (4;0)
(1;0) (0;1)
(5;3)
27