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ả ế ằ ươ ế ướ ế ả
đ nh ịkhông gian tìm ki mế bao g m t t c các đ i 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ầ ượ ớ ồ ướ
h n ch , dùng 2 bình trên đ đong k lit n c. Không m t tính t ng quát có thạ ế ể ướ ấ ổ ể
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àướ ệ ư ậ ộ ứ ự ể
tr ng ạthái c a bài toán. V i cách mô t nh v y, các tr ng thái đ c bi t c a bàiủ ớ ả ư ậ ạ ặ ệ ủ
toán s là:ẽ
-Tr ng thái đ u: (0,0)ạ ầ
12
-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ừ ế ị ộ ả ị ố
(không ch a giá tr nào c . Xu t phát t m t s p x p nào đó các s trongứ ị ả ấ ừ ộ ắ ế ố
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.ệ ướ ể ố ể ạ ượ
2 8 3
1 6 4
7 5
Hình 1.
1 2 3
8 4
7 6 5
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óị ầ ử ả ị ạ ậ
th mô t tr ng thái c a bài toán b ng m t ma tr n Aể ả ạ ủ ằ ộ ậ 3*3= (aij) , aij∈{0..8}, aij <
> akl, ∀i<>k, j<> l
-Tr ng thái đ u c a bài toán là ma tr nạ ầ ủ ậ
-Tr ng thái cu i là ma tr nạ ố ậ
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 )ố
13
507
461
382
567
408
321
Ví d 3.ụ Bài toán tháp Hà N i ộ
Cho ba c c 1, 2, 3. c c 1 ban đ u có n đĩa s p x p theo th t to d n tọ Ở ọ ầ ắ ế ứ ự ầ ừ
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 t đ c t ng đĩa đang n m c c nào. Hay nói cáchị ế ượ ừ ằ ở ọ
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ứ ả ư ự ệ ề ộ ứ
t trong toán h c, cách này mô 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ọ ứ ớ ứ i∈{1, 2, 3}, i∈{1 ..n}. Khi đó b có th tộ ứ ự
(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 chuy n tr ng thái th c ch t là các phép bi n đ i đ a t tr ng tháiử ể ạ ự ấ ế ổ ư ừ ạ
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óể ễ ướ ạ ắ ả ấ ế
tr ng thái S thì có th đ a đ n tr ng thái A.ạ ể ư ế ạ
14
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ể ể ạ ươ ứ ớ ệ ể ố
ph i, sang trái, lên, xu ng n u có th đ c.ả ố ế ể ượ
-Bi u di n theo quy t c s n xu t:ể ễ ắ ả ấ
-Bi u di n theo m t hàmể ễ ộ
G i hàm fọu là hàm bi u di n cho toán t chuy n ô tr ng lên trên; g i B (B=ể ễ ử ể ố ọ
(bij)) là tr ng thái sau khi di chuy n ô tr ng tr ng thái A (A= (aạ ể ố ở ạ ij)) lên trên,
15
'()*+,-6
'(*+),-6
'()*+6,-
'()*+,-6
nghĩa là: B= fu(A), gi s ô tr ng đang v trí (iả ử ố ở ị 0, j0) (hay nói cách khác ai0 j0 =
0) thì hàm f đ c xác đ nh nh sau:ượ ị ư
aij ∀ (i, j) n u iế0 = 1
fu(aij) = aij n u (i, j) ế≠ (i0-1, j0) và (i, j) ≠ (i0, j0) và i0 >1
ai0-1, j0 n u (i, j) = (iế0, j0), i0 >1
ai0, j0 n u (i, j) = (iế0-1, j0), i0 >1
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:ư
aij ∀ (i, j) n u iế0 = 3
fd(aij) = aij n u (i, j) ế≠ (i0+1, j0) và (i, j) ≠ (i0, j0) và i0 <3
ai0-1, j0 n u (i, j) = (iế0, j0), i0 <3
ai0, j0 n u (i, j) = (iế0+1, j0), i0 <3
aij ∀ (i, j) n u jế0 = 1
fl(aij) = aij n u (i, j) ế≠ (i0, j0-1) và (i, j) ≠ (i0, j0) và j0 > 1
ai0-1, j0 n u (i, j) = (iế0, j0), j0 > 1
ai0, j0 n u (i, j) = (iế0, j0-1), j0 > 1
aij ∀ (i, j) n u jế0 = 3
fr(aij) = aij n u (i, j) ế≠ (i0, j0+1) và (i, j) ≠ (i0, j0) và j0 < 3
ai0-1, j0 n u (i, j) = (iế0, j0), j0 < 3
ai0, j0 n u (i, j) = (iế0, j0+1), j0 < 3
Ví d 3.ụ Bài toán Tháp Hà N i v i n=3. ộ ớ
M i tr ng thái là m t b ba (i, j, k). Có các tr ng h p nh sau:ỗ ạ ộ ộ ườ ợ ư
- 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)ằ ộ ọ
- Ba đĩa n m trên ba c c phân bi t: (i, j, k)ằ ọ ệ
16