Ch
ng 1
ươ
BI U DI N BÀI TOÁN
Ể
Ễ
TRONG KHÔNG GIAN TR NG THÁI
Ạ
1. Đ t v n đ ặ ấ ề.
Khi gi i quy t bài toán b ng ph ng pháp tìm ki m, tr c h t ta ph i xác ả ế ằ ươ ế ướ ế ả
t c các đ i t đ nh ị không gian tìm ki mế bao g m t ồ ấ ả ố ượ ệ ng trên đó th c hi n ự
vi c tìm ki m. ế ệ
M t ph ộ ươ ệ ng pháp bi u di n v n đ phù h p là s d ng các khái ni m ử ụ ể ễ ề ấ ợ
tr ng thái ạ (state) và toán tử (operator).
Ph ng pháp gi i quy t v n đ d a trên khái ni m tr ng thái và toán t ươ ả ế ấ ề ự ệ ạ ử
đ c g i là cách ti p c n gi i quy t v n đ nh không gian tr ng thái. ượ ọ ế ậ ả ế ấ ề ạ ờ
2. Mô t tr ng thái ả ạ
Gi i bài toán trong không gian tr ng thái, tr c h t ph i xác đ nh d ng mô ả ạ ướ ế ả ạ ị
t ả ạ ấ tr ng thái bài toán sao cho bài toán tr nên đ n gi n h n, phù h p b n ch t ở ả ả ơ ơ ợ
v t lý c a bài toán (Có th s d ng các xâu ký hi u, véct ể ử ụ ậ ủ ệ ơ ề , m ng hai chi u, ả
cây, danh sách).
ầ M i tr ng thái chính là m i hình tr ng c a bài toán, các tình tr ng ban đ u ỗ ạ ủ ạ ạ ỗ
và tình tr ng cu i c a bài toán g i là tr ng thái đ u và tr ng thái cu i. ố ủ ạ ạ ầ ạ ọ ố
Ví d 1.ụ Bài toán đong n cướ
Cho 2 bình có dung tích l n l t là m và n (lit). V i ngu n n c không ầ ượ ớ ồ ướ
c. Không m t tính t ng quát có th h n ch , dùng 2 bình trên đ đong k lit n ạ ể ế ướ ấ ổ ể
gi thi t k <= min(m,n). ả ế
T i m i th i đi m xác đ nh, l ng n ể ạ ỗ ờ ị ượ ướ ả c hi n có trong m i bình ph n ệ ỗ
ánh b n ch t hình tr ng c a bài toán ủ ả ấ ạ ở ờ th i đi m đó. ể
- G i x là l ng n c hi n có trong bình dung tích m và y là l ọ ượ ướ ệ ượ ng
n c hi n có trong bình dung tích n. Nh v y b có th t (x,y) có th xem là ướ ư ậ ứ ự ệ ộ ể
thái c a bài toán. V i cách mô t t c a bài tr ng ạ ủ ớ ả ư ậ nh v y, các tr ng thái đ c bi ạ ặ ệ ủ
toán s là:ẽ
12
- Tr ng thái đ u: (0,0) ạ ầ
- Tr ng thái cu i: (x,k) ho c (k,y), 0
£ x £ m , 0 £ y £ n ạ ặ ố
Ví d 2.ụ Bài toán trò ch i 8 s ố ơ
ạ Trong b ng ô vuông 3 hàng, 3 c t , m i ô ch a m t s n m trong ph m ộ ố ằ ứ ả ộ ỗ
vi t ừ ị ố 1 đ n 8 sao cho không có 2 ô có cùng giá tr , có m t ô trong b ng b tr ng ế ả ộ ị
m t s p x p nào đó các s trong (không ch a giá tr nào c . Xu t phát t ị ứ ả ấ ừ ộ ắ ế ố
b ng, hãy d ch chuy n ô tr ng sang ph i, sang trái, lên trên ho c xu ng d ả ể ả ặ ố ố ị ướ i
(n u có th đ c) đ đ a v b ng ban đ u v b ng qui c tr ể ượ ế ể ư ề ả ề ả ầ ướ ướ ẳ c. Ch ng
h n Hình 1. d ạ ướ ự i đây là b ng xu t phát và Hình 2. là b ng mà ta ph i th c ả ấ ả ả
hi n các b c di chuy n ô tr ng đ đ t đ c. ệ ướ ể ạ ượ ể ố
8 6
3 2 4 1 5 7 Hình 1.
2
3 1 4 8 7 5 6 Hình 2.
Giá tr các ph n t trong b ng xác đ nh tr ng thái bài toán. Vì v y có ầ ử ị ả ạ ậ ị
3*3= (aij) , aij˛ {0..8}, aij <
th mô t tr ng thái c a bài toán b ng m t ma tr n A ể ả ạ ủ ằ ậ ộ
> akl, " i<>k, j<> l
- Tr ng thái đ u c a bài toán là ma tr n ậ ầ ủ ạ
382
461
507
(cid:246) (cid:230) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) ł Ł
- Tr ng thái cu i là ma tr n ậ ạ ố
321
408
567
(cid:246) (cid:230) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) ł Ł
13
Có th phát bi u d ng t ng quát c a bài toán này (Trò ch i n ủ ể ể ạ ổ ơ 2-1 s )ố
Ví d 3.ụ Bài toán tháp Hà N i ộ
c c 1 ban đ u có n đĩa s p x p theo th t to d n t Cho ba c c 1, 2, 3. ọ Ở ọ ứ ự ế ầ ắ ầ ừ
d i lên trên. Hãy d ch chuy n n đĩa đó sang c c th 3 sao cho: ướ ứ ể ọ ị
- M i l n ch chuy n m t đĩa. ỗ ầ ể ộ ỉ
- Trong m i c c không cho phép đĩa to n m trên đĩa nh h n. ỗ ọ ỏ ơ ằ
Bài toán xác đ nh khi bi c t ng đĩa đang n m c c nào. Hay nói cách t đ ị ế ượ ừ ằ ở ọ
khác, có hai cách xác đ nh: ị
1- C c 1 hi n đang ch a nh ng đĩa nào? C c 2 hi n đang ch a nh ng đĩa ữ ứ ứ ữ ệ ệ ọ ọ
nào? Và c c 3 đang ch a nh ng đĩa nào. ữ ứ ọ
2- Đĩa l n th i hi n đang nàm c c nào? ( i = 1 .. n ) ứ ệ ớ ở ọ
Nh v y cách mô t tr ng thái bài toán không duy nh t, v n đ là ch n cách ư ậ ả ạ ề ấ ấ ọ
mô t nào đ đ t đ ả ể ạ ượ c m c đích d dàng nh t. ễ ụ ấ
ỗ Theo trên, v i cách th nh t ta ph i dùng 3 danh sách đ ng vì s đĩa trên m i ứ ấ ả ớ ố ộ
c c là khác nhau trong t ng th i đi m khác nhau. ừ ọ ể ờ
Cách th hai, nhìn qua thì khó mô t nh ng d a vào khái ni m v b có th ứ ả ề ộ ự ư ệ ứ
i˛ {1, 2, 3}, i˛ {1 ..n}. Khi đó b có th t
trong toán h c, cách này mô t t ự ọ ả bài toán hi u qu h n. Th t v y, n u g i x ọ i ậ ậ ả ơ ệ ế
là c c ch a đĩa l n th i, trong đó x ớ ứ ứ ọ ứ ự ộ
(x1, x2, . . ,xn) có th dùng làm d ng mô t ể ạ ả ạ ớ tr ng thái đang xét c a bài toán. V i ủ
cách mô t này, ả
Tr ng thái đ u là (1,1,. . .,1) ầ ạ
Tr ng thái cu i là (3,3,. . .,3) ố ạ
3. Toán t chuy n tr ng thái. ử ể ạ
Toán t tr ng thái ử chuy n tr ng thái th c ch t là các phép bi n đ i đ a t ấ ổ ư ừ ạ ự ể ế ạ
này sang tr ng thái khác. Có hai cách dùng đ bi u di n các toán t ể ể ễ ạ : ử
- Bi u di n nh m t hàm xác đ nh trên t p các tr ng thái và nh n giá tr ư ộ ể ễ ậ ạ ậ ị ị
cũng trong t p này. ậ
- Bi u di n d ễ ể ướ ạ i d ng các quy t c s n xu t S? A có nghĩa là n u có ấ ế ắ ả
14
tr ng thái S thì có th đ a đ n tr ng thái A. ể ư ế ạ ạ
Ví d 1.ụ Bài toán đong n cướ
Các thao tác s d ng đ chuy n tr ng thái này sang tr ng thái khác ử ụ ể ể ạ ạ
g m: ồ
Đ đ y m t bình, đ h t n c trong m t bình ra ngoài, đ n c t bình này ổ ế ướ ổ ầ ộ ổ ướ ừ ộ
sang bình khác. Nh v y, n u tr ng thái đang xét là (x,y) thì các tr ng thái k ư ậ ế ạ ạ ế
ti p có th chuy n đ n s là: ế ẽ ể ể ế
(m,y)
(x,n)
(0,y)
(x,0)
(x,y) (0, x+ y) nếu x+y < = n
(x+y -n,n) n u x+y > n ế
(x+ y,0) n u x+y < = m ế
(m, x+y-m) n u x+y > m ế
Ví d 2.ụ Trò ch i 8 s ơ ố
Các thao tác đ chuy n tr ng thái t ng ng v i vi c chuy n ô tr ng sang ể ể ạ ươ ứ ệ ể ớ ố
- Bi u di n theo quy t c s n xu t:
ph i, sang trái, lên, xu ng n u có th đ c. ể ượ ế ả ố
13254876
13425876
13425876
13425687
ắ ả ể ễ ấ
- Bi u di n theo m t hàm ễ ể ộ
u là hàm bi u di n cho toán t
G i hàm f chuy n ô tr ng lên trên; g i B (B= ọ ễ ể ử ể ố ọ
ij)) lên trên,
15
(bij)) là tr ng thái sau khi di chuy n ô tr ng tr ng thái A (A= (a ể ạ ố ở ạ
0, j0) (hay nói cách khác ai0 j0 =
nghĩa là: B= fu(A), gi v trí (i ả ử s ô tr ng đang ố ở ị
0) thì hàm f đ c xác đ nh nh sau: ượ ư ị
0 = 1
" aij (i, j) n u iế
„ fu(aij) = (i0-1, j0) và (i, j) „ (i0, j0) và i0 >1 aij n u (i, j) ế
0, j0), i0 >1
ai0-1, j0 n u (i, j) = (i ế
0-1, j0), i0 >1
ai0, j0 n u (i, j) = (i ế
T ng t , có th xác đ nh các phép chuy n ô tr ng xu ng d i f ươ ự ể ể ố ố ị ướ d, qua trái fl,
qua ph i fả r nh sau: ư
0 = 3
" aij (i, j) n u iế
„ fd(aij) = (i0+1, j0) và (i, j) „ (i0, j0) và i0 <3 aij n u (i, j) ế
0, j0), i0 <3
ai0-1, j0 n u (i, j) = (i ế
0+1, j0), i0 <3
ai0, j0 n u (i, j) = (i ế
0 = 1
" aij (i, j) n u jế
„ aij fl(aij) = (i0, j0-1) và (i, j) „ (i0, j0) và j0 > 1 n u (i, j) ế
0, j0), j0 > 1
ai0-1, j0 n u (i, j) = (i ế
0, j0-1), j0 > 1
ai0, j0 n u (i, j) = (i ế
0 = 3
" aij (i, j) n u jế
„ aij fr(aij) = (i0, j0+1) và (i, j) „ (i0, j0) và j0 < 3 n u (i, j) ế
0, j0), j0 < 3
ai0-1, j0 n u (i, j) = (i ế
0, j0+1), j0 < 3
ai0, j0 n u (i, j) = (i ế
Ví d 3.ụ Bài toán Tháp Hà N i v i n=3. ộ ớ
ng h p nh sau: M i tr ng thái là m t b ba (i, j, k). Có các tr ộ ộ ỗ ạ ườ ư ợ
- Ba đĩa cùng n m trên m t c c: (i, i, i) ộ ọ ằ
- Hai đĩa cùng n m trên m t c c: (i, i, j), (i, j, i), (j, i, i) ộ ọ ằ
16
- Ba đĩa n m trên ba c c phân bi t: (i, j, k) ằ ọ ệ
(i, i, i) (i, i, j)
(i, i, k)
(i, i, j) (i, i, k)
(i, k, j)
(i, i, i)
(i, j, i) (i, j, k)
(i, j, j)
(i, k, i)
(j, i, i) (j, i, j)
(j, i, k)
(k, i, i)
(i, j, k) (i, i, k)
(i, j, j)
(i, j, i)
4 Kkhông gian tr ng thái là t p t
4. Không gian tr ng thái c a bài toán. ủ ạ
t c các tr ng thái có th có và t p các toán ậ ấ ả ể ạ ậ ạ
c a bài toán. t ử ủ
Không gian tr ng thái là m t b b n, Ký hi u: K= (T, S, G, F). Trong ộ ộ ố ệ ạ
đó,
T: t p t t c các tr ng thái có th có c a bài toán ậ ấ ả ủ ể ạ
S: tr ng thái đ u ầ ạ
G: t p các tr ng thái đích ạ ậ
F: t p các toán t ậ ử
hông gian tr ng thái c a bài toán đong n c là b b n T, S, G, F Ví d 1. Kụ ủ ạ ướ ộ ố
xác đinh nh sau: ư
4 T = { (x,y) / 0 <= x <= m; 0 <= y <= n }
5 S = (0,0)
17
6 G = { (x,k) ho c (k,y) / 0 <= x <= m; 0 <= y <= n} ặ
7 F = T p các thao tác đong đ y, đ ra ho c đ sang bình khác th c hi n trên ặ ổ ự ệ ậ ầ ổ
m t bình. ộ
ộ ớ
Ví d 2. ụ Không gian tr ng thái c a bài toán Tháp Hà n i v i n = 3: ạ ủ T = { (x1, x2, x3)/ xi ˛ {1, 2, 3} }
S = (1, 1, 1)
G = {(3, 3, 3)}
ầ F = T p các kh năng có th chuy n đĩa đã xác đ nh trong ph n ể ể ậ ả ị
tr c.ướ
Ví d 3.ụ Không gian tr ng thái c a bài toán trò ch i 8 s : ố ủ ạ ơ
T = { (aij)3x3 / 0<= aij <= 8 và aij <> akl v i i<> j ho c k <> l} ặ ớ
S = Ma tr n xu t phát c a bài toán, ủ ậ ấ
G = Ma tr n cu i cùng c a bài toán (các s n m theo v trí yêu ố ằ ủ ậ ố ị
c u)ầ
F = {fl, fr, fu, fd}
Tìm ki m l i gi i trong không gian tr ng thái là quá trình tìm ki m xu t phát ế ờ ả ế ấ ạ
t ừ ạ tr ng thái ban đ u, d a vào toán t ầ ự ử ạ chuy n tr ng thái đ xác đ nh các tr ng ể ể ạ ị
thái ti p theo cho đ n khi g p đ c tr ng thái đích. ặ ượ ế ế ạ
5. Bi u di n không gian tr ng thái d ể ễ ạ ướ ạ i d ng đ th ồ ị
5.1. Các khái ni mệ
• Đ th G = (V,E) trong đó V:t p đ nh, E: t p cung (E
(cid:204) V*V) ồ ị ậ ậ ỉ
- G là đ th vô h
Chú ý
ng thì (i, j) là m t c nh cũng nh là (j, i) (t c là:(i, j) ˛ E ồ ị ướ ộ ạ ư ứ
thì (j,i)˛ E)
2
- N u G là đ th có h ng thì cung (i, j) hoàn toàn khác v i cung (j, i). ồ ị ế ướ ớ
1 và đ th có h ướ ồ ị 1
ng G ng G Ví d ụ xét d th vô h ướ
2
4
2
4
3
3
18
ồ ị 1
G1 G2
• T p đ nh k : ề ỉ ậ
" n˛ V, T(n)={m˛ V/ (n,m) ˛ E}đ c g i là t p các đ nh k c a n ượ ọ ề ủ ậ ỉ
• Đ ng đi: ườ
1 fi
i ˛ V, "
p = (n1,...,nk) đ c g i là đ ng đi t đ nh n i=1,k ; ượ ọ ườ ừ ỉ nk n u nế
• Cây là đ th có đ nh g c n
(ni, ni+1)˛ E " i=1, k -1
ồ ị ố 0˛ V tho : ả ỉ
0˛ V có nh ng tính ch t ấ ữ
M t đ th G=(V, E) g i là cây n u t n t ộ ồ ị ế ồ ạ ọ i m t đ nh n ộ ỉ
sau:
-
(cid:217) (cid:217)
-
" n˛ V, n˛ T(n0), trong đó T(n0): t p các đ nh thu c dòng dõi c a n ậ ủ 0 (n0 là tổ ộ ỉ
tiên c a n)ủ " n˛ V, $! m˛ V sao cho n˛ T(m); m đ c g i là cha c a n. ượ ọ ủ
5.2. Bi u di n không gian tr ng thái b ng đ th ồ ị ể ễ ạ ằ
Theo ngôn ng đ th , không gian tr ng thái t ữ ồ ị ạ ươ ng ng v i m t đ th ớ ộ ồ ị ứ
ng trong đó: Các tr ng thái t đ nh h ị ướ ạ ươ ồ ị ế ng ng v i các đ nh trong đ th , n u ứ ớ ỉ
i toán t chuy n tr ng thái thì có cung (s, t) t n t ồ ạ ử ể ạ
Đ th y rõ m i t ng quan, ta có b ng sau ể ấ ố ươ ả
KGTT Đ thồ ị
Tr ng thái Đ nhỉ ạ
Cung Toán tử
Đ ng đi Dãy các tr ng thái liên ạ ườ
ti pế
5.3. Bi u di n đ th ễ ồ ị ể
Cho đ th G = (V,E) , gi s V={1, 2,....,n}. Có hai cách th ng dùng ồ ị ả ử ườ
đ bi u di n đ th G l u tr trong máy tính. ể ể ồ ị ữ ư ễ
i) Bi u di n b ng ma tr n k ằ ậ ề ể ễ
ij)nxn, v i n là s đ nh c a đ
Đ th G đ c bi u di n b i ma tr n k A=(a ồ ị ượ ể ễ ề ậ ở ủ ồ ố ỉ ớ
19
th , trong đó: ị
aij= 1 ˛ E n u (i, j) ế
0 trong tr i ườ ng h p ng ợ c l ượ ạ
N u G là đ th vô h ng thì ma tr n k A là ma tr n đ i x ng. ồ ị ế ướ ố ứ ề ậ ậ
2
1 và đ th có h ồ ị
ng G ng G Ví dụ V i đ th vô h ớ ồ ị ướ ướ ở ậ trên ta có các ma tr n
k sau: ề
0 1 1 1
1 0 1 1
1 1 0 0
1 1 0 0
0 1 0 0
1 0 0 0
0 1 0 1
1 1 0 0
G1: G2:
ii) Bi u di n b ng danh sách k . ề ằ ể ễ
V i m i đ nh i c a đ th , ta có m t danh sách t ủ ồ ị ỗ ỉ ớ ộ ấ ả ề ớ t c các đ nh k v i i, ỉ
ợ ta ký hi u là List(i). Đ th hi n List(i) ta có th dùng m ng, ki u t p h p ể ể ệ ể ậ ể ệ ả
hay ki u con tr . Ví d v i đ th G1, ta có List(1)= [2, 3, 4] ụ ớ ồ ị ể ỏ
c m=3, n=2, k=1 Ví d 1.ụ Bài toán đong n ướ
(0,0)
(3,0)
(0,2)
(1,2)
(3,2)
(2,0)
(1,0)
(0,1)
(2,2)
(3,1)
111
Ví d 2.ụ Tháp Hà N i v i n = 3 ộ ớ
(112)
(111) (113)
112
(132)
(123)
(133)
(131)
(121)
(122)
(233)
(322)
(231)
(232)
(323)
(321)
(221)
(212)
(313)
(331)
(222)
(223)
(213)
(211)
(311)
(312)
(332)
(333)
20
21
6. BÀI T PẬ
Xây d ng không gian tr ng thái đ i v i các bài toán sau: ố ớ ự ạ
6.1. Cho n thành ph đánh s t 1 đ n n. Giao thông đ ng b gi a hai thành ố ừ ố ế ườ ộ ữ
ij nh sau: a
ij = -1 có nghĩa là không có đ
ph i và j đ ố ượ c cho b i giá tr a ở ị ư ngườ
ij = 1 n u có đ ế
thành ph i sang thành ph j và a b đi t ộ ừ ố ố ườ ng đi tr c ti p t ự ế ừ
thành ph i sang thành ph j. Tìm đ ng đi t thành ph i ố ố ườ ừ ố 0 sang thành ph jố 0.
k viên s i, đ
n
1 viên, đ ng th 2 có a
6.2. Cho k và n là 2 s nguyên d ng. Có 2 ố ươ ỏ ượ c phân b trong n ố
2 viên, …, đ ng th n có a ố
đ ng, đ ng th nh t có a ố ứ ấ ố ứ ố ứ
1+ a2 + …+ an = 2k. Ng
viên và t t nhiên a i ta c n san s l ng s i t các ấ ườ ẻ ượ ầ ỏ ừ
ụ đ ng đ d n s i tr v 1 đ ng. Quy t c san s i nh sau: m i l n san áp d ng ắ ố ể ồ ỏ ở ề ỗ ầ ư ố ỏ
cho 2 đ ng s i, gi ố ỏ ả ử ả s 1 đ ng có a viên và đ ng kia có b viên (không gi m ố ố
‡ thi t a b) thì san s i t đ ng có a viên sang đ ng có b t ng quát, có th gi ổ ể ả ế ỏ ừ ố ố
viên đ thành m t đ ng có a-b viên và đ ng kia 2*b viên. ộ ố ể ố
H ng d n: ẫ Tr ng thái c a bài toán ph i xác đ nh đ ướ ủ ạ ả ị ượ ố ỏ c s s i hi n có trong ệ
m i đ ng. ỗ ố
1, a2, …, an đ
6.3. M t dãy các s nguyên d ng a c g i là h p lý n u tho ộ ố ươ ượ ế ợ ọ ả
-
mãn hai đi u ki n: ệ ề
-
i
an là s nguyên t . ố ố
ai+1 = ai +1 ho c 2*a ặ
1, a2, …, an.
Cho tr c s a ướ ố 1, hãy tìm dãy h p lý a ợ
6.4 Bài toán ng i đ a hàng. ườ ư
Ng i đ a hàng c n ph i xác đ nh đ ườ ư ầ ả ị ượ c hành trình ng n nh t sao cho ắ ấ
m i thành ph đi đ n đúng m t l n và quay tr l i thành ph xu t phát. Gi ộ ầ ở ạ ế ố ỗ ấ ố ả
t c n thành ph đánh s t s thành ph xu t phát là thành ph 1, có t ử ấ ố ố ấ ả ố ừ ố ế 1 đ n
22
n.
H ng d n ướ ẫ :
- M i tr ng thái cho b i danh sách các thành ph đã đi qua cho đ n th i ờ ế ạ ỗ ở ố
đi m hi n t i, trong đó không cho phép m t thành ph nào đ ệ ạ ể ộ ố ượ ệ c xu t hi n ấ
nhi u h n m t l n tr thành ph 1 sau khi đã li t kê t t c các thành ph ộ ầ ừ ề ơ ố ệ ấ ả ố
còn l i.ạ
- Các toán t ng ng v i các hành đ ng t ử ươ ứ ớ ộ
1- đi t i thành ph 1 ớ ố
2- đi t i thành ph 2 ớ ố
3- đi t i thành ph 3. ớ ố
. . .
6.5. Bài toán phân tích cú pháp.
ế Văn ph m G là b b n G = (N, T, P, S), N là t p ký hi u không k t ộ ố ệ ạ ậ
˛ thúc, T là t p ký hi u k t thúc, S N là ký hi u đ u và P là t p s n xu t có ế ệ ậ ậ ả ệ ầ ấ
a a fi b , đây , b ˛ (NUT). Ngôn ng sinh ra b i văn ph m G đ d ng ạ ở ữ ạ ở ượ c
ở
1, …, w
n ˛
˛ đ nh nghĩa b i:\ ị L(G) = { w w T | S (cid:222) }, S (cid:222) w có nghĩa là $ w (NUT) sao cho
i (cid:222)
i+1, w
1 = S và w
n = w
w w .
Bài toán phân tích cú pháp đ ượ c phát bi u : ch tr ể ướ ớ c văn ph m G v i ạ
23
w xâu w ˛ T đã cho hãy xác đ nh xem ˛ L(G) hay không ? ị
