Giáo trình Trí Tuệ Nhân Tạo -chương 1- GIẢI QUYẾT VẤN ĐỀ BẰNG TÌM KIẾ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á.
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
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Trang 1
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«.
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Trang 2
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.1 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
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Trang 3
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 0 (u 0 ∈
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.
• 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).
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Trang 4
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.
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
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Trang 5
víi c¸c hµnh ®éng chë 1 hoÆc 2 ngêi qua s«ng. Nh ng ë ®©y ta cÇn lu ý 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.2 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).
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:
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Trang 6
• 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.
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Trang 7
C©y t×m kiÕm
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 cha ®î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.3 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.
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Trang 8
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.3.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 Breadth_First_Search;
begin
1. Khëi t¹o danh s¸ch L chØ chøa tr¹ng th¸i ban ®Çu;
2. loop do
2.1 if L rçng then
{th«ng b¸o 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) 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 2 + ... + b d-1 + k
Trong ®ã k cã thÓ lµ 1, 2, ..., bd. Do ®ã sè lín nhÊt c¸c ®Ønh cÇn xem
xÐt lµ:
1 + b + b 2 + ... + 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(bd). §é phøc t¹p kh«ng gian còng lµ O(bd), 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µ bd.
§Ó 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:
§é s©u d Thêi gian Kh«ng gian
4 11 gi©y 1 megabyte
6 18 gi©y 111 megabytes
8 31 giê 11 gigabytes
10 128 ngµy 1 terabyte
12 35 n¨m 111 terabytes
14 3500 n¨m 11.111 terabytes
1.3.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
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Trang 10
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(bd), 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 cha ®î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(bd)!
1.3.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
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Trang 11
®å 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, lu 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.3.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, nhng
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
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Trang 12
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 0;
depth(u 0) 0;
2. loop do
2.1 if L rçng then
{th«ng b¸o thÊt b¹i; stop};
2.2 Lo¹i tr¹ng th¸i u ë ®Çu danh s¸ch L ;
2.3 if u lµ tr¹ng th¸i kÕt thóc then
{th«ng b¸o thµnh c«ng; stop};
2.4 if depth(u) • 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 2 + ... + 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 2 + ... + 2b d-1 + 1b d
Do ®ã thêi gian t×m kiÕm s©u lÆp lµ O(bd).
Tãm l¹i, t×m kiÕm s©u lÆp cã ®é phøc t¹p thêi gian lµ O(bd) (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 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.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:
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 ∫ (xex + x 3) 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.
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Trang 14
Sö dông c¸c quy t¾c tÝnh tÝch ph©n (quy t¾c tÝnh tÝch ph©n cña mét tæng,
quy t¾c tÝnh tÝch ph©n tõng phÇn...), sö dông c¸c phÐp biÕn ®æi biÕn sè, c¸c
phÐp biÕn ®æi c¸c hµm (ch¼ng h¹n, c¸c phÐp biÕn ®æi l îng gi¸c),... ®Ó ®a
tÝch ph©n cÇn tÝnh vÒ tÝch ph©n cña c¸c hµm sè s¬ cÊp mµ chóng ta ®·
biÕt c¸ch tÝnh. Ch¼ng h¹n, ®èi víi tÝch ph©n ∫ (xex + x 3) dx, ¸p dông quy t¾c
tÝch ph©n cña tæng ta ®a vÒ hai tÝch ph©n ∫ xexdx vµ ∫ x 3dx. ¸p dông quy
t¾c tÝch ph©n tõng phÇn ta ®a tÝch ph©n ∫ xexdx vÒ tÝch ph©n ∫ exdx. Qu¸
tr×nh trªn cã thÓ biÓu diÔn bëi ®å thÞ trong h×nh 1.5.
C¸c tÝch ph©n ∫ exdx vµ ∫ x 3dx 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:
∫ (f 1 + f 2) dx → ∫ f 1 dx, ∫ f 2 dx vµ ∫ u dv → ∫ v du
C¸c tr¹ng th¸i kÕt thóc lµ c¸c bµi to¸n s¬ cÊp (c¸c bµi to¸n ®· biÕt c¸ch
gi¶i). Ch¼ng h¹n, trong bµi to¸n tÝnh tÝch ph©n, c¸c tÝch ph©n c¬ b¶n lµ c¸c
tr¹ng th¸i kÕt thóc. Mét ®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
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Trang 15
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 con ®êng nèi, nèi thµnh phè nµy víi thµnh phè kh¸c. B©y giê ta ®a
ra mét c¸ch biÓu diÔn kh¸c dùa trªn viÖc quy vÊn ®Ò vÒ c¸c vÊn ®Ò con. 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.
Mçi mét trong hai bµi to¸n trªn l¹i cã thÓ ph©n nhá nh sau
1) Bµi to¸n t×m ®êng ®i tõ A ®Õn B qua E ®îc quy vÒ:
1.1 T×m ®êng ®i tõ A ®Õn E (vµ)
1.2 T×m ®êng ®i tõ E ®Õn B.
2) Bµi to¸n t×m ®êng ®i tõ A ®Õn B qua G ®îc quy vÒ:
2.1 T×m ®êng ®i tõ A ®Õn G (vµ)
2.2 T×m ®êng ®i tõ G ®Õn B.
Qu¸ tr×nh rót gän vÊn ®Ò nh trªn cã thÓ biÓu diÔn díi d¹ng ®å thÞ (®å
thÞ vµ/hoÆc) trong h×nh 1.7. ë ®©y mçi bµi to¸n t×m ®êng ®i tõ mét thµnh
phè tíi mét thµnh phè kh¸c øng víi mét tr¹ng th¸i. C¸c tr¹ng th¸i kÕt thóc lµ c¸c
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Trang 16
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.4.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íi d¹ng ®å thÞ ®Þnh híng ®Æc biÖt ®îc gäi lµ ®å thÞ vµ/hoÆc. §å
thÞ nµy ®îc x©y dùng nh sau:
Mçi bµi to¸n øng víi mét ®Ønh cña ®å thÞ. NÕu cã mét to¸n tö quy mét
bµi to¸n vÒ mét bµi to¸n kh¸c, ch¼ng h¹n R : a →b, th× trong ®å thÞ sÏ cã cung
g¸n nh·n ®i tõ ®Ønh a tíi ®Ønh b. §èi víi mçi to¸n tö quy mét bµi to¸n vÒ mét
sè bµi to¸n con, ch¼ng h¹n R : a →b, c, d ta ®a vµo mét ®Ønh míi a1, ®Ønh nµy
biÓu diÔn tËp c¸c bµi to¸n con {b, c, d} vµ to¸n tö R : a →b, c, d ®îc biÓu diÔn
bëi ®å thÞ h×nh 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:
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Trang 17
R1 : a →d, e, f
R2 : a →d, k
R3 : a →g, h
R4 : d →b, c
R5 : f →i
R6 : f →c, j
R7 : k →e, l
R8 : k →h
• 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 a1, a2, a3 ®î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 a1 biÓu
diÔn tËp c¸c bµi to¸n {d, e, f} vµ a1 ®îc gi¶i quyÕt nÕu d vµ e vµ f ®îc gi¶i
quyÕt. Cßn t¹i ®Ønh a, ta cã c¸c to¸n tö R 1, R2, R3 quy bµi to¸n a vÒ c¸c bµi to¸n
con kh¸c nhau, do ®ã a ®îc gi¶i quyÕt nÕu hoÆc a1 = {d, e, f}, hoÆc a2 = {d, k},
hoÆc a3 = {g, h} ®îc gi¶i quyÕt.
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.
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Trang 18
Trong ®å thÞ rót gän nµy, ta sÏ nãi ch¼ng h¹n d, e, f lµ c¸c ®Ønh kÒ ®Ønh a
theo to¸n tö R1, cßn d, k lµ c¸c ®Ønh kÒ a theo to¸n tö R2.
Khi ®· cã c¸c to¸n tö rót gän vÊn ®Ò, th× b»ng c¸ch ¸p dông liªn tiÕp c¸c
to¸n tö, ta cã thÓ ®a bµi to¸n cÇn gi¶i vÒ mét tËp c¸c bµi to¸n con. Ch¼ng h¹n,
trong vÝ dô trªn nÕu ta ¸p dông c¸c to¸n tö R 1, R4, R6, ta sÏ quy bµi to¸n a vÒ
tËp c¸c bµi to¸n con {b, c, e, f}, tÊt c¶ c¸c bµi to¸n con nµy ®Òu lµ s¬ cÊp. Tõ c¸c
to¸n tö R1, R4 vµ R6 ta x©y dùng ®îc mét c©y trong h×nh 1.11a, c©y nµy ®îc
gäi lµ c©y nghiÖm. C©y nghiÖm ®îc ®Þnh nghÜa nh sau:
C©y nghiÖm lµ mét c©y, trong ®ã:
• Gèc cña c©y øng víi bµi to¸n cÇn gi¶i.
• TÊt c¶ c¸c l¸ cña c©y lµ c¸c ®Ønh kÕt thóc (®Ønh øng víi c¸c bµi to¸n s¬
cÊp).
• NÕu u lµ ®Ønh trong cña c©y, th× c¸c ®Ønh con cña u lµ c¸c ®Ønh kÒ u
theo mét to¸n tö nµo ®ã.
C¸c ®Ønh cña ®å thÞ vµ/hoÆc sÏ ®îc g¾n nh·n gi¶i ®îc hoÆc kh«ng gi¶i
®îc.
C¸c ®Ønh gi¶i ®îc ®îc x¸c ®Þnh ®Ö quy nh sau:
• C¸c ®Ønh kÕt thóc lµ c¸c ®Ønh gi¶i ®îc.
• NÕu u kh«ng ph¶i lµ ®Ønh kÕt thóc, nhng 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.
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Trang 19
Ta cã nhËn xÐt r»ng, nÕu bµi to¸n a gi¶i ®îc th× sÏ cã mét c©y nghiÖm
gèc a, vµ ngîc l¹i nÕu cã mét c©y nghiÖm gèc a th× a gi¶i ®îc. HiÓn nhiªn lµ,
mét bµi to¸n gi¶i ®îc cã thÓ cã nhiÒu c©y nghiÖm, mçi c©y nghiÖm biÓu
diÔn mét c¸ch gi¶i bµi to¸n ®ã. Ch¼ng h¹n trong vÝ dô ®· nªu, bµi to¸n a cã
hai c©y nghiÖm trong h×nh 1.11.
Thø tù gi¶i c¸c bµi to¸n con trong mét c©y nghiÖm lµ nh sau. Bµi to¸n øng
víi ®Ønh u chØ ®îc gi¶i sau khi tÊt c¶ c¸c bµi to¸n øng víi c¸c ®Ønh con cña u
®· ®îc gi¶i. Ch¼ng h¹n, víi c©y nghiÖm trong h×nh 1.11a, thø tù gi¶i c¸c bµi
to¸n cã thÓ lµ b, c, d, j, 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 trong mét c©y nghiÖm. §¬ng nhiªn ta còng cã
thÓ gi¶i quyÕt ®ång thêi c¸c bµi to¸n con ë cïng mét møc trong c©y nghiÖm.
VÊn ®Ò cña chóng ta b©y giê lµ, t×m kiÕm trªn ®å thÞ vµ/hoÆc ®Ó x¸c
®Þnh ®îc ®Ønh øng víi bµi to¸n ban ®Çu lµ gi¶i ®îc hay kh«ng gi¶i ®îc, vµ
nÕu nã gi¶i ®îc th× x©y dùng mét c©y nghiÖm cho nã.
1.4.3 T×m kiÕm trªn ®å thÞ vµ/hoÆc
Ta sÏ sö dông kü thuËt t×m kiÕm theo ®é s©u trªn ®å thÞ vµ/hoÆc ®Ó
®¸nh dÊu c¸c ®Ønh. C¸c ®Ønh sÏ ®îc ®¸nh dÊu gi¶i ®îc hoÆc kh«ng gi¶i ®îc
theo ®Þnh nghÜa ®Ö quy vÒ ®Ønh gi¶i ®îc vµ kh«ng gi¶i ®îc. XuÊt ph¸t tõ
®Ønh øng víi bµi to¸n ban ®Çu, ®i xuèng theo ®é s©u, nÕu gÆp ®Ønh u lµ
®Ønh kÕt thóc th× nã ®îc ®¸nh dÊu gi¶i ®îc. NÕu gÆp ®Ønh u kh«ng ph¶i
lµ ®Ønh kÕt thóc vµ tõ u kh«ng ®i tiÕp ®îc, th× u ®îc ®¸nh dÊu kh«ng gi¶i ®-
îc. Khi ®i tíi ®Ønh u, th× tõ u ta lÇn l ît ®i xuèng c¸c ®Ønh v kÒ u theo mét
to¸n tö R nµo ®ã. NÕu ®¸nh dÊu ®îc mét ®Ønh v kh«ng gi¶i ®îc th× kh«ng
cÇn ®i tiÕp xuèng c¸c ®Ønh v cßn l¹i. TiÕp tôc ®i xuèng c¸c ®Ønh kÒ u theo
mét to¸n tö kh¸c. NÕu tÊt c¶ c¸c ®Ønh kÒ u theo mét to¸n tö nµo ®ã ®îc ®¸nh
dÊu gi¶i ®îc th× u sÏ ®îc ®¸nh dÊu gi¶i ®îc vµ quay lªn cha cña u. Cßn nÕu tõ
u ®i xuèng c¸c ®Ønh kÒ nã theo mäi to¸n tö ®Òu gÆp c¸c ®Ønh kÒ ®îc ®¸nh
dÊu kh«ng gi¶i ®îc, th× u ®îc ®¸nh dÊu kh«ng gi¶i ®îc vµ quay lªn cha cña u.
Ta sÏ biÓu diÔn thñ tôc t×m kiÕm theo ®é s©u vµ ®¸nh dÊu c¸c ®Ønh ®·
tr×nh bµy trªn bëi hµm ®Ö quy Solvable(u). Hµm nµy nhËn gi¸ trÞ true nÕu u
gi¶i ®îc vµ nhËn gi¸ trÞ false nÕu u kh«ng gi¶i ®îc. Trong hµm Solvable(u),
ta sÏ sö dông:
• BiÕn Ok. Víi mçi to¸n tö R ¸p dông ®îc t¹i u, biÕn Ok nhËn gi¸ trÞ true
nÕu tÊt c¶ c¸c ®Ønh v kÒ u theo R ®Òu gi¶i ®îc, vµ Ok nhËn gi¸ trÞ false
nÕu cã mét ®Ønh v kÒ u theo R kh«ng gi¶i ®îc.
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Trang 20
