trạng thái (state) và toán
tử (operator).Một giải pháp trình diễn yếu tố tương thích là sử dụng những khái niệm ( state ) và ( operator ) .
Phương pháp xử lý yếu tố 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 xử lý yếu tố nhờ khoảng trống trạng thái .
Mô tả trạng thái
Giải bài toán trong khoảng trống trạng thái, trước hết phải xác lập dạng diễn đạt trạng thái bài toán sao cho bài toán trở nên đơn thuần hơn, tương thích thực chất vật lý của bài toán ( Có thể sử dụng những xâu ký hiệu, véctơ, mảng hai chiều, cây, list ) .Mỗi trạng thái chính là mỗi hình trạng của bài toán, những thực trạng bắt đầu và thực 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ướcCho 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 hoàn toàn 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
đó.Tại mỗi thời gian xác lập, lượng nước hiện có trong mỗi bình phản ánh thực chất hình trạng của bài toán ở thời gian đó .thái của bài toán. Với cách miêu tả như vậy, những trạng thái đặc biệt quan trọng của bài toán sẽ là :– 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 ) hoàn toàn có thể xem là trạng
–
Trạng thái đầu:(0,0)
–
Trạng thái cuối : ( x, k ) hoặc ( k, y ), 0
£
x
£
m, 0
£
y
£
Ví dụ 2 .Bài toán game show 8 sốTrong bảng ô vuông 3 hàng, 3 cột, mỗi ô chứa một số ít nằm trong khoanh vùng 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 đó những số trong bảng, hãy di dời ô trống sang phải, sang trái, lên trên hoặc xuống dưới ( nếu hoàn toàn có thể được ) để đưa về bảng khởi đầu về bảng quy ướ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 triển khai những bước chuyển dời ô trống để đạt được .
Giá trị những thành phần trong bảng xác lập trạng thái bài toán. Vì vậy hoàn toàn có thể diễn đạ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 cuối là ma trận
2-1 số)Có thể phát biểu dạng tổng quát của bài toán này ( Trò chơi n-1 số )
Ví dụ 3 .Bài toán tháp Hà Nội3 sao cho:Cho ba cọc 1, 2, 3. Ở cọc 1 khởi đầu có n đĩa sắp xếp theo thứ tự to dần từ dưới lên trên. Hãy di dời 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 được cho phép đĩa to nằm trên đĩa nhỏ hơn .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:Bài toán xác địnhkhi 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 lập :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 miêu tả trạng thái bài toán không duy nhất, yếu tố là chọn cách diễn đạt nào để đạt được mục tiêu thuận tiện nhất .Theo trên, với cách thứ nhất ta phải dùng 3 list động vì số đĩa trên mỗi cọc là khác nhau trong từng thời gian khác nhau .Cách thứ hai, nhìn qua thì khó miêu 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 diễn đạt bài toán hiệu suất cao 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,
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, { 1 .. n }. Khi đó bộ có thứ tự ( x, x ,. ., x ) hoàn toàn có thể dùng làm dạng diễn đạt trạng thái đang xét của bài toán. Với cách miêu 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 ra là những phép biến hóa đưa từ trạng thái này sang trạng thái khác. Có hai cách dùng để trình diễn những toán tử :
–
Biểu diễn như một hàm xác lập trên tập những trạng thái và nhận giá trị cũng trong tập này .
–
Biểu diễn dưới dạng những quy tắc sản xuất S ? A có nghĩa là nếu có trạng thái S thì hoàn toàn có thể đưa đến trạng thái A .
Ví dụ 1 .Bài toán đong nướcCá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ì những trạng thái tiếp nối hoàn toàn có thể chuyển đến sẽ là :
(m,y)( m, y )(x,n)( x, n )(0,y)( 0, y )(x,0)( x, 0 )(x,y) (0, x+ y) nếu x+y < = n( x, y ) ( 0, x + y ) nếu x + y < = n(x+y
-n,n) nếu x+y > n( x + y – n, n ) nếu x + y > n(x+
y,0) nếu x+y < = m( x + y, 0 ) nếu x + y < = m(m,
x+y-m) nếu x+y > m( m, x + y-m ) nếu x + y > mVí 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 hoàn toàn có thể được .
–
Biểu diễn theo quy tắc sản xuất :
–
Biểu diễn theo một hàmu 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:Gọi hàm flà hàm trình diễn cho toán tử chuyển ô trống lên trên ; gọi B ( B = ( b ) ) là trạng thái sau khi vận động và di chuyển ô trống ở trạng thái A ( A = ( a ) ) lên trên, nghĩa là : B = f ( A ), giả sử ô trống đang ở vị trí ( i, j ) ( hay nói cách khác a = 0 ) thì hàm f được xác lập như sau :
aij
“
nếui0 = 1( i, j ) nếu = 1
fu(aij)=aijnếu(i, j)
¹
( i0-1, j0 ) và ( i, j )
¹
0, j0) và i0 >1( i, j ) và i > 1ai0-1, j0nếu(i, j) = (i0, j0), i0
>1nếu ( i, j ) = ( i, j ), i > 1ai0, j0nếu(i, j) = (i0-1, j0), i0
>1nếu ( i, j ) = ( i-1, j ), i > 1d, qua trái fl, qua phải fr như
sau:Tương tự, hoàn toàn có thể xác lập những phép chuyển ô trống xuống dưới f, qua trái f, qua phải fnhư sau :
aij
“
nếui0 = 3( i, j ) nếu = 3
fd(aij)
=aijnếu(i, j)
¹
( i0 + 1, j0 ) và ( i, j )
¹
0, j0) và i0 <3( i, j ) và i <3ai0-1, j0nếu(i, j) = (i0, j0), i0
<3nếu ( i, j ) = ( i, j ), i <3ai0, j0nếu(i, j) = (i0+1, j0), i0
<3nếu ( i, j ) = ( i + 1, j ), i <3
aij
“
nếuj0 = 1( i, j ) nếu = 1
fl(aij)
=aijnếu(i, j)
¹
( i0, j0-1 ) và ( i, j )
¹
0, j0) và j0 >
1( i, j ) và j > 1ai0-1, j0nếu(i, j) = (i0, j0), j0
> 1nếu ( i, j ) = ( i, j ), j > 1ai0, j0nếu(i, j) = (i0, j0-1), j0
> 1nếu ( i, j ) = ( i, j-1 ), j > 1
aij
“
nếuj0 = 3( i, j ) nếu = 3
fr(aij)
=aijnếu(i, j)
¹
( i0, j0 + 1 ) và ( i, j )
¹
0, j0) và j0 <
3( i, j ) và j < 3ai0-1, j0nếu(i, j) = (i0, j0), j0
< 3nếu ( i, j ) = ( i, j ), j < 3ai0, j0nếu(i, j) = (i0, j0+1), j0
< 3nếu ( i, j ) = ( i, j + 1 ), j < 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ó những 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, i)(i, i, j)( i, i, i ) ( i, i, j )(i,
i, k)( i, i, k )(i,
i, j)(i, i, k)( i, i, j ) ( i, i, k )(i,
k, j)( i, k, j )(i,
i, i)( i, i, i )(i,
j, i)(i, j, k)( i, j, i ) ( i, j, k )
(i,
j, j)( i, j, j )(i,
k, i) ( i, k, i )
(j,
i, i)(j, i, j)( j, i, i ) ( j, i, j )(j,
i, k)( j, i, k )(k,
i, i)( k, i, i )(i,
j, k)(i, i, k)( i, j, k ) ( i, i, k )(i,
j, j)( i, j, j )(i,
j, i)( i, j, i )4. Không gian trạng thái của bài toán .
của bài toán.Không gian trạng thái là tập toàn bộ những trạng thái hoàn toàn có thể có và tập những 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ổng thể những trạng thái hoàn toàn có thể có của bài toánS : trạng thái đầuG : tập những trạng thái đíchF : tập những 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 những thao tác đong đầy, đổ ra hoặc đổ sang bình khác triển khai 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: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)S = ( 1, 1, 1 )G = {(3, 3, 3)}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.F = Tập những năng lực hoàn toàn có thể chuyển đĩa đã xác lập trong phần trước .Ví dụ 3 .Không gian trạng thái của bài toán game show 8 số :T = { (aij)3×3 / 0<= aij
<= 8 và aij <> akl với i<> j hoặc k
<> l}T = { ( a / 0 < = a < = 8 và a < > avới i < > j hoặc k < > l }S = Ma trận xuất phát của bài toán,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)G = Ma trận ở đầu cuối của bài toán ( những số nằm theo vị trí nhu yếu )F = {fl,
fr, fu, fd}F = { f, f, f, fTìm kiếm lời giải trong khoảng trống trạng thái là quy trình tìm kiếm xuất phát từ trạng thái bắt đầu, dựa vào toán tử chuyển trạng thái để xác lập những trạng thái tiếp theo cho đến khi gặp được trạng thái đích .5. Biểu diễn khoảng trống trạng thái dưới dạng đồ thị. Các khái niệm5.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 ) trọn vẹn khác với cung ( j, i ) .Ví dụxét dồ thị
vô hướng G1 và đồ thị có hướng G2xét dồ thị vô hướng Gvà đồ thị có hướng G
 |
| G1 và G2 |
·
Tập đỉnh kề :
“
n
Î
V, T ( n ) = { m
Î
V / ( n, m )
Î
E } được gọi là tập những đỉnh kề của n
·
Đường đi :p = ( n1, …, nk ) được gọi là đường đi từ đỉnh n1
®
nknếu ni
Î
V ,
“
i = 1, k ;
(ni, ni+1)
Î
E
“
i = 1, k – 1
·
Cây là đồ thị có đỉnh gốc n0
Î
Vthỏa :Một đồ thị G = ( V, E ) gọi là cây nếu sống sót một đỉnh n0
Î
Vcó những đặc thù sau :
Ù
Ù
–
“
n
Î
V, n
Î
0), 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)T ( n ), trong đó T ( n ) : tập những đỉnh thuộc dòng dõi của n ( nlà tổ tiên của n )
–
“
n
Î
V ,
USD
!
m
Î
V sao cho n
Î
T ( m ) ; m được gọi là cha của n .5.2. Biểu diễn khoảng trống trạng thái bằng đồ thịthì có cung (s, t)Theo ngôn từ đồ thị, khoảng trống trạng thái tương ứng với một đồ thị khuynh hướng trong đó : Các trạng thái tương ứng với những đỉnh trong đồ thị, nếu sống sót toán tử chuyển trạng tháithì có cung ( s, t )Để thấy rõ mối đối sánh tương quan, ta có bảng sau
| KGTT |
Đồ thị |
| Trạng tháiToán tửDãy những trạng thái liên tục |
ĐỉnhCungĐườ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 để màn biểu diễn đồ thị G tàng 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ị, trong đó:Đồ thị G được trình diễn bởi ma trận kề A = ( a, với n là số đỉnh của đồ thị, trong đó :
aij=1nếu
(i, j)
Î
trong trường hợp ngược lạitrong 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:Với đồ thị vô hướng Gvà đồ thị có hướng Gở trên ta có những ma trận kề sau :
ii ) Biểu diễn bằng list kề .với đồ thị G1, ta có List(1)= [2, 3, 4]Với mỗi đỉnh i của đồ thị, ta có một list toàn bộ những đỉnh kề với i, ta ký hiệu là List ( i ). Để biểu lộ List ( i ) ta hoàn toàn 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)( 0,0 )
(3,0)(0,2)( 3,0 ) ( 0,2 )(1,2)(3,2)(2,0)( 1,2 ) ( 3,2 ) ( 2,0 )(1,0)(0,1)(2,2)( 1,0 ) ( 0,1 ) ( 2,2 )(3,1)( 3,1 )
Ví dụ 2 .Tháp Hà Nội với n = 3
( 111 )
(112)(113)( 112 ) ( 113 )
(123)( 132 ) ( 123 )
(233)(322)( 233 ) ( 322 )
(231)(232)(323)(321)( 231 ) ( 232 ) ( 323 ) ( 321 )(221)(212)(313)(331)( 221 ) ( 212 ) ( 313 ) ( 331 )
(222)(223)(213)(211)(311)(312)(332)(333)
(222)(223)(213)(211)(311)(312)(332)(333)
