Đặ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.
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)
-
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
|
1
|
2
|
3
|
8
|
4
|
|
7
|
6
|
5
|
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 A3*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 đầ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 n2-1 số)
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 xi là cọc chứa đĩa lớn thứ
i, trong đó xiÎ{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.
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à:

(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 fu 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= (aij)) lên trên, nghĩa
là: B= fu(A), giả sử ô trống đang ở vị trí (i0, j0)
(hay nói cách khác ai0 j0 = 0) thì hàm f được xác định như sau:

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) = (i0, j0), i0
>1
ai0, j0 nếu (i, j) = (i0-1, j0), i0
>1
Tương tự, có thể xác định các phép chuyển ô trống
xuống dưới fd, qua trái fl, qua phải fr như
sau:

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) = (i0, j0), i0
<3
ai0, j0 nếu (i, j) = (i0+1, j0), i0
<3

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) = (i0, j0), j0
> 1
ai0, j0 nếu (i, j) = (i0, j0-1), j0
> 1

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) = (i0, j0), j0
< 3
ai0, j0 nếu (i, j) = (i0, 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)

(i,
i, k)
(i,
i, j) (i, i, k)
(i,
k, j)
(i,
i, i)
(i,
j, i) (i, j, k)
(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. Không gian
trạng thái của bài toán.
Không gian trạng
thái là tập tất cả các trạng thái có thể có và tập các toán tử của bài toán.
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ử
Ví dụ 1. Không gian trạng thái của bài toán đong nước là bộ
bốn T, S, G, F xác đinh như sau:
T = { (x,y) / 0
<= x <= m; 0 <= y <= n }
S = (0,0)
G = { (x,k) hoặc (k,y) / 0 <= x <= m; 0 <= y
<= n}
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ÌV*V)
Chú ý
-
G là đồ thị vô
hướ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)
-
Nếu G là đồ thị
có hướng thì cung (i, j) hoàn toàn khác với cung (j, i).
Ví dụ xét dồ thị
vô hướng G1 và đồ thị có hướng 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:
p
= (n1,...,nk) được gọi là đường đi từ đỉnh n1 ®
nk nếu ni ÎV,
"i=1,k ;

·
Cây là đồ thị có
đỉnh gốc n0ÎV thoả:
Một đồ thị G=(V, E) gọi là cây nếu tồn tại một đỉnh
n0ÎV có những tính
chất sau:
Ù Ù
-
"nÎV, nÎT(n0), trong đó T(n0): tập các
đỉnh thuộc dòng dõi của n0 (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ị định hướng trong đó: Các trạng thái
tương ứng với các đỉnh trong đồ thị, nếu tồn tại toán tử chuyển trạng thái thì có cung (s, t)
Để thấy rõ mối tương quan, ta
có bảng sau
KGTT
|
Đồ thị
|
Trạng thái
Toán tử
Dãy
các trạng thái liên tiếp
|
Đỉnh
Cung
Đường
đi
|
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ề
Đồ thị G được biểu diễn bởi ma trận kề
A=(aij)nxn, với n là số đỉnh của đồ thị, trong đó:

0 trong trường hợp ngược lại
Nếu G là đồ thị vô hướng thì ma trận kề A là ma trận
đối xứng.
Ví dụ Với đồ thị
vô hướng G1 và đồ thị có hướng G2 ở trên ta có các ma
trận kề sau:
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]
Ví dụ 1. Bài toán đong nước m=3, n=2, k=1
(0,0)
(3,0) (0,2)
(1,2) (3,2) (2,0)
(1,0) (0,1) (2,2)
(3,1)
Ví dụ 2. Tháp Hà Nội với n = 3
(111)







(221) (212) (313) (331)


Tags
trituenhantao