GIÁO TRÌNH TRÍ TUỆ NHÂN TẠO - 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

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 ế

i ta th ng quan tâm đ n các v n đ sau: ạ ườ ế ề ấ

i gi gian tr ng thái , ng ườ • K thu t tìm ki m l ậ ế ỹ ờ 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 ể ể ạ ả ử

ng pháp may r i trong quá trình tìm ki m. d ng .ph ụ ươ ủ ế

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. ươ ề ộ ế

23

1.1. K thu t tìm ki m r ng. ộ ế ậ ỹ

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.

m c th nh t c a không gian bài K thu t tìm ki m r ng b t đ u t ế ắ ầ ừ ứ ấ ủ ứ ậ ộ ỹ

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 ể ứ ứ ố

c l i gi i n u có. đ ti p t c … đ n khi đ nh v đ ế ể ế ụ ị ượ ờ ị ả ế

1.2. Gi i thu t. ả ậ

Input:

0 (tr ng thái đ u)

Cây/Đ th G = (V,E) v i đ nh g c là n ồ ị ớ ỉ ố ạ ầ

T p đích Goals ậ

Output:

* ˛

M t đ ng đi p t n Goals ộ ườ ừ 0 đ n m t đ nh n ộ ỉ ế

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);

24

end;

Write (‘Không có l i gi i’); ờ ả

End;

0) b sung m t ph n t

Chú ý: Th t c Append(MO,n 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. ẽ ạ

nhánh. N u bài toán tìm đ c nghi m theo ph Khi đó ta g i k là nhân t ọ ố ế ượ ệ ươ 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.

d). Đ ph c t p ứ ạ

i thu t là O(k Nh v y đ ph c t p th i gian c a gi ứ ạ ư ậ ủ ộ ờ ả ậ ộ

không gian cũng là O(kd), vì t m c d+1 đêu ấ ả t c các đ nh c a cây tìm ki m ủ ế ở ứ ỉ

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 đ i gi i n u có. c l ượ ờ ả ế

ậ ẽ • Đ 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,

i gi i. không nh n ra ngay l ậ ả

ờ • 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: ươ ặ ớ ầ ộ ố

25

- C n nhi u b nh theo s nút c n l u tr . ữ ầ ư ề ầ ộ ớ ố

- 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ý. ả ử ể ố

i gi sâu. Ph • Không hi u q a n u l ệ ế ờ ủ i ả ở ươ ợ ng pháp này không phù h p

ng h p có nhi u đ ng d n đ n k t qu nh ng đ u sâu. ề ườ ợ ả ư ế ế ề ẫ ườ

i dùng không thân thi n. Do duy t qua t t c các nút, ườ ệ ệ ấ ả cho tr • Giao ti p v i ng ế ớ

vi c tìm ki m không t p trung vào m t ch đ . ủ ề ế ệ ậ ộ

1.5. Các ví d .ụ

c v i m = 5, n= 4, k =3 Ví d 1. ụ Bài toán đong n ướ ớ

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) ứ ứ

i gi ậ c l ượ ờ ả i nh sau: ư

Ở ứ (0;0)fi m c 5 ta g p tr ng thái đích là (5;3) vì v y có đ (4;4) fi ặ ạ (4;0) fi (0;4) fi (5;3)

Đ có đ i gi i này ta ph i l u l i v t c a đ ể c l ượ ờ ả ả ư ạ ế ủ ườ 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) DONG › MO fl

(0;0) (5;0) (5;0) (0;4) (5;4) (0;0) (1;4) (0;0) (0;0) (5;0) (5;4)

(0;4) (5;4) (0;0) (4;0) (1;4) (0;0) (5;0) (0;4)

(0;0) (5;0) (0;4) (0;4) (1;4) (5;4) (4;0) (1;4) (4;0) (4;0) (1;0) (5;4) (1;4) (0;0) (5;0) (0;4) (5;4) (0;0) (5;0) (0;4) (5;4) (1;4)

(4;0) (1;0) (4;4) (0;0) (5;0) (0;4) (5;4) (1;4) (4;0)

(4;4) (0;1) (1;0) (0;4) (5;0) (5;4) (0;4) (1;0) (5;0) (5;0) (4;4) (0;0) (0;4) (5;0) (1;4) (0;1)

26

(4;4) (5;4) (0;4) (4;0) (0;1) (5;3) (0;0) (5;0) (0;4) (5;4) (1;4) (4;0) (1;0) (0;0) (5;0) (0;4) (5;4) (1;4) (4;0)

(5;3) (5;1) (0;1)

(5;3) (5;1) (0;4) (0;0) (1;0) (1;0) (4;4) (0;0) (5;0) (0;4) (5;4) (1;4) (4;0) (1;0) (0;1)

27

(5;3)

Ví d 2.ụ Bài toán trò ch i 8 s ơ ố

B ng xu t phát ấ ả

8 6

2 1 7 3 4 5

B ng k t thúc ế ả

2

1 8 7 3 4 5

6 M c 1: Có m t tr ng thái ộ ạ ứ

8 6

2 1 7 3 4 5

M c 2: Có ba tr ng thái ứ ạ

8

3 4 2 1

2 1 7 6 3 4 5 2 1 7 8 6 5 8 6 7 3 4 5

M c 3: Có năm tr ng thái ứ ạ

2 3

7 8 1 6 3 4 5 2 1 7 8 6 3 4 5 2 1 7 8 4 6 5

2 3

1 8 6 7 3 4 5 2 1 7 8 6 5 4

M c 4: Có m i tr ng thái ườ ạ ứ

2 7

2 7 8 1 6 3 4 5 8 1 6 3 4 5

28

2 1 8 4 3 2 1 8 4 3 5

1 7 5 7 6

1 7 2 8 6 3 4 5 2 1 7 3 8 6 4 5

8

2 1 8 6 7 3 4 5 2 6 1 7 3 4 5

3 4

2 1 7 8 6 5 3 4 2 1 7 8 6 5

M c 6: Có 12 tr ng thái ứ ạ

1 4

29

7 2 8 6 3 4 5 2 1 7 3 8 6 5

8 1

2 7 6 3 4 5 8 2 7 3 4 5 1 6

8 4

2 1 7 3 5 6 2 1 7 8 3 5 4 6

2 6 1 8 7 3 4 5 8 2 1 3 4 5 6 7

8 7

2 1 7 6 5 8 3 4 2 6 1 3 4 5

8 5

2 1 7 3 6 4 2 1 7 3 3 4 8 5

M c 6: Có 24 tr ng thái ứ ạ

2

1 7

2 8 6 3 4 5 1 8 7 3 4 5 6

. . .

m c này ta g p đ c tr ng thái đích. Ở ứ ặ ượ ạ

2

1 8 7 6 3 4 5

2. Ph ng pháp tìm ki m theo chi u sâu. ươ ề ế

30

2.1. K thu t tìm ki m sâu. ế ậ ỹ

Tìm ki m sâu trong không gian bài toán đ c b t đ u t ế ượ ắ ầ ừ ộ ồ m t nút r i

ậ ti p t c cho đ n khi ho c đ n ngõ c t ho c đ n đích. T i m i nút có lu t ụ ế ụ ế ế ế ặ ặ ạ ỗ

trong tài, ch ng h n, “đi theo nút c c trái”, h ng d n vi c tìm. N u không đi ự ẳ ạ ướ ệ ế ẫ

ti p đ oc, g i là đ n ngõ c t, h th ng quay l i m t m c trên đ th và tìm ệ ố ụ ự ế ế ọ ạ ồ ị ứ ộ

theo h ng khác, ch ng h n, đ n nút “sát nút c c trái”. Hành đ ng này g i là ướ ự ế ẳ ạ ộ ọ

quay lui.

c hình dung nh vi c kh o sát Thu t toán tìm ki m theo chi u sâu đ ế ề ậ ượ ư ệ ả

m t cây b t đ u t c, khi g p cành c t thì ắ ầ ừ ố g c đi theo m i cành có th đ ọ ể ượ ộ ụ ặ

quay l i xét cành ch a đi qua. ạ ư

- c t ng quát, gi b s đang xét đ nh i, khi đó các đ nh k v i i có Ở ướ ổ ả ử ề ớ ỉ ỉ

các tr ườ ng h p: ợ

+ N u t n t ế ồ ạ ỉ i đ nh j k i ch a đ ề ư ượ c xét thì xét đ nh này (nó tr ỉ ở

thành đ nh đã xét) và b t đ u t đó ti p t c quá trình tìm ki m v i đ nh ắ ầ ừ ỉ ế ụ ớ ỉ ế

này..

+ N u v i m i đ nh k v i i đ u đã đ ề ớ ọ ỉ ề ế ớ ượ ệ c xét thì i coi nh duy t ư

xong và quay tr l i tìm ki m t đ nh mà t đó ta đi đ n đ c i. ở ạ ế ừ ỉ ừ ế ượ

2.2. Gi i thu t. ả ậ

Input:

0 (tr ng thái đ u)

Cây/Đ th G = (V,E) v i đ nh g c là n ồ ị ớ ỉ ố ạ ầ

T p đích Goals ậ

Output:

* ˛

M t đ ng đi p t n Goals ộ ườ ừ 0 đ n m t đ nh n ộ ỉ ế

Method:

S d ng hai danh sách ho t đ ng theo nguyên t c LIFO (Stack) MO và ạ ộ ử ụ ắ

DONG

Procedure DFS; (Depth First Search)

Begin

31

Push (MO,no)

DONG=null;

While MO <> null do

begin

n:=pop (MO); if n˛ DICH then exit;

push (DONG, n); For m˛ T(n) and mˇ DONG+MO do

Push (MO, m);

end;

Write (‘Không có l i gi i’); ờ ả

End;

0) th c hi n vi c b sung n

0 vào stack MO

Chú ý: Th t c Push(MO,n ủ ụ ệ ổ ự ệ

Hàm Pop(MO) l y ph n t đ u tiên trong Stack MO. ầ ử ầ ấ

2.3. Đánh giá đ ph c t p c a thu t toán tìm ki m sâu. ộ ứ ạ ủ ế ậ

G i s nghi m c a bài toán là đ ng đi có đ dài d, cây tìm ki m có ả ử ủ ệ ườ ế ộ

nhân t nhánh là k. Có th xãy ra nghi m là đ nh cu i cùng đ c xét ố ể ệ ố ỉ ượ ở ứ m c

ế d+1 theo lu t tr ng tài. Khi đó đ ph c t p th i gian c a thu t toán tìm ki m ứ ạ ậ ọ ủ ậ ộ ờ

d).

theo chi u sâu trong tr ng h p x u nh t là O(k ề ườ ấ ấ ợ

Đ đánh giá đ ph c t p không gian c a thu t toán tìm ki m sâu ta có ứ ạ ủ ể ế ậ ộ

nh n xét ràng: Khi xét đ nh j, ta ch c n l u các đ nh ch a đ c xét mà chúng ỉ ầ ư ư ượ ậ ỉ ỉ

là nh ng đ nh con c a nh ng đ nh n m trên đ ng đi t đ nh g c đ n j. Vì ữ ữ ủ ằ ỉ ỉ ườ ừ ỉ ế ố

i đa la k*d. Do đó đ ph c t p không gian c a thu t toán là v y ch c n l u t ậ ỉ ầ ư ố ứ ạ ủ ậ ộ

O(k*d).

2.4. u và nh c đi m c a ph ng pháp tìm ki m sâu. Ư ượ ủ ể ươ ế

i gi i, ph ng pháp tìm ki m sâu b o đ m tìm ra l 2.4.1. u đi m. Ư ể • N u bài toán có l ờ ả ươ ế ả ả ờ i ế

32

gi i.ả

• K thu t tìm ki m sâu t p trung vào đích, con ng i c m th y hài lòng khi ế ậ ậ ỹ ườ ả ấ

các câu h i t p trung vào v n đ chính. ỏ ậ ề ấ

• Do cách tìm c a k thu t này, n u l i gi r t sâu, k thu t tìm sâu s i ế ờ ủ ậ ỹ ả ở ấ ậ ỹ ẽ

ti t ki m th i gian. ế ệ ờ

ượ c đi m. ể

2.4.2. Nh • Tìm sâu khai thác không gian bài toán đ tìm l i gi ể ờ ả ơ i theo thu t toán đ n ậ

gi n m t cách c ng nh c. Trong quá trình tìm nó không có thông tin nào ứ ả ắ ộ

h tr đ phát hi n l i gi ổ ợ ể ệ ờ ả i. N u ch n nút ban đ u không thích h p có th ầ ế ọ ợ ể

không d n đ n đích c a bài toán. ủ ế ẫ

• Không phù h p v i không gian bài toán l n, k thu t tìm ki m sâu có th ế ậ ợ ớ ớ ỹ ể

không đ n l i gi ế ờ ả i trong kho ng th i gian v a ph i. ờ ừ ả ả

2.5. Các ví d .ụ

c v i m = 5, n = 4, k = 3 Ví d 1. ụ Bài toán đong n ướ ớ

i gi N u ta ch n nhánh u tiên đ đ y bình th hai thì s tìm th y l ổ ầ ấ ờ ứ ư ẽ ế ọ ả ấ i r t

nhanh. Quá trình tìm ki m có th trình bày b ng b ng d i đây ể ế ằ ả ướ

› i T(i) DONG MO fl

(0;0) (5;0) (0;4) (5;0) (0;0) (0;4) (5;0) (0;4) (5;4) (0;0) (4;0) (0;0) (0;0) (0;4) (5;4)

(4;0) (5;0) (4;0) (5;0) (4;4) (0;0) (5;4) (0;0) (0;4) (4;0)

(0;4) (5;4) (0;4) (4;0) (4;4) (5;0) (4;4) (5;4) (0;0) (0;4) (4;0) (4;4)

(5;3) (5;3)

fi i tìm đ c: (0;0) (0;4) fi (4;0) fi (4;4) fi (5;3) (5;3) L i gi ờ ả ượ

Ví d 2. ụ Bài toán Tháp Hà n i v i n = 3. ộ ớ

1; x2; x3) bi u di n tr ng thái bài toán, v i x ạ

Nh c l i, dùng b ba (x ắ ạ ộ ớ i là c cọ ể ễ

ch a đĩa l n th i. ứ ứ ớ

33

› i T(i) DONG MO fl

(1;1;1) (1;1;3) (1;1;2) (1;1;3) (1;1;1)(1;1;2) (1;1;1) (1;1;2) (1;1;3) (1;1;2)(1;2;3) (1;1;1) (1;1;1)(1;1;3)

(1;2;1) (1;1;2)(1;2;1)(1;2;2) (1;1;1)(1;1;3)(1;2;3) (1;2;3) (1;1;3) (1;2;3)

(1;2;1) (1;1;2)(1;2;1)(3;2;2) (1;1;1)(1;1;3)(1;2;3)(1;2;2) (1;2;2) (1;2;3) (1;2;2)

(3;2;3) (1;1;2)(1;2;1)(3;2;1) (1;1;1)(1;1;3)(1;2;3)(1;2;2) (3;2;2) (1;2;2) (3;2;2)

(3;2;3) (1;1;2)(1;2;1)(3;3;1) (3;2;2) (1;1;1)(1;1;3)(1;2;3)(1;2;2) (3;2;1) (3;2;2) (3;2;1)

(3;3;2) (1;1;2)(1;2;1)(3;3;3) (3;2;2) (3;2;1) (1;1;1)(1;1;3)(1;2;3)(1;2;2) (3;3;1) (3;2;1) (3;3;1)

(3;2;2) (3;2;1) (3;3;3) (3;3;3)

(3;3;3)

i c a bài toán: ả ủ

L i gi ờ (1;1;1) fi (1;1;3) fi (1;2;3) fi (1;2;2) fi (3;2;2) fi (3;2;1) fi (3;3;1) fi (3;3;3)

• C hai ví d trên, chúng ta đ u th y, tìm ki m theo chi u sâu đ u cho l ấ ụ ề ế ề ề ả ờ i

gi t và nhanh. i t ả ố

Ví d 3. ụ Bài toán tìm dãy h p lý v i s h ng đ u a ớ ố ạ ầ 1 = 26 ợ

1, a2, …,an đ

-

Nh c l i: Dãy a c g i là h p lý n u tho hai đi u ki n: ắ ạ ượ ọ ế ề ệ ả ợ

-

k

an là s nguyên t ố ố

ak+1 = ak+1 ho c 2*a ặ

t a c a ể

ị k t ế k thì ta xác đ nh đ ứ ạ tr ng thái ộ i thòi đi m đang xét. Ta có th ch ra m t ượ k+1. Vì v y có th mô t ả ạ ậ ỉ ể ể

Nh v y, khi bi ư ậ bài toán t cách tìm ki m theo chi u sâu nh sau ng ng v i giá trj a ớ ề ươ ế ư

› T(i) I DONG MO fl

27 52 53 104 105 208 209 416 26 27 52 27 53 104 27 53 105 208 27 53 105 209 416 26 26 52 26 52 104 26 52 104 208

34

26 52 104 208 . . .

V i cách tìm ki m theo theo thu t toán m t cách máy móc nh v y thì rõ ràng ư ậ ế ậ ớ ộ

không bao gi c đích. Trong khi chúng ta d dàng nh n đ i gi đ t đ ờ ạ ượ ễ ậ c l ượ ờ ả i,

chăng h n:ạ

a1 = 26; a2 = 52; a3 = 53. Nh v y n =3 ư ậ

3. Tìm ki m sâu d n ế ầ

3.1. K thu t tìm ki m sâu d n. ế ậ ầ ỹ

K thu t tìm ki m sâu d n là th c hi n vi c tìm ki m v i đ sâu ự ớ ộ ế ệ ệ ế ậ ầ ỹ ở

m c gi ói h n 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,...đ n đ sâu max nào đó. ộ ế

K thu t tìm ki m sâu d n th ng đ ế ậ ầ ỹ ườ ượ ế c th c hi n khi cây tìm ki m ự ệ

ch a nhánh vô h n, và n u s d ng tìm ki m theo đ sâu ta có th m c k t ể ắ ẹ ở ế ử ụ ứ ế ạ ộ

m t nhánh nào đó (thu t toán không d ng) và không tìm ra nghi m. ừ ệ ậ ộ

n0

35

D

3.2. Gi i thu t. ả ậ

Thu t toán tìm ki m sâu d n s d ng thu t toán tìm ki m sâu h n ch ầ ử ụ ế ế ậ ậ ạ ế

nh th t c con. Đó là th t c tìm ki m theo chi u sâu nh ng ch t i đ sâu d ư ủ ụ ủ ụ ỉ ớ ộ ư ế ề

nào đó r i quay lên. ồ

Th t c tìm ki m sâu h n ch (depth_limitedsearch) ủ ụ ế ế ạ

Procedure Depth_limited_search(d); {d là tham s đ sâu} ố ộ

Begin

Push (MO,no);

{hàm depth ghi l Depth(n0)=0; ạ ộ ỗ i đ sâu m i

đ nh} ỉ

DONG=null;

While MO <> null do

begin

n:=pop (MO); if n˛ DICH then exit;

push (DONG, n);

if depth(n)<=d then For m˛ T(n) and mˇ DONG do

begin

Push (MO, m);

depth(m)=depth(n)+1;

end;

end;

Write (‘Không có l i gi i’); ờ ả

End

Thu t toán tìm ki m sâu d n (Depth_deepening_search) ầ ế ậ ủ ụ s s d ng th t c ẽ ử ụ

36

tìm ki m sâu h n ch nh th t c con: ế ư ủ ụ ế ạ

Procedure Depth_deepening_search;

Begin

For d:=0 to max do

Depth_limited_search(d);

If thành công then exit;

End;

3.3. Nh n xét. ậ

- Luôn tìm ra nghi m (n u bài toán có nghi m), mi n là ch n max đ ế ễ ệ ệ ọ ủ

- Có đ ph c t p th i gian là O(k

d) (gi ng tìm ki m r ng)

l n (gi ng nh tìm ki m theo chi u r ng) ế ớ ề ộ ư ố

ộ ứ ạ ờ ế ộ ố

- Có đ ph c t p không gian là O(k*d) (gi ng tìm ki m sâu) ộ ứ ạ ế ố

- Gi ng áp d ng cho các bài toán có ả i thu t tìm ki m sâu d n th ế ậ ầ ươ ụ

không gian tr ng thái l n và đ sâu c a nghi m không bi c. ủ ệ ạ ộ ớ t tr ế ướ

4. Ph ng pháp tìm ki m t t nh t đ u tiên (Best First Search). ươ ế ố ấ ầ

ng pháp c C hai k thu t tìm ki m r ng và tìm ki m sâu đ u là ph ộ ế ế ề ậ ả ỹ ươ ơ

b n đ khai thác không gian bài toán. Chúng đ u vét c n không gian đ tìm ra ả ể ể ề ạ

i gi i theo th t c xác đ nh tr c. M c dù có s d ng tri th c v tr ng thái l ờ ả ủ ụ ị ướ ứ ề ạ ử ụ ặ

c a bài toán đ h ủ ể ướ ộ ng d n tìm ki m nh ng không ph bi n. Cho dù có m t ổ ế ư ế ẫ

s u đi m, nh ng chúng là nh ng k thu t th c hi n m t cách máy móc. ỹ ố ư ữ ự ư ệ ể ậ ộ

Chính vì v y chúng b gán tên là “ ậ ị k thu t tìm ki m mù”. ỹ ế ậ

4.1. K thu t tìm ki m t ậ ế ỹ ố t nh t đ u tiên. ấ ầ

K thu t tìm ki m t t nh t đ u tiên tìm l i gi i có dùng tri th c v bài ế ậ ỹ ố ấ ầ ờ ả ứ ề

toán đ h ng d n. Tri th c này h ng vi c tìm ki m v nút l i gi i trong ể ướ ứ ẫ ướ ệ ề ế ờ ả

không gian bài toán.

c xem xét, ng T i m i nút đ ỗ ạ ượ ườ ế i ta s quy t đ nh vi c tìm ki m ti p ế ị ẽ ệ ế

ng s d n đ n l i gi i. t c theo nhánh nào tin t ụ ưở ẽ ẫ ế ờ ả

Trong các ch ươ ng trình trí tu nhân t o, k thu t tìm ki m t ạ ệ ế ậ ỹ ố ấ ầ t nh t đ u

tiên s d ng hàm đánh giá. Hàm này dùng các thông tin hi n t i v m c đ ử ụ ệ ạ ề ứ ộ

37

i nút đó đ gán giá tr cho nút này, g i là tr ng s quan tr ng c a bài toán t ủ ọ ạ ể ọ ọ ị ố

c xem xét trong lúc tìm ki m. Thông th ng, nút có c a nút. Giá tr này đ ủ ị ượ ế ườ

c ch n trong quá trình tìm ki m. tr ng s nh (l n) nh t s đ ỏ ớ ấ ẽ ượ ọ ố ế ọ

4.2. Hàm đánh giá

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, ta s xác d 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á . ự ầ ủ ạ ượ ọ

Ph ng pháp tìm ki m kinh nghi m là ph ng pháp tìm ki m có s ươ ế ệ ươ ế ử

i m i b d ng đ n hàm đánh giá. Trong quá trình tìm ki m, t ụ ế ế ạ ỗ ướ ọ c ta s ch n ẽ

tr ng thái k ti p là tr ng thái có nhi u h a h n d n t ề ứ ẹ ế ế ẫ ớ ạ ạ i đích nhi u nh t. ề ấ

Quá trình tìm ki m trong không gian tr ng thái có s d ng hàm đánh giá ử ụ ế ạ

ướ ơ ả

bao g m các b c c b n sau: ồ • Bi u di n thích h p các tr ng thái và các toán t chuy n tr ng thái ể ễ ạ ợ ử ể ạ

• Xây d ng hàm đánh giá ự

• Thi t k chi n l ế ế ế ượ c ch n tr ng thái ạ ọ m i b c ở ỗ ướ

4.3. u và nh c đi m c a ph ng pháp tìm ki m t Ư ượ ủ ể ươ ế ố t nh t đ u tiên. ấ ầ

4.3.1. u đi m. Ư ể

- Ph ng pháp tìm ki m t t nh t đ u tiên t ươ ế ố ấ ầ ổ ợ ủ h p các u đi m c a ư ể

ph ươ ng pháp tìm ki m r ng và tìm ki m sâu. ộ ế ế

- u đi m ch y u c a ph ng pháp tìm ki m t t nh t đ u tiên là Ư ể ủ ế ủ ươ ế ố ấ ầ

dùng tri th c đ d n d t vi c tìm ki m. Tri th c này giúp ng i ta b t đ u t ứ ể ẫ ứ ệ ế ắ ườ ắ ầ ừ

đâu là t t nh t và cách t t nh t đ ti n hành tìm l i gi i. ố ấ ố ấ ể ế ờ ả

- Tìm ki m t t nh t đ u tiên tuân theo cách suy lý c a m t chuyên gia. ế ố ấ ầ ủ ộ

Do đó có th th y rõ đ ể ấ ườ ng đi h n tìm ki m r ng và tìm ki m sâu. ộ ế ế ơ

4.3.2. Nh ượ c đi m. ể

- Quá trình tìm ki m có th đi xa kh i l i gi ỏ ờ ể ế ả ộ i. K thu t này ch xét m t ậ ỹ ỉ

38

ph n c a không gian và coi đó là ph n h a h n h n c . ơ ả ầ ứ ẹ ầ ủ

4.4. Gi i thu t. ả ậ

D li u t ng t nh gi i thu t tìm ki m rông và sâu, s d ng danh ữ ệ ươ ự ư ả ử ụ ế ậ

sách MO đ l u các đ nh s xét. ể ư ẽ ỉ

Procedure BFS; {Best First Search}

Begin

Push(MO,n0);

while MO <> null do

begin

i := Pop(MO); if i ˛ Goals then

exit;

for j ˛ T(i) do

Push(MO,j);

Sort(MO); {theo th t c a hàm đánh giá} ứ ự ủ

end;

write(‘Khong co loi giai’);

end;

4.5. Các ví d .ụ

ng đi trên b n đ giao thông, ta có th Ví d 1ụ Trong bài toán tìm ki m đ ế ườ ả ồ ể

ng chim bay t m t thành ph đang xét t i m t thành ph l y đ dài c a đ ấ ủ ườ ộ ừ ộ ố ớ ộ ố

đích làm giá tr c a hàm đánh giá c a thành ph đang xét. ị ủ ủ ố

1 2 3 8 4 7 6 5

3 2 8 6 4 7 1 5

Ví d 2ụ Bài toán 8 s . Chúng ta có th đ a ra hai cách đánh giá ể ư ố

u = đích =

1(u) là s quân không n m đúng v

- Hàm h1: V i m i tr ng thái u thì h ỗ ạ ớ ằ ố ị

trí c a nó trong tr ng thái đích. ủ ạ

39

V i ví d trên, ta có h1(u)=4 ụ ớ

- Hàm h2: G i họ 2(u) là 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 l n d ch chuy n ít nh t theo hàng ho c c t đ đ a m t quân ặ ộ ể ư ố ầ ể ể ấ ộ ị ở ị v

trí c a hi n t i tr ng thái đích. i t ệ ạ ớ ạ ủ

V i ví d trên, 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) ấ ể ầ ị

5. Tìm ki m đ ế ườ ng đi có giá thành c c ti u - Thu t toán AT ự ể ậ

0 và t pậ

Cho đ th G= (V, E) bi u di n bài toán v i đ nh xu t phát n ễ ồ ị ớ ỉ ể ấ

đích DICH xác đ nh. ị

ifi ni+1 t n chi phí c(n

i, ni+1 ) ký hi uệ

i, ni+1)˛ E

V i m i phép chuy n tr ng thái n ể ạ ớ ỗ ố

c(u) v i u= (n ớ

c(u)

ni ni+1

ề V n đ : ấ

pc (

)

uc )(

min

= (cid:229)

0

˛ pu

fi Tìm đ ng đi p: n n* ˛ DICH sao cho ườ

Ch ng h n trong bài toán tìm đ ạ ẳ ườ ủ ng đi trong b n đ giao thông, giá c a ồ ả

cung (i,j) chính là đ dài c a đ ủ ộ ườ ng n i thành ph i v i thành ph j. Đ dài ớ ộ ố ố ố

đ ng đi đ ng đi. V n đ đ t ra ườ ượ c xác đ nh là t ng đ dài các cung trên đ ộ ổ ị ườ ề ặ ấ

tr ng thái ban đ u đ n tr ng thái đích. ườ ng đi ng n nh t t ắ ấ ừ ạ ế ạ ầ

=

là tìm đ • Ph ng pháp gi ươ i ả

)( uc

k

(

const

)

Eu

pc (

)

min

#

p

min

˛ " fi (cid:219) fi (cid:222) thì Dùng ph ng pháp 1) N u ế ươ

tìm ki m theo chi u r ng. ề ộ ế

0 đ n n, khi đó bài toán có

2) G i g(n) là giá c a đ đ nh n ủ ườ ọ ng đi c c ti u t ự ể ừ ỉ ế

{

}

=

th phát bi u nh sau: ể ư ể

n

n

DICH

)

min

/)( nng

DICH

0

k

( ng k

0

˛ fi ˛ Tìm đ ng đi t đ nh sao cho: ườ ừ ỉ

=ng ( 0 ) {

=

+

mg (

)

ng )(

mnc ,(

})

Lúc đó, ta có:

min Emn ) ,(

40

˛

Dùng 2 danh sách MO, DONG nh trên. T i m i th i đi m ch n đ nh n ư ể ạ ờ ọ ỗ ỉ

ỉ

trong MO ra xét là đ nh tho . ả • Thu t toán AT ậ

0

Input:

ồ ị ấ ỉ

Đ th G = (V,E), Đ nh xu t phát n Hàm chi phí c: E fi R+

˛ c(i,j): xác đ nh chi phí chuy n t E ể ừ ỉ đ nh i sang đ nh j v i (i,j) ỉ ớ ị

T p các đ nh đích DICH ậ ỉ

Output:

0 đ n đ nh n

* ˛

Đ ng đi t đ nh n DICH sao cho g(n*) = c(p) = min{g(n)| ườ ừ ỉ ế ỉ

n˛ DICH}.

Procedure AT;

{ Dùng g0(n) là chi phí c c ti u c a đ ng đi t đ nh xu t phát đ n đ nh n t ể ủ ườ ự ừ ỉ ế ấ ỉ ạ i

th i đi m đang xét và xem nh hàm g} ư ể ờ

Begin

g(n0):= 0;

push(MO, n0);

While MO<>null do

=

ng

:)(

mg (

)

min m˛ MO

begin

if n˛ DICH then

exit {xay dung duong di cuc tieu}

push(DONG, n);

if T(n) <>null then

for m˛ T(n) do

if mˇ MO+DONG then

begin

41

push(MO,m);

g(m):=g(n)+c(n,m);

cha(m):=n;

end

else

if g(m) >g(n)+c(n,m) then

begin

g(m):=g(n)+c(n,m);

cha(m):=n;

end;

end;

writeln(‘Khong co duong di’);

End;

Ví d 1. ụ Bài toán Tháp Hà N i -v i chi phí chuy n đĩa nh sau: ư ể ớ ộ

Chi phí chuy n đĩa nh gi a 2 c c g n 1 ọ ầ ỏ ữ ể

Chi phí chuy n đĩa nh gi a 2 c c xa 3 ỏ ữ ể ọ

Chi phí chuy n đĩa v a gi a 2 c c g n 2 ọ ầ ừ ữ ể

Chi phí chuy n đĩa v a gi a 2 c c xa 5 ừ ữ ể ọ

Chi phí chuy n đĩa l n gi a 2 c c g n 4 ọ ầ ữ ể ớ

Chi phí chuy n đĩa l n gi a 2 c c xa 8 ữ ể ớ ọ

Xu t phát t đ nh (1,1,1), ta có g(1,1,1) = 0. ấ ừ ỉ

Khi xét đ nh ng ng : ỉ (1,1,1) ta có các đ nh k và chi phí t ỉ ề ươ ứ

g(1,1,2) = 1; g(1,1,3) = 3; nh v y đ nh (1,1,2) đ ư ậ ỉ ượ c ch n ọ

Các đ nh k c a (1,1,2) có giá tr hàm g: ề ủ ỉ ị

g(1,1,3) = 2 ( đây giá c a đ nh (1,1,3) đ c tính l ủ ỉ ở ượ ạ ọ i); g(1,3,2) = 5; ch n

(1,1,3), ta l i tính ti p giá tr hàm g c a các đ nh k v i đ nh này: đ nh ỉ ạ ề ớ ỉ ủ ế ỉ ị

g(1,2,3) = 2; l i ch n đ nh (1,2,3); chi phí c a các đ nh k v i nó: ạ ọ ỉ ề ớ ủ ỉ

g(1,2,1) = 2 + 3 = 5; g(1,2,2) = 2 + 1 = 3; ch n đ nh (1,2,2) ọ ỉ

g(1,2,1) = 3 +1 = 4 (đ c tính l i); g(3,2,2) = 3 + 8 = 11, ch n đ nh ượ ạ ọ ỉ

42

(1,2,1)

C ti p t c nh v y cho đ n khi xét đ nh (3,3,3). ứ ế ụ ư ậ ế ỉ

A

8

5

4

C

n0=A DICH={F,K}

B

D

2

9

3

1

1

F G

E

I

H

2

K

Ví d 2ụ

ướ

g(n)

Có th trình bày quá trình tìm ki m b ng b ng d ế ể ả ằ i đây. Ký hi u giá tr g(n) ệ ị

là ch s d i t ỉ ố ướ ươ ứ ng ng đ nh n: n ỉ

DONG T(i) i

B C D G H I

A A C A C D A C D G A C D G A C D G B K E F MO A0 B8 C4 D5 B8 D5 G5 B8 G5 H14 I6 B8 H14 I6 B8 H14 K8 H14 K8 E10 F11

A C D G I B K

fi i c a bài toán là A D fi I fi K và chi phí c a đ ng đi tìm đ c là 8 L i gi ờ ả ủ ủ ườ ượ

Ví d 3.ụ

n0 = A; DICH = {G}

5

6

A

3 C 1

B

4

7

4

D

8

3

E

9 G 5

2

F

i T(i) DONG

43

A C B C D A B E F D MO A0 B5 C3 D6 B4 D6 E7 F11 A A C

A C E A C F G B C F C D E G D6 E7 F11 E7 F9 G15 F9 G15 G14 A C B A C B D A C B D E A C B D E F

B D E F G

fi Đ ng đi tìm đ c p: A D fi F fi G. Chi phí c a đ ng đi là 14. ườ ượ ủ ườ

*

6. Tìm ki m c c ti u s d ng hàm đánh giá - Thu t toán A ự ể ử ụ ế ậ

Đ i v i nhi u bài toán, vi c tìm ki m đ ng đi c c ti u s đ ố ớ ệ ế ề ườ ể ẽ ượ ự c đ nh ị

h ng t p trung xung quanh đ ng đi t t nh t; n u s d ng các thông tin ướ ậ ườ ố ế ử ụ ấ

v bài toán g i là các heuristic. đ c t ặ ả ề ọ

ng đi v i chi phí c c ti u, ng Đ i v i vi c tìm ki m đ ệ ố ớ ế ườ ự ể ớ ườ ử ụ i ta s d ng

hàm đánh giá heuristic nh sau: ư

G i g(n): giá c c ti u đ ng đi t n c. ự ể ườ ọ ừ 0fi n. T i đ nh n, g(n) xác đ nh đ ạ ỉ ị ượ

G i h(n): giá c c ti u đ ng đi t n ự ể ọ ườ ừ fi DICH, h(n) không xác đ nh đ ị ượ c

(cid:222) ng i ta tìm cách ng giá tr này. ườ c l ướ ượ ị

ng đi t Đ t ặ f0(n)=g0(n)+h0(n): d đoán chi phí c c ti u c a đ ủ ự ự ể ườ ừ

n0fi DICH có đi qua đ nh n. ỉ

g0(n) là chi phí c a đ ng đi t đ nh xu t phát đ n đ nh n t ủ ườ ừ ỉ ế ấ ỉ ạ ể i th i đi m ờ

đang xét. h0(n) là ng (d đoán) chi phí đ ng đi t c l ướ ưọ ự ườ ừ ỉ đ nh n đ n đích. ế

0(n) c a h(n) không có m t ph

Vi c ch n giá tr x p x h ị ấ ệ ọ ỉ ủ ộ ươ ng pháp t ng quát ổ

và đ ượ c xem nh m t ngh thu t. Giá tr này s do các chuyên gia đ a ra. ị ư ộ ư ẽ ệ ậ

Lúc này gi i thu t tìm ki m c c ti u s thay vi c xét hàm g b i hàm f. ả ự ể ẽ ế ệ ậ ở

Tuy nhiên, ng c 2 k t qu nh sau: ườ i ta cũng ch ng minh đ ứ ượ ả ư ế

)( uc

"> 0

Eu

0

0 )( nh

)( nh

n

0(n) có tính ch t: ấ

˛ " £ £ K t qu 1 và ả : N u hế ế thì thủ

0(n) đ ch n ph n t ọ

=

)

ng )(

ng ( *

trong MO ra xét (thay g(n)) s t c TKCT s d ng hàm f ụ ử ụ ầ ử ể ẽ

min DICH

n˛

44

cho đ ng đi t n ườ ừ 0fi n*˛ DICH sao cho

0

0

1h và

K t qu 2: Gi dùng 2 hàm c l ng ế ả s ả ử ướ ượ ả ấ 2h tho tính ch t:

(

nmh ),

(

0 nhmh ) )( 2

0 2

£ - (giá c c ti u c a đ ng đi t m fi n) và ủ ự ể ườ ừ

Nn

0,

nh )(

0 nh )( 1

0 nh )( 2

£ £ £ ˛ " . Khi đó #DONG2 £ #DONG1

Nh n xét: ậ

h 0

” h

(cid:222) ph ng án t ươ ố t nh t ấ

0h

” 0

(cid:222) ph ng án t ươ ồ i nh t ấ

*

Thu t toán A ậ

0

Input:

ồ ị ấ ỉ

Đ th G = (V,E), Đ nh xu t phát n Hàm chi phí c: E fi R+

˛ c(i,j): xác đ nh chi phí chuy n t E ể ừ ỉ đ nh i sang đ nh j v i (i,j) ỉ ớ ị

0, (t

h: V fi R+; h(n) xác đ nh d đoán chi phí t ng đi t đ nh n ự ị i u c a đ ố ư ủ ườ ừ ỉ

ng t g)) đ n đích. (ký hi u h thay cho h ệ ế ươ ự

T p các đ nh đích DICH ậ ỉ

Output:

0 đ n đ nh n

* ˛

Đ ng đi t đ nh n DICH ườ ừ ỉ ế ỉ

Procedure A* ;

Begin

g(n0):= 0;

push(MO, n0);

While MO<>null do

=

nf

:)(

mf (

)

min m˛ MO

begin

if n˛ DICH then

exit {xay dung duong di cuc tieu}

push(DONG, n);

if T(n) <>null then

45

for m˛ T(n) do

if mˇ MO+DONG then

begin

push(MO,m);

tính f(m);

cha(m):=n;

end

else

if fm iớ (m) > fcũ(n) then

begin

f(m):= fm iớ (m);

cha(m):=n;

end;

end;

writeln(‘Khong co duong di’);

End;

0 nh sau: ư

Ví d 1. ụ Cho đ th bi u di n bài toán và giá tr d đoán h ễ ồ ị ể ị ự

n A B C E F G H D

h0(n) 14 10 10 4 0 5

5

4 7

2

5 A 3 B D

6

7

C 4

3

5

12

E

2

F

G 3 H

Tìm đ ng đi t đ nh ườ ừ ỉ A đ n đ nh H. ế ỉ

Tr c đ a vào danh sách MO ướ c tiên đ nh A đ ỉ ượ ư

g(A) = 0; h(A) = 14; f(A) = 14

46

Xét đ nh A, (đ a A vào danh sách DONG) ta có các đ nh k B, C, D: ư ề ỉ ỉ

g(B) = 5; f(B) = 15; g(C) = 3; f(C) = 13; g(D) = 7; f(D) = 12  ch n đ nh ỉ D. ọ

Xét đ nh D (đ a D vào danh sách DONG) có các đ nh k A, C, E. Đ nh A đã ư ề ỉ ỉ ỉ ở

trong danh sách DONG, ta tính l i f(C) và tính f(E): ạ

f(C) không thay đ i; f(E) = g(D) +c(D,E) + H(E) = 7 + 6 + 5 = 18; f(E) = 18, ổ

ch n đ nh i ỉ C, có các đ nh k A, D, E. Tính l ề ọ ỉ ạ f(E) = 12, ch n ọ E. Các đ nh k ỉ ề

c a E là C, D, F, G. Tính ủ f(F) = 14; f(G) = 16, ch n ọ F. Các đ nh k c a F là E, ề ủ ỉ

G, B và f(B), f(E), f(G) không đ i, ch n f(H) = ọ B. Các đ nh k c a B là F, H. ề ủ ổ ỉ

i f(H) = 15 và d ng. 17, ch n ọ G. Tính l ạ ừ

Đ ng đi tìm đ c là p: A  C  E  G  H v i chi phí đ ng đi là 15 ườ ượ ớ ườ

7. Ph ươ ng pháp tìm ki m leo đ i (hill-climbing search) ồ ế

7.1. K thu t tìm ki m leo đ i. ồ ế ậ ỹ

Tìm ki m leo đ i 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 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ó h a h n nhi u ủ ứ ế ẹ ọ ố ỉ ỉ

nh t đ phát tri n, đ nh này đ c xác đ nh b i hàm đánh giá. ấ ể ể ỉ ượ ở ị

7.2. Gi i thu t. ả ậ

Input:

0.

Đ th G = (V,E), đ nh xu t phát n ồ ị ấ ỉ

Hàm đánh giá h(n) đ i v i m i đ nh n. ố ớ ỗ ỉ

T p đ nh đích DICH ậ ỉ

Output:

0 đ n DICH

Đ ng đi t đ nh n ườ ừ ỉ ế

Procedure HLC; {Hill Climbing Search} begin

Push(MO,n0); while MO <> null do

begin

47

i = Pop(MO); if T(i) ˙ DICH <> null then

begin

L:= null; for j ˛ T(i) do

if j ch a xét then ư

đ a j vào danh sách L ư

hàm đánh giá; s p x p L theo th t ắ ứ ự ế

chuy n danh sách L vào đ u danh sách MO; ể ầ

end;

write(‘Khong co loi giai’);

end;

7.3. Nh n xét. ậ

Ph ng pháp tìm ki m leo đ i chú tr ng tìm h ươ ế ồ ọ ướ ế ng đi d d n đ n ễ ẫ

tr ng thái đích nh t. Cách đó đ ấ ạ ượ ư ế c đ a ra nh m làm gi m công s c tìm ki m. ả ứ ằ

Thu t toán tìm ki m leo đ i th c ch t là thu t toán tìm ki m theo chi u sâu, ự ế ế ề ậ ấ ậ ồ

song t i m i b ạ ỗ ướ c ta s u tiên ch n m t tr ng thái có h a h n nhanh t ạ ẽ ư ứ ẹ ọ ộ ớ i

đich nh t đ phát tri n tr c. V n đ quan tr ng là bi t khai thác kheo léo ấ ể ể ướ ề ấ ọ ế

thông tin ph n h i đ xác đ nh h ng đi ti p và đ y nhnah quá trình tìm ồ ể ả ị ướ ế ẩ

ki m. Thông th ng ta gán m i tr ng thái c a bài toán v i m t s đo (hàm ế ườ ộ ố ủ ạ ỗ ớ

đánh giá) nào đó nh m đánh giá m c đ g n đích c a nó. Đi u đó có nghĩa là ứ ộ ầ ủ ề ằ

n u tr ng thái hi n th i là u thì tr ng thái v s đ ế ẽ ượ ệ ạ ạ ờ c phát tri n ti p theo n u v ế ể ế

k v i u và hàm đanh giá c a v đ t giá tr max (ho c min). ề ớ ủ ạ ặ ị

Tuy nhiên ph ng pháp này không đ c c i thi n so v i các ph ươ ượ ệ ả ớ ươ ng

pháp khác trong m t s tr ộ ố ườ ng h p sau: ợ

ng: nút đang xét t t h n các nút lân c n, nh ng đó • C c tr đ a ph ị ự ị ươ ố ơ ư ậ

không ph i là ph ng án t ả ươ ố ả t nh t trong toàn th , ví v y có th ph i ể ể ấ ậ

quay lui v nút tr c đ đi theo h ng khác. Gi ề ướ ể ướ ả ỏ i pháp này đòi h i

48

ghi nh l i nhi u đ ng đi. ớ ạ ề ườ

ng án nh nhau, • Cao nguyên b ng ph ng: Các giá tr c a các ph ẳ ị ủ ằ ươ ư

không xác đ nh đ c ngay h ng nào là t t h n trong vùng lân c n. ị ượ ướ ố ơ ậ

7.4. Các ví d .ụ

Bài toán trò ch i 8 s Ví d 1. ụ ơ ố.

2

tr ng thái đ u tr ng thái 8 6 2 1 3 4 1 8 3 4 ầ ạ ạ

đích

7 5 7 6 5

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ú nó trong ế ố ớ ị ữ ố ạ

tr ng thái đích. Tr ng thái có ti m năng d n đ n đí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.. ể ướ ạ ạ ị

Minh ho cây tìm ki m cho trò ch i này theo gi i thu t leo đ i trang ế ạ ơ ả ồ ở ậ

sau

Tr ng thái đ c ch n đi ti p ng mũi tên. ạ ượ h ế ở ướ ọ Ở ứ ấ m c 3 chúng ta th y

có hai tr ng thái cùng giá tr hàm đánh giá (= 3). Đây là tr ạ ị ươ ng h p “cao ợ

nguyên băng ph ng” nh nh n xét trên, n u ta ch n ph ậ ư ế ẳ ọ ươ ắ ng án kia thì ch c

49

ng h p này dành cho đ c gi ch n quá trình tìm ki m s khác đi nhi u. Tr ế ề ẽ ắ ườ ộ ợ . ả

8 6

2 1 7 3 4 5

h(u) = 4

8

2 1 3 4

8 6 7 3 4 5 2 1 7 6 2 1 7

3 4 5 h(u) = 5 h(u) = 3 8 6 5 h(u) = 5

2 3

8 1 6 2 1 7 3 4 5 8 6 7 2 1 7

3 4 5 h(u) = 3 h(u) = 3 8 4 5 6 h(u) = 4

2 8 6 3 4 5 1 7 2 1 7 3 8 6

4 5 h(u) = 2 h(u) = 4

1

2 3 8 4 5 6 7 h(u) = 1

2

1 1 7 3 4 5

8. Ph ươ ng pháp sinh và th . ử

- Tr

Chi n l c: ế ượ c này đ n gi n, g m ba b ả ơ ồ ướ

c h t t o ra m t gi ướ ế ạ ộ ả ệ i pháp. Trong vài bài toán c th đó là vi c ụ ể

50

ch n m t l i gi i trong không gian các l i gi i hay t o ra m t đ ng đi. ộ ờ ả ọ ờ ả ộ ườ ạ

- Th hai, th xem l

i gi i đó có thích h p không b ng cách so sánh ứ ử ờ ả ằ ợ

ph ươ ng án khác hay so sanh v i đi m cu i c n suy di n. ớ ố ầ ể ễ

- Ti p theo, n u l i gi i, l p l i t ế ờ ế i đ t đ ả ạ ượ c thì d ng, ng ừ c l ướ ạ ặ ạ ừ

b c đ u v i nút khác. ướ ầ ớ

i gi i thì s đ a đ n đích. Tuy V i ph ớ ươ ng pháp này n u bài toán có ll ế ờ ả ẽ ư ế

nhiên kích th ng tính toán. Vi c t o l i gi ướ c bài toán l n s tăng kh i l ớ ẽ ố ượ ệ ạ ờ ả i

ạ ban đ u có th th c hi n ng u nhiên, và cũng hy v ng ng u nhiên mà đ t ể ự ệ ầ ẫ ẫ ọ

đ i gi i, b i v y, không th không tính đ n ch m t vài h ng đi đ c l ượ ờ ả ở ậ ỉ ộ ể ế ướ ượ c

t, và lo i tr tr c các h ng không d n đ n l i gi i. c m nh n là t ả ậ ố ạ ừ ướ ướ ế ờ ẫ ả

ng các ch s chia h t cho 3. Ví d 1.ụ Tìm s có 6 ch s mà t ng bình ph ữ ố ố ổ ươ ữ ố ế

Giai đo n sinh: t o ra s có 6 ch s và ta g i các ch s t trái qua ữ ố ừ ữ ố ạ ạ ố ọ

ph i l n l t là a, b, c, d, e, f thì 0 < a <= 9 , 0 <= b, c, d, e, f <= 9. ả ầ ượ

Giai đo n th : n u a*a + b*b + c*c + d*d + e*e + f*f chia h t cho 3 thì ử ể ế ạ

chon, ng i, t o ra s khác. c l ượ ạ ạ ố

c g i là th a n u trong xâu không có hai ch Ví d 2. ụ M t xâu nh phân đ ộ ị ượ ư ế ọ ữ

s 1 đ ng k nhau. Tìm xâu nh phân th a có chi u dài n. ố ư ứ ề ề ị

Giai đo n sinh: T o ra m t xâu nh phân S có chi u dài n. ề ạ ạ ộ ị

Giai đo n th : Ki m tra có ph i xâu th a không? (Pos(‘11’,S) = 0). ư ử ể ạ ả

Trong hai ví d trên, sinh viên có th l p trình đ tìm t t c các l i gi ể ậ ụ ể ấ ả ờ ả i

t c các xâu nh phân th a có chi u dài n cho c a bài toán, ch ng hain tìm t ủ ẳ ấ ả ư ề ị

tr c.ướ

ổ Ví d 3. ụ M t b nh nhân có m t vài tri u ch ng, ch ng h n: s t cao v bu i ệ ộ ệ ứ ề ẳ ạ ộ ố

chi u, ho và m t m i ,…. Bác sĩ có ch n đoán nghi b lao ph i, ng i ta s ệ ề ẩ ỏ ổ ị ườ ẽ

cho làm ngay xét nghi m, n u đúng là d ệ ế ươ ị ệ ng tính thì k t lu n và đi u tr b nh ậ ế ề

c lai, băt bu c bác sĩ ph i chuy n h lao ph i, ng ổ ượ ể ả ộ ướ ộ ng suy nghĩ sang m t

51

v.v… b nh khác, ệ

9. Ph ng pháp tho mãn ràng bu c. ươ ộ ả

Ph ng pháp tho mãn ràng bu c h tr cho ph ng pháp sinh và th , khi ươ ổ ợ ả ộ ươ ử

chú ý t ớ ụ i m t s ràng bu c áp đ t lên các nút trong không gian bài toán. M c ộ ố ặ ộ

đích đ t ra là xác đ nh đ ng đi trong đ th không gian bài toán, đ ng đi t ặ ị ườ ồ ị ườ ừ

ậ tr ng thái đ u đ n tr ng thái cu i đáp ng m t vài ràng bu c nào đó. Do v y ứ ế ầ ạ ạ ố ộ ộ

quá trình tìm ki m l i gi i bao g m hai ph n liên quan ch t ch v i nhau: ế ờ ả ẽ ớ ầ ặ ồ

- Tìm ki m trong không gian các ràng bu c. ế ộ

- Tìm ki m trong không gian các bài toán ban đ u. ế ầ

N i dung c a ph ng pháp nh sau: Th c hi n các b ủ ộ ươ ư ự ệ c t ướ ừ a) đ n e) ế

d i gi i đày đ c a bài toán ho c t t c các ướ i đây cho đ n khi tìm đ ế c l ượ ờ ả ủ ủ ặ ấ ả

đ ươ ng đ u đã duy t qua nh ng không cho k t qu . ả ư ề ệ ế

a) Ch n m t đ nh ch a đ ộ ỉ ư ượ ọ c xét trong đ th tìm ki m. ồ ị ế

ọ b) Áp d ng các lu t suy di n trên các ràng bu c đ i v i đ nh đã ch n ố ớ ỉ ụ ễ ậ ộ

đ t o ra t p các ràng bu c m i. ể ạ ậ ộ ớ

c) N u t p các ràng bu c m i có mâu thu n thì đ a ra thông báo đ ế ậ ư ẫ ộ ớ ườ ng

đi h n th i t i nút đang xét d n t i b t c. ờ ớ ệ ẫ ớ ế ắ

d) N u t p ràng bu c mô t i gi i đ y đ c a bài toán thì d ng và ế ậ ộ l ả ờ ả ầ ủ ủ ừ

c lai, sang b c sau. đ a ra thông báo thành công. Ng ư ượ ướ

e) Áp d ng các lu t bi n đ i không gian tr ng thái t ng ng đ t o ra ụ ế ậ ạ ổ ươ ứ ể ạ

i gi i b ph n, t ng h p v i t p các ràng bu c hi n th i. Thêm l ờ ả ộ ậ ươ ớ ậ ệ ợ ộ ờ

các l i gi i b ph n này vào đ th tìm ki m. ờ ả ộ ồ ị ế ậ

Ví d . ụ Xét bài toán đi n các ch s phân bi ề ữ ố ệ t thay cho các ch cái S, E, N, D, ữ

M, O, R, Y sao cho phép c ng sau là đúng: ộ

SEND

MORE

MONEY

Các ràng bu c ban đ u: ộ ầ

- Các ch cái khác nhau không nh n cùng m t giá tr . ị ữ ậ ộ

52

- Các ràng bu c s h c (c ng có nh ho c không có nh . ớ ộ ố ọ ặ ộ ớ

G i C1, C2, C3, C4 l n l ph i sang trái. Khi ầ ượ ọ t lá s nh c a các c t t ớ ủ ộ ừ ả ố

đó ta xây d ng các ràng bu c c th nh sau: ộ ụ ể ư ự

(1) E, N, D,O, R, Y thu c t p {0 ..9} ộ ậ

(2) S, M thu c t p {1..9} ộ ậ

C1, C2, C3, C4 thu c t p {0,1} (3) ộ ậ

(4) D + E = Y + 10*C1

(5) N + R + C1 = E + 10*C2

(6) E + O + C2 = N + 10*C3

(7) S + M + C3 = O + 10*C4

(8) M = C4

T ràng bu c (2) và (8) suy ra M = 1 và C4=1 (9) ừ ộ

T ràng bu c (7) và (9) suy ra S +C3 = O + 9, lúc này có hai ph ng án ừ ộ ươ

đ l a ch n: ể ự ọ

Ph ng án 1 : ươ

C3 = 0, khi đó ta có S = O + 9, nh v y (10-1) ư ậ S = 9 và O = 0

T ràng bu c (6) ta có E + C2 = N, suy ra C2 = 1 và ừ ộ

E + 1 = N (11-1)

T ràng bu c (5), ta có R + C1 = 9, nh v y ư ậ R = 8 và C1 = 1 (12-1) ừ ộ

(do k t h p v i các ràng bu c (2) và (10-1). ế ợ ớ ộ

T ràng bu c (4) ta có D + E = Y +10. Đ n b ừ ế ộ ứơ ả c này ta có th kh ng ể

đ nh các giá tr c a D, E, Y ch có th nh n trong t p {2, 3, 4, 5, 6, 7}. Ngoài ị ị ủ ể ậ ậ ỉ

ra D + E >= 12. Vì v y ch có các kh năng sau có th xãy ra: ể ậ ả ỉ

- D = 5 và E = 7

- D = 7 và E = 5 (hai tru ng h p này Y = 2) ờ ợ

- D = 6 và E = 7

- D = 7 và E = 6 (hai tr ng h p sau Y = 3) ườ ợ

ớ Xét kh năng th nh t. T ràng bu c (11-1) ta suy ra N = 8 mâu thu n v i ừ ứ ả ấ ẫ ộ

53

(12-1) nên b lo i ị ạ

ệ Xét kh năng th hai. T ràng bu c (11-1) ta suy ra N= 6. Ki m tra đi u ki n ừ ứ ể ề ả ộ

bài toán đ u tho mãn. V y ta có nghi m là: ệ ề ả ậ

S = 9, E = 5, N= 6, D = 7, M= 1, O = 0, R = 8, Y = 2.

Xét kh năng th ba. T ràng bu c (11-1) suy ra N = 8 mâu thu n v i (12-1) ứ ừ ả ẫ ớ ộ

Xét kh năng th t . T ràng bu c (11-1) suy ra N=7 = D mâu thu n. ứ ư ừ ả ẫ ộ

Ph ng án 2. ươ

C3 = 1. T ràng bu c (7) ta có S = O + 8, suy ra S = 8 và O = 0(10-2) ừ ộ

(vì M=1 và S <= 9).

ậ T ràng bu c (6) ta có E = N +10 mâu thu n v i ràng bu c (1). v y ừ ẫ ộ ộ ớ

ph ng án 2 không có l i gi i. ươ ờ ả

10.Cài đ t m t s gi i thu t. ộ ố ả ặ ậ

c: ướ ộ ố

M t s quy • Gi s đ th G đ c cho b i ma tr n k A. ả ử ồ ị ượ ề ậ ở

• Các danh sách MO và DONG đ ượ ư ớ c l u trong cùng m t m ng, v i ả ộ

các ch s riêng. ỉ ố

• M ng logic Dau dùng đ đánh d u các đ nh đã xét (n m trong danh ấ ể ả ằ ỉ

sách DONG

10.1. Tìm ki m r ng. ộ ế

• Danh sách MO và DONG đ c l u trong m ng Q, d và c là ch s ượ ư ỉ ố ả

ầ ử ầ đ u và cu i c a queue Q. ố ủ

c a ph n t ủ • V = { 1..n}

• Th t c Duyet_rong(i) đánh d u t t c các đ nh t ủ ụ ấ ấ ả ỉ ừ ể ế i có th đ n

đ c đ nh đó. ượ ỉ

Procedure Khoitao;

Begin

Fillchar (Dau, n, True);

End;

54

Procedure Duyet_rong (i:byte);

Var Q: array [1..100] of byte;

d, c, j, k: byte;

Begin

d:=1; {Kh i t o hàng đ i r ng } ợ ỗ ở ạ

c:=1;

Q[c]:= i;

Dau[i]:= false;

While d<=c do

begin

j:= Q[d];

inc(d);

for k:=1 to n do

if (A[j,k]=1) and Dau[k] then

begin

inc(c);

Q[c]:=k;

Dau[k]:=false;

end;

end;

End;

0 đ n đ nh j

0 c a đ th G. ủ ồ ị

ng đi t đ nh i Ví d 1. ụ Tìm đ ườ ừ ỉ ế ỉ

- Dòng đ u tiên ch a 3 s n, i

D li u đ c l u vào file Text có c u trúc nh sau: ữ ệ ượ ư ư ấ

0, j0 (n là s đ nh c a đ th ) ủ ồ ị

ứ ầ ố ố ỉ

t ch a giá tr n dòng c a ma tr n A. - n dòng ti p theo l n l ế ầ ượ ủ ứ ậ ị

Tên file đ c nh p t bàn phím khi th c hi n ch ng trình. ượ ậ ừ ự ệ ươ

Giá tr c a m ng Truoc t v trí j Truoc[j] xác đ nh đ nh đ ng tr c j trong ị ủ ả ạ ị ứ ị ỉ ướ

đ ng đi tìm đ c. ườ ượ

Program đuongdi;

55

Var

A: array[1..50,1..50] of byte;

Dau: array[1..50] of boolean;

Truoc: array[1..50] of byte;

n, i0, j0: byte;

Procedure khoitao;

Var

i, j : byte;

f:text;

tenfile:string;

Begin

write(‘ten file’);

readln(tenfile);

assign(f, tenfile);

reset(f);

readln(f,n,i0,j0);

for i:=1 to n do

begin

for j:=1 to n do

read(f, A[i,j]);

readln(f);

end;

close(f);

Fillchar (Dau,n,true);

End;

Procedure BFS(i:byte);

Var

Q: array [1..50] of byte;

d,c,j,k: byte;

56

Begin

d:=1;

c:=1;

Q[c]:=i;

Dau[i]:=false;

Truoc[i] := 0;

While d<=c do

begin

j:=Q[d];

inc(d);

for k:=1 to n do

if (A[j,k]=1) and Dau[k] then

begin

inc(c) ;

Q[c]:=k;

Dau[k]:=false;

Truoc[k] := j;

end;

end;

End;

Procedure inkq(j: byte);

Begin

if Truoc[j] <> 0 then

inkq(truoc[j]);

write(j:4);

End;

Procedure Duyet;

Var i:byte;

Begin

57

BFS(i0);

if Dau[j0] then

inkq(j0)

else

writeln(‘ Khong co duong di’);

End;

BEGIN {main}

Khoitao;

Duyet;

Readln;

END.

Ví d 2.ụ Tìm s thành ph n liên thông c a m t đ th . ộ ồ ị ầ ủ ố

D li u đ c l u vào file Text có c u trúc nh sau: ữ ệ ượ ư ư ấ

- Dòng đ u tiên ch a s n (s đ nh c a đ th ) ủ ồ ị ứ ố ố ỉ ầ

t ch a giá tr n dòng c a ma tr n A. - n dòng ti p theo l n l ế ầ ượ ứ ủ ậ ị

- Tên file đ c nh p t bàn phím khi th c hi n ch ng trình. ượ ậ ừ ự ệ ươ

Program lienthong;

Var

A: array[1..50,1..50] of byte;

Dau: array [1..50] of boolean;

n, So:byte;

Procedure khoitao;

Var

i, j : byte;

f:text;

tenfile:string;

Begin

write(‘ten file’);

58

readln(tenfile);

assign(f, tenfile);

reset(f);

readln(f,n);

for i:=1 to n do

begin

for j:=1 to n do

read(f, A[i,j]);

readln(f);

end;

close(f);

Fillchar (Dau,n,true);

So:=0;

End;

Procedure BFS(i:byte);

Var

Q: array [1..50] of byte;

d,c,j,k: byte;

Begin

d:=1;

c:=1;

Q[c]:=i;

Dau[i]:=false;

While d<=c do

begin

j:=Q[d];

inc(d);

for k:=1 to n do

if (a[j,k]=1) and Dau[k] then

59

begin

inc(c) ;

Q[c]:=k;

Dau[k]:=false;

end;

end;

End;

Procedure Duyet;

Var

i:byte;

Begin

For i:=1 to n do

If Dau[i] then

begin

inc(So);

BFS (i);

end;

writeln(‘So thành ph n liên thông:’, So); ầ

End;

BEGIN {main}

Khoitao;

Duyet;

Readln;

60

END.

10.2. Tìm ki m sâu. ế

thi t nh duy t r ng, do MO ho t đ ng nh stack nên dùng V i gi ớ ả ế ạ ộ ệ ộ ư ư

th t c đ quy. ủ ụ ệ

Procedure DFS (i:byte); {Depth First Search}

{Xu t phát t c xét khi tìm ki m theo chi u sâu} ấ ừ ỉ đ nh i, đánh d u các đ nh đ ấ ỉ ượ ế ề

Var

j: byte;

Begin

Dau[i]:=false;

For j:=1 to n do

If (a[i,j]=1) and Dau[j] then

DFS (j);

End;

ng đi t Ví d 1. ụ Tìm đ ườ ừ ỉ đ nh i0 đ n đ nh j0. ế ỉ

Program Duong_di;

Var

A: array[1..50,1..50] of byte;

Truoc: array [1..50] of byte;

Dau: array [1..50] of boolean;

n, i0, j0: byte;

Procedure Khoitao;

Var

i, j : byte;

f:text;

tenfile:string;

Begin

write(‘ten file’);

61

readln(tenfile);

assign(f, tenfile);

reset(f);

readln(f,n,i0,j0);

for i:=1 to n do

begin

for j:=1 to n do

read(f, a[i,j]);

readln(f);

end;

close(f);

Fillchar (Dau,n,true);

End;

Procedure DFS (i:byte);

Var

j: byte;

Begin

Dau[i]:=false;

For j:=1 to n do

If (a[i,j]=1) and Dau[j] then

DFS (j);

End;

Procedure inkq(j: byte);

Begin

if Truoc[j] <> 0 then

inkq(truoc[j]);

write(j:4);

End;

62

Procedure duyet;

Begin

DFS(i0);

if dau[j0] then

inkq(j0)

else

writeln(‘Khong co duong di’);

End;

BEGIN {main}

Khoitao;

Duyet;

Readln;

END.

Ví d 2.ụ Tìm t ấ ả t c hoán v c a (1,2,...n) ị ủ

Program hoanvi;

Var

A:array [1..50] of byte;

n:byte;

Dau: array [1..50] of boolean;

Procedure Khoitao;

Begin

write(‘n = ‘);

readln(n);

Fillchar(Dau,n, true);

63

End;

Procedure DFS (i:byte);

Begin

if i

for j:=1 to n do

if Dau[j] then

begin

A[i]:=j;

Dau[j]:=false;

DFS (j);

Dau[j]:=true;

end

else

begin

j:=1;

While not Dau[j] do

inc (j);

a[n]:=j;

begin

for j:=1 to n do

write (A[j]:4);

witeln;

end;

end;

End;

BEGIN {main}

Khoitao;

DFS (1);

Readln;

64

END.

10.3. Thu t toán AT – Tìm ki m c c ti u. ư ể ế ậ

Gi thi ả ế ữ ệ ư t d li u l u tr nh tìm ki m r ng. ữ ư ế ộ

cp là m ng chi phí c a đ th G. ủ ồ ị ả

Đ th G đ c l u tr b i ma tr n chi phí cp, trong đó cp[i,j] = Vocung ồ ị ượ ư ữ ở ậ

có nghĩa là không có cung (i,j).

Procedure ddcuctieu;

Const

Vocung = 70000;

Var

A: array[1..50,1..50] of byte;

Truoc: array [1..50] of byte;

Dau: array [1..50] of boolean;

cp: array[1..50, 1..50] of word;

n, i0, j0: byte;

Procedure Khoitao;

Var

i, j : byte;

f:text;

tenfile:string;

Begin

write(‘ten file’);

readln(tenfile);

assign(f, tenfile);

reset(f);

readln(f,n,i0,j0);

for i:=1 to n do

65

begin

for j:=1 to n do

read(f, cp[i,j]);

readln(f);

end;

close(f);

Fillchar (Dau,n,true);

End;

Procedure inkq(j: byte);

Begin

if Truoc[j] <> 0 then

inkq(truoc[j]);

write(j:4);

End;

Procedure Timkiem;

Begin

g[i0]:=0;

truoc[i0]:=0;

d:=1; c:=1;

Q[c]:=i0;

While d<=c do

begin

k:=d;

for l:=d+1 to c do

if g[q[l]]

k:=l;

tam:=q[d];

66

q[d]:=q[k];

q[k]:=tam;

m:=q[d];

inc(d);

if m=j0 then

inkq(j0)

else

for l:=1 to n do

if (cp[m,l]< vocung) then

if dau[l] then

begin

inc(c);

q[c]:=l;

dau[l]:=false;

g[l]:=g[m]+cp[m,n];

truoc[l]:=m;

end

else

if g[l]>g[m]+cp[m,n] then

begin

g[l]:= g[m]+cp[m,n];

truoc[l]:=m;

end;

end;

End;

Begin

Khoitao;

Timkiem;

67

End;

10.4. Tìm ki m leo đ i. ế ồ

Trong ch ng trình cài đ t này, chúng ta quy c n u đ nh đang xét là ươ ặ ướ ế ỉ

đ nh u, thì ỉ ả đ nh k v i u có kh năng đ n đích nh t là đ nh có kho ng ế ề ớ ấ ả ỉ ỉ

cách v i u l n nh t. ớ ớ ấ

Khi đó gi i thu t leo đ i có th trình bày l ả ể ậ ồ ạ i nh sau. ư

Leodoi(i,j): Th c hi n gi i thu t leo đ i t ự ệ ậ ồ ừ ỉ ỉ

- N u (i, j) đ nh i đ n đ nh j. ả ế ˛ E : d=c[i,j], push(i,j,k), exit ế

- N u (i,j) ˇ E: Tìm k sao cho c[i,k]=max {c[l,k]/ l˛ T[i] and ế

dau[i,l]}:

N u có (d=c[l,k]): dau[i,l]=false, push(i,j,d), Leodoi(k,j) ế

Ng i (d=0): pop(k,j,d), leodoi(k,j) c l ượ ạ

D li u đ c thi t k nh sau: ữ ệ ựơ ế ế ư

- M ng A l u danh sách các cung c a đ th G ủ ồ ị ư ả

- S là stack l u danh sách các đ nh s đ c xét và Top là đ nh c a S ẽ ượ ư ỉ ủ ỉ

- i0, j0 là đ nh xu t phát và đ nh k t thúc ế ấ ỉ ỉ

c l u trong file d ng Text có c u trúc nh sau: - Toàn b thông tin đ ộ ượ ư ư ấ ạ

ỗ dòng đ u l u m (s cung c a đ th ), i0, j0; m dòng tiép theo m i ồ ị ầ ư ủ ố

dòng ch a thông tin c a m tcung đ th G (đ nh đ u, đ nh cu i và đ ồ ị ủ ứ ầ ộ ố ỉ ỉ ộ

dài cung).

Procedure Leodoi;

Type

cung = record

dau, cuoi: byte;

kc: word;

end;

Var

68

S, A: array[1..50] of cung;

B: array[1..50] of boolean;

m,i0,j0, Top: byte;

Procedure Khoitao;

Var

f: text;

l: byte;

d: word;

tenfile: string;

begin

write(‘Nhap ten file: ‘);

readln(tenfile);

assign(f,tenfile);

reset(f);

readln(f,m,i0,j0);

for l:=1 to m do

with A[l] do

readln(f,dau, cuoi, kc);

fillchar(B, l, false);

Top:= 0;

end;

Procedure Pop( Var i,j: byte; var d: word);

{L y m t b n ghi (i,j,d) t S} ộ ả ấ ừ

begin

with S[Top] do

begin

i:= dau;

j:= cuoi;

69

d:= kc;

end;

dec(Top);

end;

Procedure TimKiem(i: byte; Var j: byte; var d: word);

{ Tìm cung (i,j) có c[i,j] l n nh t, n u có thì d = c[i,j] và đ nh d u cung ế ấ ấ ấ ớ ơ ư i,j

là true, ng i d = 0 } c l ượ ạ

Var

l,p: byte;

begin

d:=0;

for l:= 1 to m do

if (A[l].dau = i) and (A[l].kc > d) and not B[l] then

begin

j:= A[l].cuoi;

p:= l;

d:= A[l].kc;

end;

B[l]:= true;

end;

Function DenDich(i,j: byte; var d:word): boolean;

Var

l: byte;

begin

for l:= 1 to m do

if (A[l].dau = i) and (A[l].cuoi = j) then

begin

70

d:= A[l].kc;

DenDich:= true;

end

else

begin

DenDich:= false;

d:= 0;

end;

end;

Procedure Inkq(j:byte);

Var

d:word;

k: byte;

begin

d:=0;

for k:= 1 to Top do

begin

write(S[k].dau);

d:=d + S[k].kc;

end;

writeln(j);

writeln(‘ Chi phi: ‘,d);

end;

Procedure Duongdi(i,j: byte);

Var

k,d: byte;

Begin

71

if Dendich(i,j) then

begin

push(i,j,d);

inkq(j);

exit;

end;

Timkiem(i,k,d);

if d > 0 then

begin

push(i,j,d);

duongdi(k,j);

end

else

if Top > 0 then

begin

pop(i,j,d);

duongdi(i,j);

end

else

writeln(‘Khong co duong di’);

end;

Begin {leo doi}

Khoitao;

Duongdi(i0,j0);

72

end;

ij) bi u di n m t đ th vô h

11. Bài t p.ậ

ng G = (V,E) Bài t p 1. ậ Cho ma tr n k A= (a ậ ề ộ ồ ị ễ ể ướ

d i đây: ướ

¥ ¥ ¥ ¥ (cid:246) (cid:230)

0

4

(cid:247) (cid:231) ¥ ¥ (cid:247) (cid:231)

4

7

3

0

(cid:247) (cid:231) ¥

0

6

3

8

7

(cid:247) (cid:231)

¥ ¥ ¥ (cid:247) (cid:231)

3

0

5

(cid:247) (cid:231) ¥ ¥

8

2

5

0

(cid:247) (cid:231) (cid:247) (cid:231) ¥ ¥

6

0

2

3

ł Ł

trong đó aij= ¥ n u (i,j) ˇ E, ng i a c l đ nh i sang đ nh j. ế ượ ạ ij là chi phí đ đi t ể ừ ỉ ỉ

a. Hãy tìm đ ng đi t đ nh 1 sang đ nh 4 theo các ph ườ ừ ỉ ỉ ươ ế ng pháp tìm ki m

r ng và tìm ki m sâu. ộ ế

b. Tìm đ đ nh 1 sang đ nh 4 ườ ng đi ng n nh t t ắ ấ ừ ỉ ỉ

L i gi i ờ ả

4

3

2

1

6

7

6

2

8

3

5

5

3

4

73

c bi u di n b i ma tr n k A trên - V đ th G đ ẽ ồ ị ượ ậ ề ở ễ ở ể

- Ph ng pháp duy t r ng ươ ệ ộ

n t(n) close

2 1, 3, 6 2, 4, 5, 6 2, 3, 5 › open fl 1 2 3, 6 6, 4, 5 4, 5 1 1, 2 1, 2, 3 1, 2, 3, 6

1 2 3 6 4 ˛ dichfi d ngừ

fi Đ ng đi t ng pháp duy t r ng là: 1 2fi 3fi 4 ườ ừ ỉ đ nh 1 đ n đ nh 4 theo ph ỉ ế ươ ệ ộ

- Ph ng pháp duy t sâu ươ ệ

fl n t(n) close

2 1, 3, 6 2, 3, 5 3, 4, 6 open › 1 2 3, 6 3, 5 3, 4 1 1, 2 1, 2, 6 1, 2, 6, 5

1 2 6 5 4 ˛ dichfi d ngừ

fi Đ ng đi t đ nh 1 đ n đ nh 4 theo ph ng pháp duy t sâu là: 1 2fi 6fi 5fi 4 ườ ừ ỉ ế ỉ ươ ệ

- Ph ng pháp tìm ki m c c ti u ươ ự ể ế

n t(n) close

2 1, 3, 6 2, 3, 5 3, 4, 6 2, 4, 5, 6 open 10 24 311, 67 311, 59 311, 414 414 1 1, 2 1, 2, 6 1, 2, 6, 5 1, 2, 6, 5, 3

1 2 6 5 3 4˛ DICH fi d ngừ

74

fi V y đ 2fi 6fi 5fi 4 v i chi phí 14 ậ ườ ng đi ng n nh t: 1 ắ ấ ớ

g i ta s d ng hai bình ch a có dung tích l n l t là 3(lít) và Bài t p 2. N ậ ườ ử ụ ầ ượ ứ

4(lít) đ đong 2(lít) n c. gi ng n c l y t c đ vòi không h n ch ể ướ s l ả ử ượ ướ ượ ấ ừ ạ ế

và công đ l y n c t vòi cho đ y m t bình là 3, công đ đ n ể ấ ướ ừ ể ổ ướ ầ ộ ộ c trong m t

bình ra ngoài là 2 và đ n c t bình này sang bình khác thì t n công là 5. ổ ướ ừ ố

Hãy ch ra quá trình tìm ki m l i gi i b ng ph ng pháp tìm ki m theo ế ỉ ờ ả ằ ươ ế

chi u r ng và tìm ki m leo đ i. ề ộ ế ồ

L i gi i ờ ả

- Ph ng pháp tìm ki m theo chi u r ng ươ ề ộ ế

n t(n) close

› open fl (0,0)

(0,0) (0,4), (3,0) (0,4), (3,0) (0,0)

(0,4) (0,0), (3,4), (3,1) (3,0), (3,4), (0,0), (0,4)

(3,0) (0,0), (3,4), (0,3) (3,1) (0,0),(0,4),(3,0)

(3,4) (0,4), (3,0) (3,4), (3,1), (0,0),(0,4),(3,0), (3,4)

(3,1) (0,1), (3,0), (3,4), (0,3) (0,0),(0,4),(3,0), (3,4), (3,1)

(0,3) (0,4) (0,0), (0,4), (3,1), (0,3) (0,0),(0,4),(3,0), (3,4), (3,1), (0,3)

(3,3), (3,0) (0,3), (0,1)

(0,1) (0,0), (3,1), (0,4), (0,1), (3,3) (0,0),(0,4),(3,0), (3,4), (3,1), (0,3),

(1,0) (3,3), (1,0) (0,1)

(3,3) (0,3), (3,0), (2,4) (1,0), (2,4) (0,0),(0,4),(3,0), (3,4), (3,1), (0,3),

(0,1), (3,3)

(1,0) (0,0), (3,0), (1,4), (2,4), (1,4), (0,0),(0,4),(3,0), (3,4), (3,1), (0,3),

(0,1) (0,1), (3,3), (1,0)

(2,4)

Quá trình đong n ướ ệ ộ

75

c theo ph (0,0)fi ươ (3,0)fi ng pháp duy t r ng là: (3,3)fi (0,3)fi (2,4)

- Ph

thi t đ nh k v i đ nh đang xáe và có ươ ng tìm ki m leo đ i ế ồ (gi ả ế ỉ ề ớ ỉ

kho ng cách đên đ nh đó l n nh t là đ nh có tri n v ng đ n đích nh t) ể ế ả ấ ấ ớ ọ ỉ ỉ

((0,0), (2,4))ˇ E fi k= (3,0) c[(0,0), (3,0)]=5

((3,0), (2,4)) ˇ E fi k= (0,3) c[(3,0), (0,3)]=5

((0,3), (2,4)) ˇ e fi k= (3,3) c[(0,3), (3,3)]=5

((3,3), (2,4)) ˛ E fi c[(3,3), (2,4)]=5 d ngừ

c theo ph ng pháp leo đ i là: ươ ồ

Quá trình đong n (0,3)fi (3,0)fi ướ (3,3)fi (0,0)fi (2,4) v i chi phí 20 ớ

. Đ i d ng đ c xem nh là m t m t ph ng to đ trên đó có n Bài t p 3ậ ạ ươ ượ ạ ộ ư ặ ẳ ộ

1, y1), (x2, y2), …, (xn, yn). M t chi c ca nô

hòn đ o v i to đ l n l t là (x ạ ộ ầ ượ ả ớ ế ộ

1 mu n tu n tra đ n đ o d

xu t phát t đ o d ấ ừ ả ế ầ ả ố ứ 2. bình xăng c a ca nô ch ch a ủ ỉ

c m t quãng đ ng dài không quá m (km). Trên đ ng đi đ xăng đ đi đ ủ ể ượ ộ ườ ườ

2

ca nô có th ghé m t s đ o nào đó đ ti p thêm xăng, lúc này ca nô đ ộ ố ả ể ế ể ượ c

1 đ n đ o d

ti p thêm xăng đ y bình ch a. Hãy ch ra m t đ ng đi t đ o d ộ ườ ứ ế ầ ỉ ừ ả ế ả

sao cho s l n ghé đ o trung gian đ ti p thêm xăng là ít nh t. ể ế ố ầ ả ấ

H ng d n ướ ẫ

Ta xem hai đ o là k nhau n u kho ng cách gi a chúng không v t quá m ữ ề ế ả ả ượ

1 đ n đ o d

2 thông qua các đ o kả

(km). Bài toán c n tìm đ ng đi t đ o d ầ ườ ừ ả ế ả ề

nhau. Thu t toán tìm ki m theo chi u r ng cho phép tìm đ ng tìm ra đ ề ộ ế ậ ườ ườ ng

đi n i hai đ o qua ít c nh trung gian nh t (t c là ít đ o trung gian nh t). ấ ứ ả ạ ả ấ ố

D li u vào l u trong file d ng text, dòng đ u ch a s đ o n, dòng th hai ứ ố ả ữ ệ ư ứ ạ ầ

ch a kho ng cách l n nh t cano có th đi liên t c, n dònh ti p theo m i dòng ể ụ ứ ế ả ấ ớ ỗ

76

ch a hai giá tr t ng ng v i to đ c a m i đ o. ị ươ ứ ạ ộ ủ ỗ ả ứ ớ

. M t m ng l i giao thông gi a n thành ph (các thành ph đ Bài t p 4ậ ạ ộ ướ ố ượ c ữ ố

ij)n*n , trong đó:

đánh s t c cho b i ma tr n a=(a ố ừ 1 đ n n) đ ế ượ ậ ở

0, n u không có đ ng đi tr c ti p t ế ườ ự ế ừ i đ n j ế

aij= 1, n u có đ ng đi tr c ti p t i đ n j và là đ ng đi an toàn ế ườ ự ế ừ ế ườ

2, n u có đ ế ườ ng đi tr c ti p t ự ế ừ ặ i đ n j nh ng ph i qua m t ch ng ả ư ế ộ

ng nguy hi m ể

đ ườ ii=1, " Quy c: a i =1..n ướ

Cho tr c hai thành ph i ng đi t i ướ ố 0, i1. hãy tìm m t đ ộ ườ ừ 0 đ n iế 1 sao cho số

ch ng đ ặ ườ ng nguy hi m ph i đi qua là ít nh t. ả ể ấ

H ng d n: c h t ph i xác đ nh đ th bi u di n bài toán. đây d ẫ Tr ướ ướ ồ ị ể ễ ế ả ị Ở ễ

ng ng v i m t đ nh c a đ th , v n đ ch còn th y r ng m i thành ph t ỗ ấ ằ ố ươ ủ ồ ị ấ ộ ỉ ứ ề ớ ỉ

xác đ nh t p cung E căn c vào gi thi t c a bài toán. ứ ậ ị ả ế ủ

Bài t p 5ậ . Cho b ng vuông g m m*n ô. Trên m i ô ghi s 0 hay 1. ả ồ ỗ ố

a. T m t ô nào đó có th chuy n sang ô ch a s 1 có chung c nh v i nó. gi ứ ố ừ ộ ể ể ạ ớ ả

ô (h,c). Hãy tìm xem có cách di chuy n t ô này ra m t ô mép s đang ử ở ể ừ ộ ở

b ng hay không? Tìm cách chuy n qua ít ô nh t. ả ể ấ

b. M t mi n c a b ng là t p h p các ô có chung c nh và có cùng giá tr . hãy ề ủ ả ậ ạ ộ ợ ị

đ m xem b ng có bao nhiêu mi n. mi n l n nh t có bao nhiêu ô. ề ế ề ớ ả ấ

c. Cho phép thay đ i giá tr t t c các ô trong cùng m t mi n. Hãy xác đ nh ị ấ ả ề ổ ộ ị

mi n c n thay đ i đ s mi n gi m nhi u nh t. ổ ể ố ề ầ ề ề ả ấ

c m t mi n m i l n nh t. d. Hãy xác đ nh mi n c n thay đ i đ thu đ ề ầ ổ ể ị ượ ớ ớ ề ấ ộ

H ng d n ướ ẫ : M i ô t ỗ ươ ứ ng ng v i m t đ nh c a đ th . Hai đ nh k nhau khi ủ ồ ị ộ ỉ ề ớ ỉ

và ch khi hai ô t ỉ ươ ứ ề ủ ả ng ng có th chuy n sang nhau. M i mi n c a b ng ể ể ỗ

77

t ươ ứ ng ng v i m t mi n liên thông c a đ th . ủ ồ ị ề ớ ộ

ng trình đ i v i bài toán đong n Bài t p 6.ậ L p ch ậ ươ ố ớ ướ c, v i các s m, n, k là ố ớ

các s d c nh p t bàn phím khi th c hi n ch ng trình. ố ươ ng b t kỳ đ ấ ượ ậ ừ ự ệ ươ

H ng d n: ẫ S d ng thu t toán tìm ki m r ng s cho s l n thao tác là ít ử ụ ố ầ ướ ế ẽ ậ ộ

nh t.ấ

M t toà lâu đài đ c mô t b ng m t hình ch nh t có m*n ô. Bài t p 7. ậ ộ ượ ả ằ ữ ậ ộ

Gi a các ô có m t s b c t òng ngăn cách chia lâu đài thành các phòng. Nh ộ ố ứ ư ữ ư

ng ng v i t p các ô thông nhau. T i ô (i,j), cho bi t thông v y, m i phòng t ỗ ậ ươ ứ ớ ậ ạ ế

ij là m tộ

tin có t ng ngăn gi a ô này v i b n ô k v i nó không b i giá tr a ườ ớ ố ề ớ ữ ở ị

ng ng ô (i,j) có (1) ho c không có (0) t ng phía s nh phân 4 ch s t ố ữ ố ươ ị ứ ặ ườ ở

Tây, B c, Đông, Nam. Ví d a ng phía Tây ụ ij = 1001 có nghĩa là ô (i,j) có t ắ ườ ở

ng phía B c và Đông. Hãy vi t ch ng trình và Nam, nh ng không có t ư ườ ở ắ ế ươ

th c hi n các yêu c u sau: ự ệ ầ

a. Đ m s phòng c a toà lâu đài. ủ ế ố

b. Cho bi ế t phòng l n nh t có di n tích là bao nhiêu ô. ệ ấ ớ

t nên p há b c t ng ngăn hai phòng nào đ đ ế ứ ườ ể ượ ớ c m t phòng m i ộ

C. Cho bi

có di n tích l n nh t. ệ ấ ớ

ij có th nh n t

H ng d n 0 đ n 15. Vì ươ ẫ : Giá tr aị ể ậ ươ ứ ng ng v i s th p phân t ớ ố ậ ừ ế

v y ta l u ậ ư d li u trong file d ng text có c u trúc nh sau: dòng đ u ch a hai ấ ữ ệ ư ứ ạ ầ

s m,n. T dòng th hai đ n dòng th m+1, ch a các hàng c a ma tr n A = ứ ố ứ ủ ừ ứ ế ậ

(aij). K t qu đ a ra file d ng text có c u trúc nh sau: dòng đ u ch a s ả ư ứ ố ư ế ạ ấ ầ

ộ phòng, dònh hai ch a di n tíach phòng l n nh t và dong ba ch a hàng, c t, ứ ứ ệ ấ ớ

h ng c a b c t ướ ủ ứ ườ ng c n phá. ầ

Ch ng h n d li u vào là ạ ữ ệ ẳ

4 6

11 6 11 6 3 10 6

7 9 6 13 5 15 5

78

1 10 12 7 13 7 5

13 11 10 8 10 12 13

D li u ra s là: ữ ệ ẽ

5

9

4 1 Dong

M t sân ch i hình ch nh t g m m*n ô đ n v . Trên m i ô (i,j) có Bài t p 8. ậ ậ ồ ữ ộ ơ ơ ỗ ị

ij. Gi

đóng các tr bê tông chi u cao a thi c không th m qua đ c các ụ ề ả t n ế ướ ấ ượ

c nh gi a hai tr ữ ạ ụ bê tông k nhau. Sau m t tr n m a đ l n, hãy tính n ộ ậ ủ ớ ư ề ướ c

i trên sân. đ ng l ọ ạ

H ng d n ướ ẫ

Chia n c thành t ng t ng có chi u cao b ng 1. Tính th tích n ướ ừ ề ể ằ ầ ướ c

đ ng trên m i t ng theo thu t toán loang tìm thành ph n liên thông. ọ ỗ ầ ậ ầ

t a và b sao cho thoã mãn hai đi u ki n sau: Bài t p 9.ậ Tìm 2 ch s phân bi ữ ố ệ ệ ề

a. a2b chia h t cho 3 ế

b. a2b - ab=110

G ii bài toán đoán ch sau Bài t p 10. ậ ữ ả

DONALD CROSS

+

GERALD

+

ROADS

79

ROBERT DANGER

Cho s có hai ch s . N u vi Bài t p 11. ậ ữ ố ế ố ế t thêm hai ch s v bên ph i s ữ ố ề ả ố

đó thì đ c s m i l n h n s đã ho là 1986 đ n v . Hãy tìm s đã cho và hai ượ ố ớ ớ ơ ố ơ ố ị

ch s vi t thêm đó. ữ ố ế

Gi i bài toán đoán ch sau: Bài t p 12. ậ ả ữ

T

+ TH

THA

THAN

4321

Ch ươ ng trình tham kh o ả

Program cano_di_tuan; { Bài t p 3}ậ

uses crt;

type

dao = record

x,y: integer;

end;

var

n,d1,d2,so: byte;

m: word;

a: array[byte] of dao;

b: array[byte] of boolean;

tr: array[byte] of byte;

procedure nhap;

var

f: text;

80

s: string[20];

i: byte;

begin

clrscr;

write('ten file du lieu:');

readln(s);

assign(f,s);

reset(f);

readln(f,n);

readln(f,m);

for i:=1 to n do

with a[i] do readln(f,x,y);

close(f);

end;

procedure indulieu;

var

i: byte;

begin

writeln('so dao:',n);

writeln('gioi han khoang cach:',m);

for i:=1 to n do

with a[i] do writeln('toa do dao ',i,' : (',x,',',y,')');

end;

procedure khoitao;

var

i: byte;

begin

81

for i:=1 to n do

b[i]:= true;

end;

function kc(i,j: byte):real;

begin

kc:= sqrt(sqr(a[i].x-a[j].x)+sqr(a[i].y-a[j].y));

end;

procedure bfs(i: byte);

var

j,k,d,c: byte;

q: array[byte] of byte;

begin

d:=1;

c:=1;

q[1]:=i;

b[i]:= false;

while d<=c do

begin

j:= q[d];

d:=d+1;

for k:=1 to n do

if b[k] and (kc(k,j) <= m) then

begin

c:=c+1;

q[c]:=k;

b[k]:= false;

tr[k]:=j;

82

end;

end;

end;

procedure inketqua;

var

i:byte;

begin

write('duong di ghe dao it nhat nhu sau: ');

write(d1);

i:=d1;

so:=0;

while i<>d2 do

begin

write('-->',tr[i]);

so:=so+1;

i:=tr[i];

end;

writeln;

writeln('duong di tren ghe qua ',so-1,' dao');

end;

procedure timduongdi;

begin

write('dao xuat phat: ');

readln(d1);

write('dao ket thuc: ');

readln(d2);

bfs(d2);

83

if b[d2] then write('khong co duong di tu ',d1,' den ',d2)

else inketqua;

readln;

end;

BEGIN

nhap;

khoitao;

indulieu;

timduongdi;

END.

Program laudai; { Bài t p 7}ậ

uses crt;

type

size = 0..100;

var

m,n,so,p,hang,cot: size;

A:array[size,size] of 0..15;

ph: array[size,size] of word;

S: array[size] of word;

dt: word;

huong: string[4];

procedure nhap;

var

f: text;

i,j: size;

begin

84

clrscr;

assign(f,'input.pas');

reset(f);

read(f,m,n);

for i:=1 to m do

for j:=1 to n do read(f,A[i,j]);

close(f);

end;

procedure khoitao;

var

i,j: size;

begin

for i:=1 to m do

for j:=1 to n do

ph[i,j]:=0;

so:=0;

end;

procedure bfs(i,j: size);

var

qh,qc: array[size] of size;

d,c,k,l: size;

begin

ph[i,j]:= so;

d:=1;

c:=1;

qh[1]:=i;

85

qc[1]:=j;

while d<=c do

begin

k:= qh[d];

l:= qc[d];

d:=d+1;

if A[k,l]>=8 then

S[k,l]:=A[k,l]-8

else

if (k

begin

c:=c+1;

qh[c]:=k+1;

qc[c]:=1;

ph[k+1,l]:=so;

end;

if A[k,l]>=4 then

A[k,l]:=A[k,l]-4

else

if (l

begin

c:=c+1;

qh[c]:=k;

qc[c]:=l+1;

ph[k,l+1]:=so;

end;

if A[k,l]>=2 then

A[k,l]:= A[k,l]-2

else

86

if (k>1) and (ph[k-1,l] = 0) then

begin

c:=c+1;

qh[c]:=k-1;

qc[c]:=l;

ph[k-1,l]:=so;

end;

if A[k,l] >=1 then

A[k,l]:= A[k,l]-1

else

if (l>1) and (ph[k,l-1]=0) then

begin

c:=c+1;

qh[c]:=k;

qc[c]:=l-1;

ph[k,l-1]:=so;

end;

end;

end;

procedure demphong;

var

i,j: size;

begin

for i:=1 to m do

for j:=1 to n do

if ph[i,j] = 0 then

begin

so:= so+1;

87

bfs(i,j);

end;

end;

procedure smax;

var

i: word;

j,k: size;

begin

dt:=0;

for i:=1 to so do

begin

S[i]:=0;

for j:=1 to m do

for k:=1 to n do

if ph[j,k]=i then S[i]:= S[i]+1;

if S[i] > dt then dt:= S[i];

end;

end;

procedure phatuong;

{ Ch c n phá phía Đông ho c phía Nam, phía Tây c a ô (i,j) t ỉ ầ ủ ặ ươ ng ng là ứ

nh t ng ng phía Nam phía Đông c a ô (i,j-1), t ủ ươ ự , phía B c c a ô (i,j) t ắ ủ ươ ứ

c a ô (i-1,j)} ủ

var

i,j: size;

max,tg: word;

begin

max:=0;

88

for i:=1 to m do

for j:=1 to n do

begin

if i< m then

if ph[i,j] <> ph[i+1,j] then

begin

tg:= S[ph[i,j]] + S[ph[i+1,j]];

if tg >= max then

begin

hang :=i;

cot:=j;

huong:= 'nam';

max:= tg;

end;

end;

if j

if ph[i,j]<> ph[i,j+1] then

begin

tg:= S[ph[i,j]] + S[ph[i,j+1]];

if tg >= max then

begin

hang:=i;

cot:=j;

huong:= 'dong';

max:= tg;

end;

end;

end;

89

end;

procedure inkq;

var

i,j: size;

f: text;

begin

assign(f,'out.pas');

rewrite(f);

writeln(f,so);

writeln(f,dt);

writeln(f,hang,' ',cot,' ',huong);

close(f);

end;

BEGIN

nhap;

khoitao;

demphong;

smax;

phatuong;

inkq;

90

END.