Giáo trình Trí tuệ Nhân tạo - Đinh Mạnh Tường

Nguyễn Hoàng Cương

Môc lôc

PhÇn I : Gi¶i quyÕt vÊn ®Ò b»ng t×m kiÕm

1.1 Ch-¬ng I - C¸c chiÕn l-îc t×m kiÕm mï

1.1 BiÓu diÔn vÊn ®Ò trong kh«ng gian tr¹ng th¸i

1.2 C¸c chiÕn l-îc t×m kiÕm

1.3 C¸c chiÕn l-îc t×m kiÕm mï

1.3.1 T×m kiÕm theo bÒ réng

1.3.2 T×m kiÕm theo ®é s©u

1.3.3 C¸c tr¹ng th¸i lÆp

1.3.4 T×m kiÕm s©u lÆp

1.4 Quy vÊn ®Ò vÒ c¸c vÊn ®Ò con. T×m kiÕm trªn ®å thÞ vµ/hoÆc

1.4.1 Quy vÊn ®Ò vÒ c¸c vÊn ®Ò con

1.4.2 §å thÞ vµ/hoÆc

1.4.3 T×m kiÕm trªn ®å thÞ vµ/hoÆc

Ch-¬ng II - C¸c chiÕn l-îc t×m kiÕm kinh nghiÖm

2.1 Hµm ®¸nh gi¸ vµ t×m kiÕm kinh nghiÖm

2.2 T×m kiÕm tèt nhÊt - ®Çu tiªn

2.3 T×m kiÕm leo ®åi

2.4 T×m kiÕm beam

1.2 Ch-¬ng III - C¸c chiÕn l-îc t×m kiÕm tèi -u

3.1 T×m ®-êng ®i ng¾n nhÊt

3.1.1 ThuËt to¸n A*

3.1.2 ThuËt to¸n t×m kiÕm Nh¸nh-vµ-CËn

1.2.1 3.2 T×m ®èi t-îng tèt nhÊt

1.2.1.1 3.2.1 T×m kiÕm leo ®åi

3.2.2 T×m kiÕm gradient

3.2.3 T×m kiÕm m« pháng luyÖn kim

1.2.2 3.3 T×m kiÕm m« pháng sù tiÕn hãa. ThuËt to¸n di truyÒn

1.3 Ch-¬ng IV - T×m kiÕm cã ®èi thñ

4.1 C©y trß ch¬i vµ t×m kiÕm trªn c©y trß ch¬i

4.2 ChiÕn l-îc Minimax

4.3 Ph-¬ng ph¸p c¾t côt Alpha-Beta

PhÇn II: Tri thøc vµ lËp luËn

Đinh Mạnh Tường

Trang 1

Nguyễn Hoàng Cương

§inh M¹nh T-êng

Gi¸o tr×nh

TrÝ tuÖ Nh©n t¹o

Khoa CNTT - §¹i Häc Quèc Gia Hµ Néi

Đinh Mạnh Tường

Trang 2

Nguyễn Hoàng Cương

PhÇn I

Gi¶i quyÕt vÊn ®Ò b»ng t×m kiÕm

-----------------------------------

VÊn ®Ò t×m kiÕm, mét c¸ch tæng qu¸t, cã thÓ hiÓu lµ t×m mét ®èi t-îng tháa m·n

mét sè ®ßi hái nµo ®ã, trong mét tËp hîp réng lín c¸c ®èi t-îng. Chóng ta cã thÓ kÓ ra

rÊt nhiÒu vÊn ®Ò mµ viÖc gi¶i quyÕt nã ®-îc quy vÒ vÊn ®Ò t×m kiÕm.

C¸c trß ch¬i, ch¼ng h¹n cê vua, cê car« cã thÓ xem nh- vÊn ®Ò t×m kiÕm. Trong sè

rÊt nhiÒu n-íc ®i ®-îc phÐp thùc hiÖn, ta ph¶i t×m ra c¸c n-íc ®i dÉn tíi t×nh thÕ kÕt

cuéc mµ ta lµ ng-êi th¾ng.

Chøng minh ®Þnh lý còng cã thÓ xem nh- vÊn ®Ò t×m kiÕm. Cho mét tËp c¸c tiªn

®Ò vµ c¸c luËt suy diÔn, trong tr-êng hîp nµy môc tiªu cña ta lµ t×m ra mét chøng minh

(mét d·y c¸c luËt suy diÔn ®-îc ¸p dông) ®Ó ®-îc ®-a ®Õn c«ng thøc mµ ta cÇn chøng

minh.

Trong c¸c lÜnh vùc nghiªn cøu cña TrÝ TuÖ Nh©n T¹o, chóng ta th-êng xuyªn

ph¶i ®èi ®Çu víi vÊn ®Ò t×m kiÕm. §Æc biÖt trong lËp kÕ ho¹ch vµ häc m¸y, t×m kiÕm

®ãng vai trß quan träng.

Trong phÇn nµy chóng ta sÏ nghiªn cøu c¸c kü thuËt t×m kiÕm c¬ b¶n ®-îc ¸p

dông ®Ó gi¶i quyÕt c¸c vÊn ®Ò vµ ®-îc ¸p dông réng r·i trong c¸c lÜnh vùc nghiªn cøu

kh¸c cña TrÝ TuÖ Nh©n T¹o. Chóng ta lÇn l-ît nghiªn cøu c¸c kü thuËt sau:

•

C¸c kü thuËt t×m kiÕm mï, trong ®ã chóng ta kh«ng cã hiÓu biÕt g× vÒ c¸c ®èi

t-îng ®Ó h-íng dÉn t×m kiÕm mµ chØ ®¬n thuÇn lµ xem xÐt theo mét hÖ thèng nµo ®ã tÊt

c¶ c¸c ®èi t-îng ®Ó ph¸t hiÖn ra ®èi t-îng cÇn t×m.

•

C¸c kü thuËt t×m kiÕm kinh nghiÖm (t×m kiÕm heuristic) trong ®ã chóng ta dùa

vµo kinh nghiÖm vµ sù hiÓu biÕt cña chóng ta vÒ vÊn ®Ò cÇn gi¶i quyÕt ®Ó x©y dùng nªn

hµm ®¸nh gi¸ h-íng dÉn sù t×m kiÕm.

•

C¸c kü thuËt t×m kiÕm tèi -u.

C¸c ph-¬ng ph¸p t×m kiÕm cã ®èi thñ, tøc lµ c¸c chiÕn l-îc t×m kiÕm n-íc ®i

trong c¸c trß ch¬i hai ng-êi, ch¼ng h¹n cê vua, cê t-íng, cê car«.

Đinh Mạnh Tường

Trang 3

Nguyễn Hoàng Cương

Ch-¬ng I

C¸c chiÕn l-îc t×m kiÕm mï

---------------------------------

Trong ch-¬ng nµy, chóng t«i sÏ 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) vµ 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 còng sÏ ®-îc ®¸nh gi¸.

1.4 BiÓu diÔn vÊn ®Ò trong kh«ng gian tr¹ng th¸i

Mét khi chóng ta muèn 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. Kh«ng gian t×m kiÕm bao gåm tÊt c¶ c¸c ®èi t-îng

mµ ta cÇn quan t©m t×m kiÕm. Nã cã thÓ lµ kh«ng gian liªn tôc, ch¼ng h¹n kh«ng gian

c¸c vÐct¬ thùc n chiÒu; nã còng cã thÓ lµ kh«ng gian c¸c ®èi t-îng rêi r¹c.

Trong môc nµy ta sÏ xÐt viÖc biÓu diÔn mét vÊn ®Ò trong kh«ng gian tr¹ng th¸i sao

cho viÖc gi¶i quyÕt vÊn ®Ò ®-îc quy vÒ viÖc t×m kiÕm trong kh«ng gian tr¹ng th¸i.

Mét ph¹m vi réng lín c¸c vÊn ®Ò, ®Æc biÖt c¸c c©u ®è, c¸c trß ch¬i, cã thÓ m« t¶

b»ng c¸ch sö dông kh¸i niÖm tr¹ng th¸i vµ to¸n tö (phÐp biÕn ®æi tr¹ng th¸i). Ch¼ng h¹n,

mét kh¸ch du lÞch cã trong tay b¶n ®å m¹ng l-íi giao th«ng nèi c¸c thµnh phè trong mét

vïng l·nh thæ (h×nh 1.1), du kh¸ch ®ang ë thµnh phè A vµ anh ta muèn t×m ®-êng ®i tíi

th¨m thµnh phè B. Trong bµi to¸n nµy, c¸c thµnh phè cã trong c¸c b¶n ®å lµ c¸c tr¹ng

th¸i, thµnh phè A lµ tr¹ng th¸i ban ®Çu, B lµ tr¹ng th¸i kÕt thóc. Khi ®ang ë mét thµnh

phè, ch¼ng h¹n ë thµnh phè D anh ta cã thÓ ®i theo c¸c con ®-êng ®Ó nèi tíi c¸c thµnh

phè C, F vµ G. C¸c con ®-êng nèi c¸c thµnh phè sÏ ®-îc biÓu diÔn bëi c¸c to¸n tö. Mét

to¸n tö biÕn ®æi mét tr¹ng th¸i thµnh mét tr¹ng th¸i kh¸c. Ch¼ng h¹n, ë tr¹ng th¸i D sÏ

cã ba to¸n tö dÉn tr¹ng th¸i D tíi c¸c tr¹ng th¸i C, F vµ G. VÊn ®Ò cña du kh¸ch b©y giê

sÏ lµ t×m mét d·y to¸n tö ®Ó ®-a tr¹ng th¸i ban ®Çu A tíi tr¹ng th¸i kÕt thóc B.

Mét vÝ dô kh¸c, trong trß ch¬i cê vua, mçi c¸ch bè trÝ c¸c qu©n trªn bµn cê lµ mét

tr¹ng th¸i. Tr¹ng th¸i ban ®Çu lµ sù s¾p xÕp c¸c qu©n lóc b¾t ®Çu cuéc ch¬i. Mçi n-íc ®i

hîp lÖ lµ mét to¸n tö, nã biÕn ®æi mét c¶nh huèng trªn bµn cê thµnh mét c¶nh huèng

kh¸c.

Nh- vËy muèn biÓu diÔn mét vÊn ®Ò trong kh«ng gian tr¹ng th¸i, ta cÇn x¸c ®Þnh

c¸c yÕu tè sau:

•

Tr¹ng th¸i ban ®Çu.

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Ëp hîp tÊt c¶ c¸c tr¹ng th¸i cã thÓ ®¹t tíi tõ tr¹ng th¸i ban ®Çu b»ng c¸ch ¸p dông

mét d·y to¸n tö, lËp thµnh kh«ng gian tr¹ng th¸i cña vÊn ®Ò.

Ta sÏ ký hiÖu kh«ng gian tr¹ng th¸i lµ U, tr¹ng th¸i ban ®Çu lµ u₀(u₀ U). Mçi

to¸n tö R cã thÓ xem nh- mét ¸nh x¹ R: UU. Nãi chung R lµ mét ¸nh x¹ kh«ng x¸c

®Þnh kh¾p n¬i trªn U.

Đinh Mạnh Tường

Trang 4

Nguyễn Hoàng Cương

•

Mét tËp hîp 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. Trong vÊn ®Ò cña du kh¸ch trªn, chØ cã mét tr¹ng th¸i ®Ých, ®ã lµ thµnh phè B.

Nh-ng trong nhiÒu vÊn ®Ò (ch¼ng h¹n c¸c lo¹i cê) cã thÓ cã nhiÒu tr¹ng th¸i ®Ých vµ ta

kh«ng thÓ x¸c ®Þnh tr-íc ®-îc c¸c tr¹ng th¸i ®Ých. Nãi chung trong phÇn lín c¸c vÊn ®Ò

hay, ta chØ cã thÓ m« t¶ c¸c tr¹ng th¸i ®Ých lµ c¸c tr¹ng th¸i tháa m·n mét sè ®iÒu kiÖn

nµo ®ã.

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. (Mét ®-êng ®i trong kh«ng gian tr¹ng th¸i lµ mét d·y to¸n tö dÉn mét tr¹ng

th¸i tíi mét tr¹ng th¸i kh¸c).

Chóng ta cã thÓ biÓu diÔn kh«ng gian tr¹ng th¸i b»ng ®å thÞ ®Þnh h-íng, trong ®ã

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.

Sau ®©y chóng ta sÏ xÐt mét sè vÝ dô vÒ c¸c kh«ng gian tr¹ng th¸i ®-îc x©y dùng

cho mét sè vÊn ®Ò.

VÝ dô 1: Bµi to¸n 8 sè. Chóng ta cã b¶ng 3x3 « vµ t¸m qu©n mang sè hiÖu tõ 1 ®Õn

8 ®-îc xÕp vµo t¸m «, cßn l¹i mét « trèng, ch¼ng h¹n nh- trong h×nh 2 bªn tr¸i. Trong

trß ch¬i nµy, b¹n cã thÓ chuyÓn dÞch c¸c qu©n ë c¹ch « trèng tíi « trèng ®ã. VÊn ®Ò cña

b¹n lµ t×m ra mét d·y c¸c chuyÓn dÞch ®Ó biÕn ®æi c¶nh huèng ban ®Çu (h×nh 1.2 bªn

tr¸i) thµnh mét c¶nh huèng x¸c ®Þnh nµo ®ã, ch¼ng h¹n c¶nh huèng trong h×nh 1.2 bªn

ph¶i.

Đinh Mạnh Tường

Trang 5

Nguyễn Hoàng Cương

Trong bµi to¸n nµy, tr¹ng th¸i ban ®Çu lµ c¶nh huèng ë bªn tr¸i h×nh 1.2, cßn tr¹ng

th¸i kÕt thóc ë bªn ph¶i h×nh 1.2. T-¬ng øng víi c¸c quy t¾c chuyÓn dÞch c¸c qu©n, ta cã

bèn to¸n tö: up (®Èy qu©n lªn trªn), down (®Èy qu©n xuèng d-íi), left (®Èy qu©n sang

tr¸i), right (®Èy qu©n sang ph¶i). Râ rµng lµ, c¸c to¸n tö nµy chØ lµ c¸c to¸n tö bé phËn;

ch¼ng h¹n, tõ tr¹ng th¸i ban ®Çu (h×nh 1.2 bªn tr¸i), ta chØ cã thÓ ¸p dông c¸c to¸n tö

down, left, right.

Trong c¸c vÝ dô trªn viÖc t×m ra mét biÓu diÔn thÝch hîp ®Ó m« t¶ c¸c tr¹ng th¸i

cña vÊn ®Ò lµ kh¸ dÔ dµng vµ tù nhiªn. Song trong nhiÒu vÊn ®Ò viÖc t×m hiÓu ®-îc biÓu

diÔn thÝch hîp cho c¸c tr¹ng th¸i cña vÊn ®Ò lµ hoµn toµn kh«ng ®¬n gi¶n. ViÖc t×m ra

d¹ng biÓu diÔn tèt cho c¸c tr¹ng th¸i ®ãng vai trß hÕt søc quan träng trong qu¸ tr×nh gi¶i

quyÕt mét vÊn ®Ò. Cã thÓ nãi r»ng, nÕu ta t×m ®-îc d¹ng biÓu diÔn tèt cho c¸c tr¹ng th¸i

cña vÊn ®Ò, th× vÊn ®Ò hÇu nh- ®· ®-îc gi¶i quyÕt.

VÝ dô 2: VÊn ®Ò triÖu phó vµ kÎ c-íp. Cã ba nhµ triÖu phó vµ ba tªn c-íp ë bªn bê

t¶ ng¹n mét con s«ng, cïng mét chiÕc thuyÒn chë ®-îc mét hoÆc hai ng-êi. H·y t×m

c¸ch ®-a mäi ng-êi qua s«ng sao cho kh«ng ®Ó l¹i ë bªn bê s«ng kÎ c-íp nhiÒu h¬n

triÖu phó. §-¬ng nhiªn trong bµi to¸n nµy, c¸c to¸n tö t-¬ng øng víi c¸c hµnh ®éng chë

1 hoÆc 2 ng-êi qua s«ng. Nh-ng ë ®©y ta cÇn l-u ý r»ng, khi hµnh ®éng xÈy ra (lóc

thuyÒn ®ang b¬i qua s«ng) th× ë bªn bê s«ng thuyÒn võa dêi chç, sè kÎ c-íp kh«ng ®-îc

nhiÒu h¬n sè triÖu phó. TiÕp theo ta cÇn quyÕt ®Þnh c¸i g× lµ tr¹ng th¸i cña vÊn ®Ò. ë ®©y

ta kh«ng cÇn ph©n biÖt c¸c nhµ triÖu phó vµ c¸c tªn c-íp, mµ chØ sè l-îng cña hä ë bªn

bê s«ng lµ quan träng. §Ó biÓu diÔn c¸c tr¹ng th¸i, ta sö dông bé ba (a, b, k), trong ®ã a

lµ sè triÖu phó, b lµ sè kÎ c-íp ë bªn bê t¶ ng¹n vµo c¸c thêi ®iÓm mµ thuyÒn ë bê nµy

hoÆc bê kia, k = 1 nÕu thuyÒn ë bê t¶ ng¹n vµ k = 0 nÕu thuyÒn ë bê h÷u ng¹n. Nh- vËy,

kh«ng gian tr¹ng th¸i cho bµi to¸n triÖu phó vµ kÎ c-íp ®-îc x¸c ®Þnh nh- sau:

•

Tr¹ng th¸i ban ®Çu lµ (3, 3, 1).

C¸c to¸n tö. Cã n¨m to¸n tö t-¬ng øng víi hµnh ®éng thuyÒn chë qua s«ng 1 triÖu

phó, hoÆc 1 kÎ c-íp, hoÆc 2 triÖu phó, hoÆc 2 kÎ c-íp, hoÆc 1 triÖu phó vµ 1 kÎ c-íp.

•

Tr¹ng th¸i kÕt thóc lµ (0, 0, 0).

1.5 C¸c chiÕn l-îc t×m kiÕm

Nh- ta ®· thÊy trong môc 1.1, ®Ó gi¶i quyÕt mét vÊn ®Ò b»ng t×m kiÕm trong

kh«ng gian tr¹ng th¸i, ®Çu tiªn ta cÇn t×m d¹ng thÝch hîp m« t¶ c¸c tr¹ng th¸i c¶u vÊn

®Ò. Sau ®ã cÇn 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 ®ã).

Gi¶ sö u lµ mét tr¹ng th¸i nµo ®ã vµ R lµ mét to¸n tö biÕn ®æi u thµnh v. Ta sÏ gäi

v lµ tr¹ng th¸i kÒ u, hoÆc v ®-îc sinh ra tõ tr¹ng th¸i u bëi to¸n tö R. Qu¸ tr×nh ¸p dông

c¸c to¸n tö ®Ó sinh ra c¸c tr¹ng th¸i kÒ u ®-îc gäi lµ ph¸t triÓn tr¹ng th¸i u. Ch¼ng h¹n,

trong bµi to¸n to¸n sè, ph¸t triÓn tr¹ng th¸i ban ®Çu (h×nh 2 bªn tr¸i), ta nhËn ®-îc ba

tr¹ng th¸i kÒ (h×nh 1.3).

Đinh Mạnh Tường

Trang 6

Nguyễn Hoàng Cương

Khi chóng ta biÓu diÔn mét vÊn ®Ò cÇn gi¶i quyÕt th«ng qua c¸c tr¹ng th¸i vµ c¸c

to¸n tö th× viÖc t×m lêi gi¶i cña vÊn ®Ò ®-îc quy vÒ viÖc t×m ®-êng ®i tõ tr¹ng th¸i ban

®Çu tíi mét tr¹ng th¸i kÕt thóc nµo ®ã.

Cã thÓ ph©n c¸c chiÕn l-îc t×m kiÕm thµnh hai lo¹i:

•

C¸c chiÕn l-îc t×m kiÕm mï. Trong c¸c 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Ø ph¸t triÓn c¸c tr¹ng th¸i ban ®Çu cho tíi

khi gÆp mét tr¹ng th¸i ®Ých nµo ®ã. Cã hai kü thuËt t×m kiÕm mï, ®ã lµ t×m kiÕm theo bÒ

réng vµ t×m kiÕm theo ®é s©u.

T- t-ëng cña t×m kiÕm theo bÒ réng lµ c¸c tr¹ng th¸i ®-îc ph¸t triÓn theo thø tù

mµ chóng ®-îc sinh ra, tøc lµ tr¹ng th¸i nµo ®-îc sinh ra tr-íc sÏ ®-îc ph¸t triÓn tr-íc.

Trong nhiÒu vÊn ®Ò, dï chóng ta ph¸t triÓn c¸c tr¹ng th¸i theo hÖ thèng nµo (theo

bÒ réng hoÆc theo ®é s©u) th× sè l-îng c¸c tr¹ng th¸i ®-îc sinh ra tr-íc khi ta gÆp tr¹ng

th¸i ®Ých th-êng lµ cùc kú lín. Do ®ã c¸c thuËt to¸n t×m kiÕm mï kÐm hiÖu qu¶, ®ßi hái

rÊt nhiÒu kh«ng gian vµ thêi gian. Trong thùc tÕ, nhiÒu vÊn ®Ò kh«ng thÓ gi¶i quyÕt ®-îc

b»ng t×m kiÕm mï.

•

T×m kiÕm kinh nghiÖm (t×m kiÕm heuristic). Trong rÊt nhiÒu vÊn ®Ò, chóng ta cã

thÓ dùa vµo sù hiÓu biÕt cña chóng 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ù ®¸nh gi¸ c¸c tr¹ng th¸i ®Ó h-íng dÉn sù t×m kiÕm: trong

qu¸ tr×nh ph¸t triÓn c¸c tr¹ng th¸i, ta sÏ chän trong sè c¸c tr¹ng th¸i chê ph¸t triÓn, tr¹ng

th¸i ®-îc ®¸nh gi¸ lµ tèt nhÊt ®Ó ph¸t triÓn. Do ®ã tèc ®é t×m kiÕm sÏ nhanh h¬n. C¸c

ph-¬ng ph¸p t×m kiÕm dùa vµo sù ®¸nh gi¸ c¸c tr¹ng th¸i ®Ó h-íng dÉn sù t×m kiÕm gäi

chung lµ c¸c ph-¬ng ph¸p t×m kiÕm kinh nghiÖm.

Nh- vËy chiÕn l-îc t×m kiÕm ®-îc x¸c ®Þnh bëi chiÕn l-îc chän tr¹ng th¸i ®Ó ph¸t

triÓn ë mçi b-íc. Trong t×m kiÕm mï, ta chän tr¹ng th¸i ®Ó ph¸t triÓn theo thø tù mµ

®óng ®-îc sinh ra; cßn trong 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

Đinh Mạnh Tường

Trang 7

Nguyễn Hoàng Cương

Chóng ta cã thÓ nghÜ ®Õn qu¸ tr×nh t×m kiÕm nh- qu¸ tr×nh x©y dùng c©y t×m

kiÕm. 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. H×nh 1.4a lµ ®å thÞ

biÓu diÔn mét kh«ng gian tr¹ng th¸i víi tr¹ng th¸i ban ®Çu lµ A, h×nh 1.4b lµ c©y t×m

kiÕm t-¬ng øng víi kh«ng gian tr¹ng th¸i ®ã.

Mçi chiÕn l-îc t×m kiÕm trong kh«ng gian tr¹ng th¸i t-¬ng øng víi mét ph-¬ng

ph¸p x©y dùng c©y t×m kiÕm. Qu¸ tr×nh x©y dùng c©y b¾t ®Çu tõ c©y chØ cã mét ®Ønh lµ

tr¹ng th¸i ban ®Çu. Gi¶ sö tíi mét b-íc nµo ®ã trong chiÕn l-îc t×m kiÕm, ta ®· x©y

dùng ®-îc mét c©y nµo ®ã, c¸c l¸ cña c©y t-¬ng øng víi c¸c tr¹ng th¸i ch-a ®-îc ph¸t

triÓn. B-íc tiÕp theo phô thuéc vµo chiÕn l-îc t×m kiÕm mµ mét ®Ønh nµo ®ã trong c¸c l¸

®-îc chän ®Ó ph¸t triÓn. Khi ph¸t triÓn ®Ønh ®ã, c©y t×m kiÕm ®-îc më réng b»ng c¸ch

thªm vµo c¸c ®Ønh con cña ®Ønh ®ã. Kü thuËt t×m kiÕm theo bÒ réng (theo ®é s©u) t-¬ng

øng víi ph-¬ng ph¸p x©y dùng c©y t×m kiÕm theo bÒ réng (theo ®é s©u).

1.6 C¸c chiÕn l-îc t×m kiÕm mï

Trong môc nµy chóng ta sÏ tr×nh bµy hai chiÕn l-îc t×m kiÕm mï: t×m kiÕm theo

bÒ réng vµ t×m kiÕm theo ®é s©u. Trong t×m kiÕm theo bÒ réng, 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.

Cßn trong t×m kiÕm theo ®é s©u, 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.

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.

1.6.1 T×m kiÕm theo bÒ réng

ThuËt to¸n t×m kiÕm theo bÒ réng ®-îc m« t¶ bëi thñ tôc sau:

procedure

begin

Breadth_First_Search;

Đinh Mạnh Tường

Trang 8

Nguyễn Hoàng Cương

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 t×m kiÕm 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 t×m kiÕm thµnh c«ng; stop};

2.4 for mçi tr¹ng th¸i v kÒ u do {

§Æt v vµo cuèi danh s¸ch L;

father(v) <- u}

end;

Chóng ta cã mét sè nhËn xÐt sau ®©y vÒ thuËt to¸n t×m kiÕm theo bÒ réng:

•

Trong t×m kiÕm theo bÒ réng, 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 xö lý nh- hµng ®îi. Trong b-íc 2.3, ta cÇn kiÓm tra xem

u cã lµ tr¹ng th¸i kÕt thóc hay kh«ng. Nãi chung c¸c tr¹ng th¸i kÕt thóc ®-îc x¸c ®Þnh

bëi mét sè ®iÒu kiÖn nµo ®ã, khi ®ã ta cÇn kiÓm tra xem u cã tháa m·n c¸c ®iÒu kiÖn ®ã

hay kh«ng.

•

NÕu bµi to¸n cã nghiÖm (tån t¹i ®-êng ®i tõ tr¹ng th¸i ban ®Çu tíi tr¹ng th¸i

®Ých), th× thuËt to¸n t×m kiÕm theo bÒ réng sÏ t×m ra nghiÖm, ®ång thêi ®-êng ®i t×m

®-îc sÏ lµ ng¾n nhÊt. Trong tr-êng hîp bµi to¸n v« nghiÖm vµ kh«ng gian tr¹ng th¸i h÷u

h¹n, thuËt to¸n sÏ dõng vµ cho th«ng b¸o v« nghiÖm.

§¸nh gi¸ t×m kiÕm theo bÒ réng

B©y giê ta ®¸nh gi¸ thêi gian vµ bé nhí mµ t×m kiÕm theo bÒ réng ®ßi hái. 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. 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 + b²+ ... + b^d-1+ k

Trong ®ã k cã thÓ lµ 1, 2, ..., b^d. Do ®ã sè lín nhÊt c¸c ®Ønh cÇn xem xÐt lµ:

1 + b + b²+ ... + b^d

Nh- vËy, ®é phøc t¹p thêi gian cña thuËt to¸n t×m kiÕm theo bÒ réng lµ O(b^d). §é

phøc t¹p kh«ng gian còng lµ O(b^d), bëi v× ta cÇn l-u vµo danh s¸ch L tÊt c¶ c¸c ®Ønh cña

c©y t×m kiÕm ë møc d, sè c¸c ®Ønh nµy lµ b^d.

§Ó thÊy râ t×m kiÕm theo bÒ réng ®ßi hái thêi gian vµ kh«ng gian lín tíi møc nµo,

ta xÐt tr-êng hîp nh©n tè nh¸nh b = 10 vµ ®é s©u d thay ®æi. Gi¶ sö ®Ó ph¸t hiÖn vµ kiÓm

tra 1000 tr¹ng th¸i cÇn 1 gi©y, vµ l-u gi÷ 1 tr¹ng th¸i cÇn 100 bytes. Khi ®ã thêi gian vµ

kh«ng gian mµ thuËt to¸n ®ßi hái ®-îc cho trong b¶ng sau:

Đinh Mạnh Tường

Trang 9

Nguyễn Hoàng Cương

§é s©u d

Thêi gian

11 gi©y

Kh«ng gian

1 megabyte

4

6

18 gi©y

31 giê

111 megabytes

11 gigabytes

1 terabyte

8

10

12

14

128 ngµy

35 n¨m

111 terabytes

11.111 terabytes

3500 n¨m

1.6.2 T×m kiÕm theo ®é s©u

Nh- ta ®· biÕt, t- t-ëng cña chiÕn l-îc t×m kiÕm theo ®é s©u lµ, 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. Cô thÓ lµ trong b-íc 2.4 cña

thuËt to¸n t×m kiÕm theo bÒ réng, ta cÇn söa l¹i lµ “§Æt v vµo ®Çu danh s¸ch L”.

Sau ®©y chóng ta sÏ ®-a ra c¸c nhËn xÐt so s¸nh hai chiÕn l-îc t×m kiÕm mï:

•

ThuËt to¸n t×m kiÕm theo bÒ réng lu«n lu«n t×m ra nghiÖm nÕu bµi to¸n cã

nghiÖm. Song 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 ®é

s©u còng t×m ra nghiÖm! NÕu bµi to¸n cã nghiÖm vµ kh«ng gian tr¹ng th¸i h÷u h¹n, th×

thuËt to¸n t×m kiÕm theo ®é s©u sÏ t×m ra nghiÖm. Tuy nhiªn, trong tr-êng hîp kh«ng

gian tr¹ng th¸i v« h¹n, th× cã thÓ nã kh«ng t×m ra nghiÖm, lý do lµ ta lu«n lu«n ®i xuèng

theo ®é s©u, nÕu ta ®i theo mét 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. Do ®ã ng-êi ta khuyªn r»ng, kh«ng nªn ¸p dông t×m kiÕm

theo dé s©u cho c¸c bµi to¸n cã c©y t×m kiÕm chøa c¸c nh¸nh v« h¹n.

•

§é phøc t¹p cña thuËt to¸n t×m kiÕm theo ®é s©u.

Gi¶ sö r»ng, 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µ b vµ cã chiÒu cao lµ d. Cã thÓ xÈy ra, nghiÖm lµ ®Ønh ngoµi cïng bªn ph¶i trªn

møc d cña c©y t×m kiÕm, do ®ã ®é phøc t¹p thêi gian cña t×m kiÕm theo ®é s©u trong

tr-êng hîp xÊu nhÊt lµ O(b^d), tøc lµ còng nh- t×m kiÕm theo bÒ réng. Tuy nhiªn, trªn

thùc tÕ ®èi víi nhiÒu bµi to¸n, t×m kiÕm theo ®é s©u thùc sù nhanh h¬n t×m kiÕm theo bÒ

réng. Lý do lµ t×m kiÕm theo bÒ réng ph¶i xem xÐt toµn bé c©y t×m kiÕm tíi møc d-1, råi

míi xem xÐt c¸c ®Ønh ë møc d. Cßn trong t×m kiÕm theo ®é s©u, cã thÓ ta chØ cÇn xem

xÐt mét bé phËn nhá cña c©y t×m kiÕm th× ®· t×m ra nghiÖm.

§Ó ®¸nh gi¸ ®é phøc t¹p kh«ng gian cña t×m kiÕm theo ®é s©u ta cã nhËn xÐt r»ng,

khi ta ph¸t triÓn mét ®Ønh u trªn c©y t×m kiÕm theo ®é s©u, ta chØ cÇn l-u c¸c ®Ønh ch-a

®-îc ph¸t triÓn mµ chóng lµ c¸c ®Ønh con cña c¸c ®Ønh n»m trªn ®-êng ®i tõ gèc tíi ®Ønh

u. Nh- vËy ®èi víi c©y t×m kiÕm cã nh©n tè nh¸nh b vµ ®é s©u lín nhÊt lµ d, ta chØ cÇn

l-u Ýt h¬n db ®Ønh. Do ®ã ®é phøc t¹p kh«ng gian cña t×m kiÕm theo ®é s©u lµ O(db),

trong khi ®ã t×m kiÕm theo bÒ réng ®ßi hái kh«ng gian nhí O(b^d)!

Đinh Mạnh Tường

Trang 10

Nguyễn Hoàng Cương

1.6.3 C¸c tr¹ng th¸i lÆp

Nh- ta thÊy trong môc 1.2, 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. Ch¼ng h¹n, trong c©y t×m kiÕm

h×nh 4b, 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. NÕu ®å thÞ cã chu tr×nh th× c©y t×m kiÕm sÏ chøa c¸c nh¸nh víi mét sè ®Ønh lËp

l¹i v« h¹n lÇn. Trong c¸c thuËt to¸n t×m kiÕm sÏ l·ng phÝ rÊt nhiÒu thêi gian ®Ó ph¸t triÓn

l¹i c¸c tr¹ng th¸i mµ ta ®· gÆp vµ ®· ph¸t triÓn. 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. Chóng ta cã thÓ ¸p dông mét trong

c¸c gi¶i ph¸p sau ®©y:

1. Khi ph¸t triÓn ®Ønh u, kh«ng sinh ra c¸c ®Ønh trïng víi cha cña u.

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

3. Kh«ng sinh ra c¸c ®Ønh mµ nã ®· ®-îc sinh ra, tøc lµ chØ sinh ra c¸c ®Ønh míi.

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. Chóng ta cã thÓ cµi ®Æt tËp Q bëi b¶ng b¨m (xem [ ]).

1.6.4 T×m kiÕm s©u lÆp

Nh- chóng ta ®· nhËn xÐt, 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

procedure Depth_Limited_Search(d);

begin

1. Khëi t¹o danh s¸ch L chØ chøa tr¹ng th¸i ban ®Çu u₀;

depth(u₀) 0;

2. loop do

2.1 if L rçng then

{th«ng b¸o thÊt b¹i; stop};

Đinh Mạnh Tường

Trang 11

Nguyễn Hoàng Cương

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;

procedure Depth_Deepening_Search;

begin

for d  0 to max do

{Depth_Limited_Search(d);

if thµnh c«ng then exit}

end;

Kü thuËt t×m kiÕm s©u lÆp kÕt hîp ®-îc c¸c -u ®iÓm cña t×m kiÕm theo bÒ réng vµ

t×m kiÕm theo ®é s©u. Chóng ta cã mét sè nhËn xÐt sau:

•

Còng nh- t×m kiÕm theo bÒ réng, t×m kiÕm s©u lÆp lu«n lu«n t×m ra nghiÖm (nÕu

bµi to¸n cã nghiÖm), miÔn lµ ta chän ®é s©u m· ®ñ lín.

•

T×m kiÕm s©u lÆp chØ cÇn kh«ng gian nhí nh- t×m kiÕm theo ®é s©u.

Trong t×m kiÕm s©u lÆp, ta ph¶i ph¸t triÓn lÆp l¹i nhiÒu lÇn cïng mét tr¹ng th¸i.

§iÒu ®ã lµm cho ta cã c¶m gi¸c r»ng, t×m kiÕm s©u lÆp l·ng phÝ nhiÒu thêi gian. Thùc ra

thêi gian tiªu tèn cho ph¸t triÓn lÆp l¹i c¸c tr¹ng th¸i lµ kh«ng ®¸ng kÓ so víi thêi gian

t×m kiÕm theo bÒ réng. ThËt vËy, mçi lÇn gäi thñ tôc t×m kiÕm s©u h¹n chÕ tíi møc d,

nÕu c©y t×m kiÕm cã nh©n tè nh¸nh lµ b, th× sè ®Ønh cÇn ph¸t triÓn lµ:

1 + b + b²+ ... + b^d

NÕu nghiÖm ë ®é s©u d, th× trong t×m kiÕm s©u lÆp, ta ph¶i gäi thñ tôc t×m kiÕm

s©u h¹n chÕ víi ®é s©u lÇn l-ît lµ 0, 1, 2, ..., d. Do ®ã c¸c ®Ønh ë møc 1 ph¶i ph¸t triÓn

lÆp d lÇn, c¸c ®Ønh ë møc 2 lÆp d-1 lÇn, ..., c¸c ®Ønh ë møc d lÆp 1 lÇn. Nh- vËy tæng sè

®Ønh cÇn ph¸t triÓn trong t×m kiÕm s©u lÆp lµ:

(d+1)1 + db + (d-1)b²+ ... + 2b^d-1+ 1b^d

Do ®ã thêi gian t×m kiÕm s©u lÆp lµ O(b^d).

Tãm l¹i, t×m kiÕm s©u lÆp cã ®é phøc t¹p thêi gian lµ O(b^d) (nh- t×m kiÕm theo bÒ

réng), 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

Đinh Mạnh Tường

Trang 12

Nguyễn Hoàng Cương

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.

1.7 Quy vÊn ®Ò vÒ c¸c vÊn ®Ò con. T×m kiÕm trªn ®å thÞ vµ/hoÆc.

1.7.1 Quy vÊn ®Ò vÒ c¸c vÊn ®Ò con:

Trong môc 1.1, 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  (xe^x+ x³) 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  (xe^x+ x³) dx, ¸p dông quy

t¾c tÝch ph©n cña tæng ta ®-a vÒ hai tÝch ph©n  xe^xdx vµ  x³dx. ¸p dông quy t¾c tÝch

ph©n tõng phÇn ta ®-a tÝch ph©n  xe^xdx vÒ tÝch ph©n  e^xdx. Qu¸ tr×nh trªn cã thÓ biÓu

diÔn bëi ®å thÞ trong h×nh 1.5.

C¸c tÝch ph©n  e^xdx vµ  x³dx 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:

Đinh Mạnh Tường

Trang 13

Nguyễn Hoàng Cương

 (f₁+ f₂) dx   f₁dx,  f₂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).

Mét ®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 1.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

diÔn kh¸c dùa trªn viÖc quy vÊn ®Ò vÒ c¸c vÊn ®Ò con. Gi¶ sö ta cã b¶n ®å giao th«ng

trong mét vïng l·nh thæ (xem h×nh 1.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.

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.

Đinh Mạnh Tường

Trang 14

Nguyễn Hoàng Cương

Qu¸ tr×nh rót gän vÊn ®Ò nh- trªn cã thÓ biÓu diÔn d-íi d¹ng ®å thÞ (®å thÞ

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.

1.7.2 §å thÞ vµ/hoÆc

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ù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 a₁, ®Ø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 1.8.

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ö quy gåm:

Đinh Mạnh Tường

Trang 15

Nguyễn Hoàng Cương

R₁: a d, e, f

R₂: a d, k

R₃: a g, h

R₄: d b, c

R₅: f i

R₆: f c, j

R₇: k e, l

R₈: 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, j, l}.

Kh«ng gian tr¹ng th¸i trªn cã thÓ biÓu diÔn bëi ®å thÞ vµ/hoÆc trong h×nh 1.9.

Trong ®å thÞ ®ã, c¸c ®Ønh, ch¼ng h¹n a₁, a₂, a₃®-îc gäi lµ ®Ønh vµ, c¸c ®Ønh ch¼ng h¹n a,

f, k ®-îc gäi lµ ®Ønh hoÆc. Lý do lµ, ®Ønh a₁biÓu diÔn tËp c¸c bµi to¸n {d, e, f} vµ a₁

®-î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ö R₁, R₂,

R₃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 a₁=

{d, e, f}, hoÆc a₂= {d, k}, hoÆc a₃= {g, h} ®-îc gi¶i quyÕt.

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 1.9 cã thÓ rót gän thµnh ®å thÞ trong h×nh 1.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ö R₁, cßn d, k lµ c¸c ®Ønh kÒ a theo

to¸n tö R₂.

Đinh Mạnh Tường

Trang 16

Nguyễn Hoàng Cương

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ö R₁, R₄, R₆, ta sÏ quy bµi to¸n a vÒ tËp c¸c bµi to¸n con {b, c, e, f},

nh- sau:

•

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.

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.

®Ø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.

f, e, a. ta cã thÓ sö dông thñ tôc s¾p xÕp topo (xem [ ]) ®Ó s¾p xÕp thø tù c¸c bµi to¸n

Đinh Mạnh Tường

Trang 17

Nguyễn Hoàng Cương

®Ø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×

1.7.3 T×m kiÕm trªn ®å thÞ vµ/hoÆ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

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.

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  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

Đinh Mạnh Tường

Trang 18

Nguyễn Hoàng Cương

{Solvable(u) true; Operator(u) R; stop}}

4. Solvable(u) false;

end;

NhËn xÐt

•

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

Đinh Mạnh Tường

Trang 19

Nguyễn Hoàng Cương

Ch-¬ng II

C¸c chiÕn l-îc t×m kiÕm kinh nghiÖm

------------------------------------------

Trong ch-¬ng I, 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.

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 ®Ò.

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

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¸:

•

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

•

trong tr¹ng th¸i ®Ých. Ch¼ng h¹n tr¹ng th¸i ®Ých ë bªn ph¶i h×nh 2.1, vµ u lµ tr¹ng th¸i ë

Đinh Mạnh Tường

Trang 20