Chương 2
BIỂU DIỄN VẤN ĐỀ TRONG KHÔNG GIAN TRẠNG THÁI
2.1. Đặt vấn đề
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 đề (bài toán) tìm kiếm, vì thế chúng ta phải có những kỹ thuật tìm kiếm áp dụng để giải quyết các vấn đề (bài toá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.
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.
Như vậ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ươ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ép biến đổi trạng thái].
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.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)
- 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-right, sang trái-left, lên trên-up hoặc xuống dưới-down (nếu có thể được) để đưa bảng ban đầu về bảng qui ước trước.
Chẳng hạn Hình 2.1 trên đây là bảng xuất phát và Hình 2.2 là bảng mà ta phải thực hiện các bước di chuyển ô trống để đạt được.
Hình 2.1 Hình 2.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 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:
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.
Hình 2.3. Bài toán tháp Hà Nội (n=3)
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:
- 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.
- Đĩ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 thì:
- Trạng thái đầu là (1,1,. . .,1)
- Trạng thái cuối là (3,3,. . .,3)
2.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à:
(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 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:
aij " (i, j) nếu i0 = 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) = (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:
aij " (i, j) nếu i0 = 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) = (i0, j0), i0 <3
ai0, j0 nếu (i, j) = (i0+1, j0), i0 <3
aij " (i, j) nếu j0 = 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) = (i0, j0), j0 > 1
ai0, j0 nếu (i, j) = (i0, j0-1), j0 > 1
aij " (i, j) nếu j0 = 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) = (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, 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)
2.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.
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 đề.
2.5. Biểu diễn không gian trạng thái dưới dạng đồ thị
2.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 đồ thị vô hướng G1 và đồ thị có hướng G2
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:
p = (n1,...,nk) được gọi là đường đi từ đỉnh n1 ® nk nếu ni ÎV, "i=1,k
(ni, ni+1)ÎE "i=1, k -1.
· Cây là đồ thị có đỉnh gốc n0ÎVthoả:
Một đồ thị G=(V, E) gọi là cây nếu tồn tại một đỉnh n0ÎVcó 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.
2.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
2.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.
* 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 đó:
aij = 1 nếu (i, j) ÎE
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:
0
1
0
1
1
0
1
1
0
0
0
0
0
0
1
0
0
1
1
1
1
0
1
1
1
1
0
0
1
1
0
0
G1: G2:
* 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)
(112) (113)
(132) (123)
(133) (131) (121) (122)
(233) (322)
(231) (232) (323) (321)
(221) (212) (313) (331)
(222) (223) (213) (211) (311) (312) (332) (333)
Chương 3
CÁC PHƯƠNG PHÁP TÌM KIẾM LỜI GIẢI TRONG
KHÔNG GIAN TRẠNG THÁI
3.1. Đặt vấn đề
Quá trình tìm kiếm lời giải của bài toán được biểu diễn trong không gian trạng thái được xem như quá trình dò tìm trên đồ thị, xuất phát từ trạng thái ban đầu, thông qua các toán tử chuyển trạng thái, lần lượt đến các trạng thái tiếp theo cho đến khi gặp được trạng thái đích hoặc không còn trạng thái nào có thể tiếp tục được nữa.
Khi áp dụng các phương pháp tìm kiếm trong không gian trạng thái, người ta thường quan tâm đến các vấn đề sau:
- Kỹ thuật tìm kiếm lời giải
- Phương pháp luận của việc tìm kiếm
- Chiến lược tìm kiếm
Tuy nhiên, không phải các phương pháp này có thể áp dụng để giải quyết cho tất cả các bài toán phức tạp mà chỉ cho từng lớp bài toán.
Việc chọn chiến lược tìm kiếm cho bài toán cụ thể phụ thuộc nhiều vào các đặc trưng của bài toán.
* 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 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.
- v.v…
* Các chiến lược tìm kiếm có thể phân thành hai loại:
- 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ù cơ bản, đó là tìm kiếm theo bề rộng (chiều rộng) và tìm kiếm theo độ sâu (chiều sâu).
- 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.
Ở tìm kiếm kinh nghiệm 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à chúng được sinh ra.
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.
* Các thủ tục tìm kiếm điển hình bao gồm:
- Tìm kiếm theo chiều rộng (Breadth – First Search)
- Tìm kiếm theo chiều sâu (Depth – First Search)
- Tìm kiếm sâu dần (Depthwise Search)
- Tìm kiếm cực tiểu hoá giá thành (Cost minimization Search).
- Tìm kiếm với tri thức bổ sung (Heuristic Search).
A - TÌM KIẾM MÙ
3.2. Phương pháp tìm kiếm theo chiều rộng
3.2.1. Kỹ thuật tìm kiếm rộng
Kỹ thuật tìm kiếm rông là tìm kiếm trên tất cả các nút của một mức trong không gian bài toán trước khi chuyển sang các nút của mức tiếp theo.
Kỹ thuật tìm kiếm rộng bắt đầu từ mức thứ nhất của không gian bài toán, theo hướng dẫn của luật trọng tài, chẳng hạn “đi từ trái sang phải”. Nếu không thấy lời giải tại mức này, nó chuyển xuống mức sau để tiếp tục … đến khi định vị được lời giải nếu có.
3.2.2. Giải thuật
Input:
Cây/Đồ thị G = (V,E) với đỉnh gốc là n0 (trạng thái đầu)
Tập đích Goals
Output:
Một đường đi p từ n0 đến một đỉnh n* Î Goals
Method:
Sử dụng hai danh sách hoạt động theo nguyên tắc FIFO (queue) MO và DONG
Procedure BrFS; (Breadth First Search)
Begin
Append(MO,no)
DONG=null;
While MO <> null do
n:= Take(MO);
if nÎ DICH then exit;
Append(DONG, n);
For mÎ T(n) and mÏDONG+MO do
Append(MO, m);
end;
Write (‘Không có lời giải’);
End;
Chú ý: Thủ tục Append(MO,n0) bổ sung một phần tử vào queue MO.
Hàm Take(MO) lấy một phần tử trong queue MO.
3.2.3. Đánh giá độ phức tạp của giải thuật tìm kiếm rộng
Giả sử rằng, mỗi trạng thái khi được xét sẽ sinh ra k trạng thái kế tiếp. Khi đó ta gọi k là nhân tố nhánh. Nếu bài toán tìm được nghiệm theo phương pháp tìm kiếm rộng có độ dài d. Như vậy, đỉnh đích sẽ nằm ở mức d, do đó số đỉnh cần xét lớn nhất là:
1 + k + k2 + . . . + kd.
Như vậy độ phức tạp thời gian của giải thuật là O(kd). Độ phức tạp không gian cũng là O(kd), vì tất cả các đỉnh của cây tìm kiếm ở mức d đều phải lưu vào danh sách.
3.2.4. Ưu và nhược điểm của phương pháp tìm kiếm rộng
* Ưu điểm:
· Kỹ thuật tìm kiếm rộng là kỹ thuật vét cạn không gian trạng thái bài toán vì vậy sẽ tìm được lời giải nếu có.
· Đường đi tìm được đi qua ít đỉnh nhất.
· Thuận lợi khi muốn tìm nhiều lời giải.
* Nhược điểm:
· Tìm kiếm lời giải theo thuật toán đã định trước, do vậy tìm kiếm một cách máy móc; khi không có thông tin hổ trợ cho quá trình tìm kiếm, không nhận ra ngay lời giải.
· Không phù hợp với không gian bài oán kích thước lớn. Đối với loại bài toán này, phương pháp tìm rộng đối mặt với các nhu cầu:
- Cần nhiều bộ nhớ theo số nút cần lưu trữ.
- Cần nhiều công sức xử lý các nút, nhất là khi các nhánh cây dài, số nút tăng.
- Dễ thực hiện các thao tác không thích hợp, thừa, đưa đến việc tăng đáng kể số nút phải xử lý.
· Không hiệu qủa nếu lời giải ở sâu. Phương pháp này không phù hợp cho trường hợp có nhiều đường dẫn đến kết quả nhưng đều sâu.
· Giao tiếp với người dùng không thân thiện. Do duyệt qua tất cả các nút, việc tìm kiếm không tập trung vào một chủ đề.
3.2.5. Các ví dụ
Ví dụ 1: Bài toán đong nước với m = 5, n= 4, k =3.
Mức 1: Trạng thái đầu (0;0)
Mức 2: Các trạng thái (5;0), (0;4) Mức 3: (5;4), (1;4), (4,0)
Mức 4: (1;0), (4;4) Mức 5: (0;1), (5;3)
Ở mức 5 ta gặp trạng thái đích là (5;3) vì vậy có được lời giải như sau:
(0;0)® (0;4) ® (4;0) ® (4;4) ® (5;3)
Để có được lời giải này ta phải lưu lại vết của đường đi, có thể trình bày quá trình tìm kiếm dưới dạng bảng sau:
T(i)
MO ¯
DONG
(0;0)
(0;0)
(5;0) (0;4)
(5;0) (0;4)
(0;0)
(5;0)
(5;4) (0;0) (1;4)
(0;4) (5;4) (1;4)
(0;0) (5;0)
(0;4)
(5;4) (0;0) (4;0)
(5;4) (1;4) (4;0)
(0;0) (5;0) (0;4)
(5;4)
(0;4) (5;0)
(1;4) (4;0)
(0;0) (5;0) (0;4) (5;4)
(1;4)
(5;4) (0;4) (1;0) (5;0)
(4;0) (1;0)
(0;0) (5;0) (0;4) (5;4) (1;4)
(4;0)
(5;0) (4;4) (0;0) (0;4)
(1;0) (4;4)
(0;0) (5;0) (0;4) (5;4) (1;4) (4;0)
(1;0)
(5;0) (1;4) (0;1)
(4;4) (0;1)
(0;0) (5;0) (0;4) (5;4) (1;4) (4;0) (1;0)
(4;4)
(5;4) (0;4) (4;0) (5;3)
(0;1) (5;3)
(0;0) (5;0) (0;4) (5;4) (1;4) (4;0) (1;0) (4;4)
(0;1)
(5;1) (0;4) (0;0) (1;0)
(5;3) (5;1)
(0;0) (5;0) (0;4) (5;4) (1;4) (4;0) (1;0) (0;1)
(5;3)
Ta có thể biểu diễn dưới dạng đồ thị sau:
Ví dụ 2: Bài toán trò chơi 8 số.
Bảng xuất phát
2
8
3
1
6
4
7
5
Bảng kết thúc
1
2
3
8
4
7
6
5
Mức 1: Có một trạng thái
2
8
3
1
6
4
7
5
Mức 2: Có ba trạng thái
2
8
3
2
8
3
2
8
3
1
4
1
6
4
1
6
4
7
6
5
7
5
7
5
Mức 3: Có năm trạng thái
2
8
3
2
8
3
2
3
1
4
1
4
1
8
4
7
6
5
7
6
5
7
6
5
2
8
3
2
8
3
6
4
1
6
1
7
5
7
5
4
Mức 4: Có mười trạng thái
8
3
2
8
3
2
1
4
7
1
4
7
6
5
6
5
2
8
2
8
3
1
4
3
1
4
5
1
7
5
7
6
2
3
2
3
1
8
4
1
8
4
7
6
5
7
6
5
8
3
2
8
3
2
6
4
6
4
1
7
5
1
7
5
2
8
2
8
3
1
6
3
1
6
4
7
5
4
7
5
Mức 5: Có 12 trạng thái
1
2
3
2
3
4
8
4
1
8
7
6
5
7
6
5
8
3
2
8
3
2
1
4
7
1
4
7
6
5
6
5
2
8
2
8
3
1
4
3
1
4
5
7
6
5
7
6
8
3
2
3
2
6
4
6
8
4
1
7
5
1
7
5
2
8
3
2
8
6
7
4
1
6
3
1
5
7
5
4
2
3
2
8
3
1
8
3
1
5
6
7
5
4
7
4
Mức 6: Có 24 trạng thái
1
2
3
1
2
3
8
4
7
8
4
7
6
5
6
5
. . .
Ở mức này ta gặp được trạng thái đích
1
2
3
8
4
7
6
5
3.3. Phương pháp tìm kiếm theo chiều sâu
3.3.1. Kỹ thuật tìm kiếm sâu
Tìm kiếm sâu trong không gian bài toán được bắt đầu từ một nút rồi tiếp tục cho đến khi hoặc đến ngõ cụt hoặc đến đích. Tại mỗi nút có luật trong tài, chẳng hạn, “đi theo nút cực trái”, hướng dẫn việc tìm. Nếu không đi tiếp được, gọi là đến ngõ cụt, hệ thống quay lại một mức trên đồ thị và tìm theo hướng khác, chẳng hạn, đến nút “sát nút cực trái”. Hành động này gọi là quay lui.
Thuật toán tìm kiếm theo chiều sâu được hình dung như việc khảo sát một cây bắt đầu từ gốc đi theo mọi cành có thể được, khi gặp cành cụt thì quay lại xét cành chưa đi qua.
- Ở bước tổng quát, giả sử đang xét đỉnh i, khi đó các đỉnh kề với i có các trường hợp:
+ Nếu tồn tại đỉnh j kề i chưa được xét thì xét đỉnh này (nó trở thành đỉnh đã xét) và bắt đầu từ đó tiếp tục quá trình tìm kiếm với đỉnh này..
+ Nếu với mọi đỉnh kề với i đều đã được xét thì i coi như duyệt xong và quay trở lại tìm kiếm từ đỉnh mà từ đó ta đi đến được i.
3.3.2. Giải thuật
Input:
Cây/Đồ thị G = (V,E) với đỉnh gốc là n0 (trạng thái đầu)
Tập đích Goals
Output:
Một đường đi p từ n0 đến một đỉnh n* Î Goals
Method:
Sử dụng hai danh sách hoạt động theo nguyên tắc LIFO (Stack) MO và DONG
Procedure DFS; (Depth First Search)
Begin
Push (MO,no)
DONG=null;
While MO <> null do
n:=pop (MO);
if nÎ DICH then exit;
push (DONG, n);
For mÎ T(n) and mÏDONG+MO do
Push (MO, m);
end;
Write (‘Không có lời giải’);
End;
Chú ý: Thủ tục Push(MO,n0) thực hiện việc bổ sung n0 vào stack MO
Hàm Pop(MO) lấy phần tử đầu tiên trong Stack MO.
3.3.3. Đánh giá độ phức tạp của thuật toán tìm kiếm sâu
Giả sử 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à k. Có thể xảy ra nghiệm là đỉnh cuối cùng được xét ở mức d+1 theo luật trọng tài. Khi đó độ phức tạp thời gian của thuật toán tìm kiếm theo chiều sâu trong trường hợp xấu nhất là O(kd).
Để đánh giá độ phức tạp không gian của thuật toán tìm kiếm sâu ta có nhận xét ràng: Khi xét đỉnh j, ta chỉ cần lưu các đỉnh chưa được xét mà chúng là những đỉnh con của những đỉnh nằm trên đường đi từ đỉnh gốc đến j. Vì vậy chỉ cần lưu tối đa la k*d. Do đó độ phức tạp không gian của thuật toán là O(k*d).
3.3.4. Ưu và nhược điểm của phương pháp tìm kiếm sâu
* Ưu điểm:
· Nếu bài toán có lời giải, phương pháp tìm kiếm sâu bảo đảm tìm ra lời giải.
· Kỹ thuật tìm kiếm sâu tập trung vào đích, con người cảm thấy hài lòng khi các câu hỏi tập trung vào vấn đề chính.
· Do cách tìm của kỹ thuật này, nếu lời giải ở rất sâu, kỹ thuật tìm sâu sẽ tiết kiệm thời gian.
· Thuận lợi khi muốn tìm một lời giải
* Nhược điểm:
· Tìm sâu khai thác không gian bài toán để tìm lời giải theo thuật toán đơn giản một cách cứng nhắc. Trong quá trình tìm nó không có thông tin nào hổ trợ để phát hiện lời giải. Nếu chọn nút ban đầu không thích hợp có thể không dẫn đến đích của bài toán.
· Không phù hợp với không gian bài toán lớn, kỹ thuật tìm kiếm sâu có thể không đến lời giải trong khoảng thời gian vừa phải.
3.3.5. Các ví dụ
Ví dụ 1: Bài toán đong nước với m = 5, n = 4, k = 3.
Chú ý: Nếu ta chọn nhánh ưu tiên đổ đầy bình thứ hai thì sẽ tìm thấy lời giải rất nhanh. Quá trình tìm kiếm có thể trình bày bằng bảng sau.
T(i)
MO ¯
DONG
(0;0)
(0;0)
(5;0) (0;4)
(5;0) (0;4)
(0;0)
(0;4)
(5;4) (0;0) (4;0)
(5;0) (5;4) (4;0)
(0;0) (0;4)
(4;0)
(5;0) (4;4) (0;0) (0;4)
(5;0) (5;4) (4;4)
(0;0) (0;4) (4;0)
(4;4)
(5;4) (0;4) (4;0) (5;3)
(5;0) (5;4) (5;3)
(0;0) (0;4) (4;0) (4;4)
(5;3)
Lời giải tìm được: (0;0) ® (0;4) ® (4;0) ® (4;4) ® (5;3)
Ví dụ 2: Bài toán Tháp Hà nội với n = 3.
Nhắc lại, dùng bộ ba (x1; x2; x3) biểu diễn trạng thái bài toán, với xi là cọc chứa đĩa lớn thứ i.
T(i)
MO ¯
DONG
(1;1;1)
(1;1;1)
(1;1;2) (1;1;3)
(1;1;2) (1;1;3)
(1;1;1)
(1;1;3)
(1;1;1)(1;1;2) (1;2;3)
(1;1;2)(1;2;3)
(1;1;1)(1;1;3)
(1;2;3)
(1;1;3) (1;2;1) (1;2;2)
(1;1;2)(1;2;1)(1;2;2)
(1;1;1)(1;1;3)(1;2;3)
(1;2;2)
(1;2;3) (1;2;1) (3;2;2)
(1;1;2)(1;2;1)(3;2;2)
(1;1;1)(1;1;3)(1;2;3)(1;2;2)
(3;2;2)
(1;2;2) (3;2;3) (3;2;1)
(1;1;2)(1;2;1)(3;2;1)
(1;1;1)(1;1;3)(1;2;3)(1;2;2) (3;2;2)
(3;2;1)
(3;2;2) (3;2;3) (3;3;1)
(1;1;2)(1;2;1)(3;3;1)
(1;1;1)(1;1;3)(1;2;3)(1;2;2) (3;2;2) (3;2;1)
(3;3;1)
(3;2;1) (3;3;2) (3;3;3)
(1;1;2)(1;2;1)(3;3;3)
(1;1;1)(1;1;3)(1;2;3)(1;2;2) (3;2;2) (3;2;1) (3;3;1)
(3;3;3)
Lời giải của bài toán:
(1;1;1) ® (1;1;3) ® (1;2;3) ® (1;2;2) ® (3;2;2) ® (3;2;1) ® (3;3;1) ® (3;3;3)
Cả hai ví dụ trên, chúng ta đều thấy, tìm kiếm theo chiều sâu đều cho lời giải tốt và nhanh.
Ví dụ 3: Bài toán tìm dãy hợp lý với số hạng đầu a1 = 26
Nhắc lại: Dãy a1, a2, …,an được gọi là hợp lý nếu thoả hai điều kiện:
- an là số nguyên tố
- ak+1 = ak+1 hoặc 2*ak
Như vậy, khi biết ak thì ta xác định được ak+1. Vì vậy có thể mô tả trạng thái bài toán tương ứng với giá trj ak tại thòi điểm đang xét. Ta có thể chỉ ra một cách tìm kiếm theo chiều sâu như sau
I
T(i)
MO ¯
DONG
26
26
27 52
27 52
26
52
53 104
27 53 104
26 52
104
105 208
27 53 105 208
26 52 104
208
209 416
27 53 105 209 416
26 52 104 208
. . .
Với cách tìm kiếm theo theo thuật toán một cách máy móc như vậy thì rõ ràng không bao giờ đạt được đích. Trong khi chúng ta dễ dàng nhận được lời giải, chăng hạn:
a1 = 26; a2 = 52; a3 = 53. Như vậy n =3.
3.4. Phương pháp tìm kiếm theo chiều sâu dần
3.4.1. Kỹ thuật tìm kiếm sâu dần
Kỹ thuật tìm kiếm sâu dần là thực hiện việc tìm kiếm với độ sâu ở mức giưói hạn 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,...đến độ sâu max nào đó.
Kỹ thuật tìm kiếm sâu dần thường được thực hiện khi cây tìm kiếm chứa nhánh vô hạn, và nếu sử dụng tìm kiếm theo độ sâu ta có thể mắc kẹt ở một nhánh nào đó (thuật toán không dừng) và không tìm ra nghiệm.
n0
d
3.4.2. Giải thuật
Thuật toán tìm kiếm sâu dần sử dụng thuật toán tìm kiếm sâu hạn chế như thủ tục con. Đó là thủ tục tìm kiếm theo chiều sâu nhưng chỉ tới độ sâu d nào đó rồi quay lên.
Thủ tục tìm kiếm sâu hạn chế (depth_limitedsearch)
Procedure Depth_limited_search(d); {d là tham số độ sâu}
Begin
Push (MO,no);
Depth(n0)=0; {hàm depth ghi lại độ sâu mỗi đỉnh}
DONG=null;
While MO <> null do
n:=pop (MO);
if nÎ DICH then exit;
push (DONG, n);
if depth(n)<=d then
For mÎ T(n) and mÏDONG do
Push (MO, m);
depth(m)=depth(n)+1;
end;
end;
Write (‘Không có lời giải’);
End;
Thuật toán tìm kiếm sâu dần (Depth_deepening_search) sẽ sử dụng thủ tục tìm kiếm sâu hạn chế như thủ tục con:
Procedure Depth_deepening_search;
Begin
For d:=0 to max do
Depth_limited_search(d);
If thành công then exit;
End;
3.4.3. Nhận xét
- Luôn tìm ra nghiệm (nếu bài toán có nghiệm), miễn là chọn max đủ lớn (giống như tìm kiếm theo chiều rộng).
- Có độ phức tạp thời gian là O(kd) (giống tìm kiếm rộng).
- Có độ phức tạp không gian là O(k*d) (giống tìm kiếm sâu).
- Giải thuật tìm kiếm sâu dần thường áp dụng cho các bài toán có không gian trạng thái lớn và độ sâu của nghiệm không biết trước.
B - TÌM KIẾM KINH NGHIỆM VÀ TỐI ƯU
(Tìm kiếm heuristic)
Kỹ thuật tìm kiếm mù là phương pháp cơ bản để khai thác không gian bài toán. Chúng đều vét cạn không gian để tìm ra lời giải theo thủ tục xác định trước. Mặc dù có sử dụng tri thức về trạng thái của bài toán để hướng dẫn tìm kiếm nhưng không phổ biến, kém hiệu quả và trong nhiều trường hợp không thể áp dụng được .
Như vậy, chúng ta sẽ nghiên cứu các phương pháp tìm kiếm kinh nghiệm (tìm kiếm heuristic), đó là các phương pháp sử dụng hàm đánh giá để hướng dẫn sự tìm kiếm.
* Hàm đánh giá và tìm kiếm kinh nghiệm:
Trong nhiều vấn đề, ta có thể sử dụng kinh nghiệm, tri thức của chúng ta về vấn đề đó để đánh giá các trạng thái của vấn đề.
Với mỗi trạng thái u, ta sẽ xác dịnh một giá trị số h(u), số này đánh giá “sự gần đích” của trạng thái u. Hàm h(u) được gọi là hàm đánh giá.
Phương pháp tìm kiếm kinh nghiệm là phương pháp tìm kiếm có sử dụng đến hàm đánh giá.
Trong quá trình tìm kiếm, tại mỗi bước ta sẽ chọn trạng thái để phát triển là trạng thái có giá trị hàm đánh giá nhỏ nhất, trạng thái này được xem là trạng thái có nhiều hứa hẹn nhất hướng tới đích.
Quá trình tìm kiếm trong không gian trạng thái có sử dụng hàm đánh giá bao gồm các bước cơ bản sau:
- Biểu diễn thích hợp các trạng thái và các toán tử chuyển trạng thái
- Xây dựng hàm đánh giá
- Thiết kế chiến lược chọn trạng thái ở mỗi bước
Hàm đánh giá
Trong tìm kiếm kinh nghiệm, hàm đánh giá đóng vai trò cực kỳ quan trọng. Chúng ta có xây dựng được hàm đánh giá cho ta sự đánh giá đúng các trạng thái thì tìm kiếm mới hiệu quả.
Nếu hàm đánh giá không chính xác, nó có thể dẫn ta đi chệch hướng và do đó tìm kiếm kém hiệu quả.
Hàm đánh giá được xây dựng tùy thuộc vào vấn đề. Sau đây là một số ví dụ về hàm đánh giá:
Ví dụ 1: Trong bài toán tìm kiếm đường đi trên bản đồ giao thông, ta có thể lấy độ dài của đường chim bay từ một thành phố tới một thành phố đích làm giá trị của hàm đánh giá.
Ví dụ 2: Bài toán 8 số.
Chúng ta có thể đưa ra hai cách xây dựng hàm đánh giá.
- Hàm h1: Với mỗi trạng thái u thì h1(u) là số quân không nằm đúng vị trí của nó trong trạng thái đích, thì h1(u) = 4, vì các quân không đúng vị trí là 3, 8, 6 và 1.
- Hàm h2: Gọi h2(u) là là tổng khoảng cách giữa vị trí của các quân trong trạng thái u và vị trí của nó trong trạng thái đích (khoảng cách được hiểu là số lần dịch chuyển ít nhất theo hàng hoặc cột để đưa một quân ở vị trí của hiện tại tới trạng thái đích).
Ta có: h2(u)=2+3+1+3= 9 (vì quân 3 cần ít nhất 2 dịch chuyển, quân 8 cần ít nhất 3 dịch chuyển, quân 6 cần ít nhất 1 dịch chuyển và quân 1 cần ít nhất 3 dịch chuyển).
Tìm kiếm kinh nghiệm
Hai chiến lược tìm kiếm kinh nghiệm quan trọng nhất là tìm kiếm tốt nhất - đầu tiên (Best-First Search) và tìm kiếm leo đồi (Hill-Climbing Search). Có thể xác định các chiến lược này như sau:
- Tìm kiếm tốt nhất đầu tiên = Tìm kiếm theo bề rộng + Hàm đánh giá
- Tìm kiếm leo đồi = Tìm kiếm theo độ sâu + Hàm đánh giá
3.5. Kỹ thuật tìm kiếm tốt nhất đầu tiên (Best First Search)
3.5.1. Kỹ thuật tìm kiếm tốt nhất đầu tiên
Sử dụng hàm đánh giá để hướng dẫn việc tìm kiếm. Hàm này dùng các thông tin hiện tại về mức độ quan trọng của bài toán tại nút đó để gán giá trị cho nút này, gọi là trọng số của nút. Giá trị này được xem xét trong lúc tìm kiếm. Thông thường, nút có trọng số nhỏ (lớn) nhất sẽ được chọn trong quá trình tìm kiếm.
Tìm kiếm tốt nhất đầu tiên khác với tìm kiếm theo chiều rộng ở chỗ:
- Trong tìm kiếm theo chiều rộng ta lần lượt phát triển tất cả các nút ở mức hiện tại để sinh ra các nút ở mức tiếp theo.
- Còn trong tìm kiếm tốt nhất đầu tiên ta chọn nút để phát triển là nút tốt nhất được xác định bởi hàm đánh giá (tức là nút có có trọng số nhỏ (lớn) nhất sẽ được chọn), nút này có thể ở mức hiện tại hoặc ở các mức trên.
3.5.2. Ưu và nhược điểm của phương pháp tìm kiếm tốt nhất đầu tiên
* Ưu điểm:
- Phương pháp tìm kiếm tốt nhất đầu tiên tổ hợp các ưu điểm của phương pháp tìm kiếm rộng và tìm kiếm sâu.
- Ưu điểm chủ yếu của phương pháp tìm kiếm tốt nhất đầu tiên là dùng tri thức để dẫn dắt việc tìm kiếm. Tri thức này giúp người ta bắt đầu từ đâu là tốt nhất và cách tốt nhất để tiến hành tìm lời giải.
- Tìm kiếm tốt nhất đầu tiên tuân theo cách suy lý của một chuyên gia. Do đó có thể thấy rõ đường đi hơn tìm kiếm rộng và tìm kiếm sâu.
* Nhược điểm:
- Quá trình tìm kiếm có thể đi xa khỏi lời giải. Kỹ thuật này chỉ xét một phần của không gian và coi đó là phần hứa hẹn hơn cả.
3.5.3. Giải thuật
Dữ liệu tương tự như giải thuật tìm kiếm rộng và sâu, sử dụng danh sách MO để lưu các đỉnh sẽ xét.
Procedure BFS; {Best First Search}
Begin
Push(MO,n0);
while MO <> null do
i := Pop(MO);
if i Î Goals then
exit;
for j Î T(i) do
Push(MO,j);
Sort(MO); {theo thứ tự của hàm đánh giá}
end;
write(‘Khong co loi giai’);
end;
3.5.4. Ví dụ
Xét không gian trạng thái được biểu diễn bởi đồ thị trong hình sau, trong đó trạng thái ban đầu là A, trạng thái kết thúc là B. Giá trị của hàm đánh giá là các trọng số ghi cạnh mỗi nút.
* Quá trình tìm kiếm tốt nhất đầu tiên diễn ra như sau:
- Đầu tiên phát triển nút A sinh ra các nút kề là C, D và E. Trong ba nút này, nút D có giá trị hàm đánh giá nhỏ nhất, nó được chọn để phát triển và sinh ra F, I.
- Trong số các nút chưa được phát triển C, E, F, I thì nút E có giá trị đánh giá nhỏ nhất, nó được chọn để phát triển và sinh ra các đỉnh G, K.
- Trong số các nút chưa được phát triển thì G tốt nhất, phát triển G sinh ra B, H. Đến đây ta đã đạt tới trạng thái kết thúc.
Kết quả:
3.6. Phương pháp tìm kiếm leo đồi (Hill-Climbing Search)
3.6.1. Kỹ thuật tìm kiếm leo đồi
Tìm kiếm leo đồi là tìm kiếm theo độ sâu được hướng dẫn bởi hàm đánh giá.
Song khác với tìm kiếm theo độ sâu, khi phát triển một đỉnh u thì bước tiếp theo ta chọn trong số các đỉnh con của u, đỉnh có hứa hẹn nhiều nhất để phát triển, đỉnh này được xác định bởi hàm đánh giá.
3.6.2. Nhận xét phương pháp tìm kiếm leo đồi
Phương pháp tìm kiếm leo đồi chú trọng tìm hướng đi dễ dẫn đến trạng thái đích nhất. Vấn đề quan trọng là biết khai thác khéo léo thông tin phản hồi để xác định hướng đi tiếp và đẩy nhanh quá trình tìm kiếm.
Thông thường ta gán mỗi trạng thái của bài toán với một số đo (hàm đánh giá) nào đó nhằm đánh giá mức độ gần đích của nó. Điều đó có nghĩa là nếu trạng thái hiện thời là u thì trạng thái v sẽ được phát triển tiếp theo nếu v kề với u và hàm đánh giá của v đạt giá trị max (hoặc min).
Tuy nhiên phương pháp này không được cải thiện so với các phương pháp khác trong một số trường hợp sau:
- Cực trị địa phương: nút đang xét tốt hơn các nút lân cận, nhưng đó không phải là phương án tốt nhất trong toàn thể, ví vậy có thể phải quay lui về nút trước để đi theo hướng khác. Giải pháp này đòi hỏi ghi nhớ lại nhiều đường đi.
- Cao nguyên bằng phẳng: Các giá trị của các phương án như nhau, không xác định được ngay hướng nào là tốt hơn trong vùng lân cận.
3.6.3. Giải thuật
Input:
Đồ thị G = (V,E), đỉnh xuất phát n0.
Hàm đánh giá h(n) đối với mỗi đỉnh n.
Tập đỉnh đích DICH.
Output:
Đường đi từ đỉnh n0 đến DICH.
Procedure HLC; {Hill Climbing Search}
Push(MO,n0);
while MO <> null do
i = Pop(MO);
if T(i) Ç DICH <> null then
L:= null;
for j Î T(i) do
if j chưa xét then
đưa j vào danh sách L
sắp xếp L theo thứ tự hàm đánh giá;
chuyển danh sách L vào đầu danh sách MO;
end;
write(‘Khong co loi giai’);
end;
Dữ liệu tương tự như giải thuật tìm kiếm sâu, sử dụng danh sách MO để lưu các đỉnh sẽ xét.
3.6.4. Các ví dụ
Ví dụ 1: Xét không gian trạng thái được biểu diễn bởi đồ thị trong hình sau, trong đó trạng thái ban đầu là A, trạng thái kết thúc là B. Giá trị của hàm đánh giá là các trọng số ghi cạnh mỗi nút.
* Quá trình tìm kiếm leo đồi diễn ra như sau:
Đầu tiên phát triển đỉnh A sinh ra các đỉnh con C, D, E. Trong các đỉnh này chọn D để phát triển, và nó sinh ra các đỉnh con B, G. Quá trình tìm kiếm kết thúc. Cây tìm kiếm leo đồi được cho trong hình dưới đây:
Ví dụ 2: Bài toán trò chơi 8 số
Trạng thái được chọn đi tiếp ở hướng mũi tên.
Ở mức 3 chúng ta thấy có hai trạng thái cùng giá trị hàm đánh giá (h = 3). Đây là trương hợp “cao nguyên băng phẳng” như nhận xét trên, nếu ta chọn phương án kia thì chắc chắn quá trình tìm kiếm sẽ khác đi nhiều.
Minh hoạ cây tìm kiếm cho trò chơi này theo giải thuật leo đồi với hướng chọn như sau:
2
8
3
1
6
4
7
5
h(u) = 4
2
8
3
2
8
3
2
8
3
1
6
4
1
4
1
6
4
7
5
7
6
5
7
5
h(u) = 5 h(u) = 3 h(u) = 5
2
8
3
2
3
2
8
3
1
4
1
8
4
1
4
7
6
5
7
6
5
7
6
5
h(u) = 3 h(u) = 3 h(u) = 4
2
3
2
3
1
8
4
1
8
4
7
6
5
7
6
5
h(u) = 2 h(u) = 4
1
2
3
8
4
7
6
5
h(u) = 1
1
2
3
8
4
7
6
5
3.7. Tìm kiếm đường đi có giá thành cực tiểu - Thuật giải AT
3.7.1. Đặt vấn đề
Cho đồ thị G= (V, E) biểu diễn bài toán với đỉnh xuất phát n0 và tập đích DICH xác định.
Với mỗi phép chuyển trạng thái ni®ni+1 tốn chi phí c(ni, ni+1 ) ký hiệu c(u) với u= (ni, ni+1)ÎE
c(u)
ni ni+1
* Vấn đề:
Tìm đường đi p: n0 n* Î DICH sao cho
(Giá của đường đi là tổng giá các cung tham gia vào đường đi và vấn đề là tìm đường đi có giá min).
Chẳng hạn trong bài toán tìm đường đi trong bản đồ giao thông, giá của cung (i,j) chính là độ dài của đường nối thành phố i với thành phố j. Độ dài đường đi được xác định là tổng độ dài các cung trên đường đi. Vấn đề đặt ra là tìm đường đi ngắn nhất từ trạng thái ban đầu đến trạng thái đích.
* Phương pháp giải
- Nếu thì Þ Dùng phương pháp tìm kiếm theo chiều rộng.
- Gọi g(n) là giá của đường đi cực tiểu từ đỉnh n0 đến n, khi đó bài toán có thể phát biểu như sau:
* Tìm đường đi từ đỉnh sao cho:
Lúc đó, ta có:
Dùng 2 danh sách MO, DONG như trên. Tại mỗi thời điểm chọn đỉnh n trong MO ra xét là đỉnh thoả.
3.7.2. Thuật giải AT
Input:
Đồ thị G = (V,E), Đỉnh xuất phát n0
Hàm chi phí c: E ® R+
c(i,j): xác định chi phí chuyển từ đỉnh i sang đỉnh j với (i,j) Î E
Tập các đỉnh đích DICH
Output:
Đường đi từ đỉnh n0 đến đỉnh n* Î DICH sao cho g(n*) = c(p) = min{g(n)| nÎDICH}.
Procedure AT;
{ Dùng g0(n) là chi phí cực tiểu của đường đi từ đỉnh xuất phát đến đỉnh n tại thời điểm đang xét và xem như hàm g}
Begin
g(n0):= 0;
push(MO, n0);
while MO<>null do
if nÎDICH then
exit {xay dung duong di cuc tieu}
push(DONG, n);
if T(n) <>null then
for mÎT(n) do
if mÏMO+DONG then
push(MO,m);
g(m):=g(n)+c(n,m);
cha(m):=n;
end
else
if g(m) >g(n)+c(n,m) then
g(m):=g(n)+c(n,m);
cha(m):=n;
end;
end;
writeln(‘khong co duong di’);
End;
3.7.3. Các ví dụ
Ví dụ 1:
A
n0=A
DICH={F,K} B C D
E F G H I
K
Có thể trình bày quá trình tìm kiếm bằng bảng dưới đây. Ký hiệu giá trị g(n) là chỉ số dưới tương ứng đỉnh n: ng(n)
T(i)
MO
DONG
A0
A
B C D
B8 C4 D5
A
C
G
B8 D5 G5
A C
D
H I
B8 G5 H14 I6
A C D
G
B8 H14 I6
A C D G
I
K
B8 H14 K8
A C D G I
B
E F
H14 K8 E10 F11
A C D G I B
K
Lời giải của bài toán là A ® D ® I ® K và chi phí của đường đi tìm được là 8
Ví dụ 2:
n0 = A; DICH = {G}
A
B C D E G
F
T(i)
MO
DONG
A0
A
B C D
B5 C3 D6
A
C
A B E F D
B4 D6 E7 F11
A C
B
A C E
D6 E7 F11
A C B
D
A C F G
E7 F9 G15
A C B D
E
B C F
F9 G15
A C B D E
F
C D E G
G14
A C B D E F
G
Đường đi tìm được p: A ® D ® F ® G. Chi phí của đường đi là 14.
Ví dụ 3: Bài toán Tháp Hà Nội - với chi phí chuyển đĩa như sau:
Chi phí chuyển đĩa nhỏ giữa 2 cọc gần 1
Chi phí chuyển đĩa nhỏ giữa 2 cọc xa 3
Chi phí chuyển đĩa vừa giữa 2 cọc gần 2
Chi phí chuyển đĩa vừa giữa 2 cọc xa 5
Chi phí chuyển đĩa lớn giữa 2 cọc gần 4
Chi phí chuyển đĩa lớn giữa 2 cọc xa 8
Xuất phát từ đỉnh (1,1,1), ta có g(1,1,1) = 0.
Khi xét đỉnh (1,1,1) ta có các đỉnh kề và chi phí tương ứng :
g(1,1,2) = 1; g(1,1,3) = 3; như vậy đỉnh (1,1,2) được chọn
Các đỉnh kề của (1,1,2) có giá trị hàm g:
g(1,1,3) = 2 (ở đây giá của đỉnh (1,1,3) được tính lại); g(1,3,2) = 5; chọn đỉnh (1,1,3), ta lại tính tiếp giá trị hàm g của các đỉnh kề với đỉnh này:
g(1,2,3) = 2; lại chọn đỉnh (1,2,3); chi phí của các đỉnh kề với nó:
g(1,2,1) = 2 + 3 = 5; g(1,2,2) = 2 + 1 = 3; chọn đỉnh (1,2,2)
g(1,2,1) = 3 +1 = 4 (được tính lại); g(3,2,2) = 3 + 8 = 11, chọn đỉnh (1,2,1)
Cứ tiếp tục như vậy cho đến khi xét đỉnh (3,3,3).
3.8. Tìm kiếm đường đi cực tiểu - Thuật giải A*
3.8.1. Đặt vấn đề
Đối với nhiều bài toán, việc tìm kiếm đường đi cực tiểu sẽ được định hướng tập trung xung quanh đường đi tốt nhất, nếu sử dụng các thông tin đặc tả về bài toán gọi là các heuristic.
Đối với việc tìm kiếm đường đi với chi phí cực tiểu, người ta sử dụng hàm đánh giá heuristic như sau:
- Gọi g(n): giá cực tiểu đường đi từ n0®n. Tại đỉnh n, g(n) xác định được.
- Gọi h(n): giá cực tiểu đường đi từ n®DICH, h(n) không xác định được Þ người ta tìm cách ước lượng giá trị này.
Để làm giảm không gian tìm kiếm ta dựa vào heuristic để ước lượng giá trị các nút.
Đặt f0(n)=g0(n)+h0(n): dự đoán chi phí cực tiểu của đường đi từ n0®DICH có đi qua đỉnh n.
Trong đó:
+ g0(n) là chi phí của đường đi từ đỉnh xuất phát đến đỉnh n tại thời điểm đang xét(hay là giá trị ước lượng dựa trên sự khai thác thông tin kinh nghiệm quá khứ).
+ h0(n) là ước lượng (dự đoán) chi phí đường đi từ đỉnh n đến đích (hay là giá trị ước lượng dựa trên sự khai thác thông tin của nút hướng tới tương lai). Việc chọn giá trị xấp xỉ h0(n) của h(n) không có một phương pháp tổng quát và được xem như một nghệ thuật, giá trị này sẽ do các chuyên gia đưa ra.
Chỉ số “0” ám chỉ đây là giá trị ước lượng chứ không phải giá trị chính xác. Giá trị chính xác chỉ biết được khi ta đến đích tức giải xong bài toán.
Ta chú ý h0(n) càng lớn thì càng tốt, tức là khai thác nhiều thông tin về trạng thái hiện tại hướng tới tương lai.
Tuy nhiên người ta CM được rằng thuật toán A* chắc chắn dừng khi h0(n) <= h(n) (h0=h: phương án tốt nhất, h0=0: phương án tồi nhất).
Lúc này giải thuật tìm kiếm cực tiểu sẽ thay việc xét hàm g (như đã biết mục trước) bởi hàm f.
3.8.2. Thuật giải A*
Input:
Đồ thị G = (V,E), Đỉnh xuất phát n0
Hàm chi phí c: E ® R+
c(i,j): xác định chi phí chuyển từ đỉnh i sang đỉnh j với (i,j) Î E
h: V ® R+; h(n) xác định dự đoán chi phí tối ưu của đường đi từ đỉnh n đến đích. (ký hiệu h thay cho h0, (tương tự g))
Tập các đỉnh đích DICH
Output:
Đường đi từ đỉnh n0 đến đỉnh n* Î DICH
Procedure A* ;
Begin
g(n0):= 0;
push(MO, n0);
while MO<>null do
if nÎDICH then
exit {xay dung duong di cuc tieu}
push(DONG, n);
if T(n) <>null then
for mÎT(n) do
if mÏMO+DONG then
push(MO,m);
tính f(m);
cha(m):=n;
end
else
if fmới(m) > fcũ(n) then
f(m):= fmới(m);
cha(m):=n;
end;
end;
writeln(‘khong co duong di’);
End;
3.8.3. Các ví dụ
Ví dụ 1:
Trạng thái ban đầu là trạng thái A, trạng thái đích là B, các số ghi cạnh các cung là độ dài đường đi, các số cạnh các đỉnh là giá trị của hàm h
Đầu tiên, phát triển đỉnh A sinh ra các đỉnh con C, D, E và F. Tính giá trị của hàm f tại các đỉnh này ta có:
g(C) = 9, f(C) = 9 + 15 = 24, g(D) = 7, f(D) = 7 + 6 = 13
g(E) = 13, f(E) = 13 + 8 = 21, g(F) = 20, f(F) = 20 +7 = 27
Như vậy đỉnh tốt nhất là D (vì f(D) = 13 là nhỏ nhất). Phát triển D, ta nhận được các đỉnh con H và E. Ta đánh giá H và E (mới):
g(H) = g(D) + Độ dài cung (D, H) = 7 + 8 = 15, f(H) = 15 + 10 = 25.
Đường đi tới E qua D có độ dài:
g(E) = g(D) + Độ dài cung (D, E) = 7 + 4 = 11.
Vậy đỉnh E mới có đánh giá là f(E) = g(E) + h(E) = 11 + 8 = 19.
Trong số các đỉnh cho phát triển, thì đỉnh E với đánh giá f(E) = 19 là đỉnh tốt nhất. Phát triển đỉnh này, ta nhận được các đỉnh con của nó là K và I.
Chúng ta tiếp tục quá trình trên cho tới khi đỉnh được chọn để phát triển là đỉnh kết thúc B, độ dài đường đi ngắn nhất tới B là g(B) = 19. Quá trình tìm kiếm trên được mô tả bởi cây tìm kiếm sau, trong đó các số cạnh các đỉnh là các giá trị của hàm đánh giá f.
KL: A à D à E à I à B
Ví dụ 2: Cho đồ thị biểu diễn bài toán và giá trị dự đoán h0 như sau:
n A B C D E F G H
h0(n) 14 10 10 5 5 4 4 0
A
B D
C
E
F
G
H
Tìm đường đi từ đỉnh a đến đỉnh H.
Trước tiên đỉnh A được đưa vào danh sách MO
g(A) = 0; h(A) = 14; f(A) = 14
Xét đỉnh A, (đưa A vào danh sách DONG) ta có các đỉnh kề B, C, D:
g(B) = 5; f(B) = 15; g(C) = 3; f(C) = 13; g(D) = 7; f(D) = 12 à chọn đỉnh D.
Xét đỉnh D (đưa D vào danh sách DONG) có các đỉnh kề A, C, E. Đỉnh A đã ở trong danh sách DONG, ta tính lại f(C) và tính f(E):
f(C) không thay đổi; f(E) = g(D) +c(D,E) + H(E) = 7 + 6 + 5 = 18; f(E) = 18, chọn đỉnh C, có các đỉnh kề A, D, E.
Tính lại f(E) = 12, chọn E. Các đỉnh kề của E là C, D, F, G.
Tính f(F) = 14; f(G) = 16, chọn F. Các đỉnh kề của F là E, G, B và f(B), f(G) không đổi, chọn B. Các đỉnh kề của B là F, H. f(H) = 17, chọn G. Tính lại f(H) = 15 và dừng.
Đường đi tìm được là p: A à C à E à G à H với chi phí đường đi là 15.
Ví dụ 3: Cho 1 bình dung tích 4 lít, 1 bình dung tích 3 lít. Làm thế nào để bình 4 có 2 lít.
Bài toán trở thành (4,3) (2,y)
Cho h: độ lệch của mức nước hiện có trong bình 4lít so với đích (2lít).
g: là độ dài mức đường đi từ nút gốc tới n
Ta có thể biểu diễn dưới dạng đồ thị sau:
3.9. Phương pháp sinh và thử
Chiến lược này đơn giản, gồm ba bước:
- Trước hết tạo ra một giải pháp. Trong vài bài toán cụ thể đó là việc chọn một lời giải trong không gian các lời giải hay tạo ra một đường đi.
- Thứ hai, thử xem lời giải đó có thích hợp không bằng cách so sánh phương án khác hay so sanh với điểm cuối cần suy diễn.
- Tiếp theo, nếu lời giải đạt được thì dừng, ngước lại, lặp lại từ bước đầu với nút khác.
Với phương pháp này nếu bài toán có lời giải thì sẽ đưa đến đích. Tuy nhiên kích thước bài toán lớn sẽ tăng khối lượng tính toán. Việc tạo lời giải ban đầu có thể thực hiện ngẫu nhiên, và cũng hy vọng ngẫu nhiên mà đạt được lời giải, bởi vậy, không thể không tính đến chỉ một vài hướng đi được cảm nhận là tốt, và loại trừ trước các hướng không dẫn đến lời giải.
Ví dụ 1: Tìm số có 6 chữ số mà tổng bình phương các chữ số chia hết cho3.
Giai đoạn sinh: tạo ra số có 6 chữ số và ta gọi các chữ số từ trái qua phải lần lượt là a, b, c, d, e, f thì 0 < a <= 9 , 0 <= b, c, d, e, f <= 9.
Giai đoạn thử: nểu a*a + b*b + c*c + d*d + e*e + f*f chia hết cho 3 thì chon, ngược lại, tạo ra số khác.
Ví dụ 2: Một bệnh nhân có một vài triệu chứng, chẳng hạn: sốt cao về buổi chiều, ho và mệt mỏi ,…. Bác sĩ có chẩn đoán nghi bị lao phổi, người ta sẽ cho làm ngay xét nghiệm, nếu đúng là dương tính thì kết luận và điều trị bệnh lao phổi, ngược lai, bắt buộc bác sĩ phải chuyển hướng suy nghĩ sang một bệnh khác, v.v…
3.10. Phương pháp thoả mãn ràng buộc
Phương pháp thoả mãn ràng buộc hỗ trợ cho phương pháp sinh và thử, khi chú ý tới một số ràng buộc áp đặt lên các nút trong không gian bài toán. Mục đích đặt ra là xác định đường đi trong đồ thị không gian bài toán, đường đi từ trạng thái đầu đến trạng thái cuối đáp ứng một vài ràng buộc nào đó. Do vậy quá trình tìm kiếm lời giải bao gồm hai phần liên quan chặt chẽ với nhau:
- Tìm kiếm trong không gian các ràng buộc.
- Tìm kiếm trong không gian các bài toán ban đầu.
Nội dung của phương pháp như sau: Thực hiện các bước từ a) đến e) dưới đây cho đến khi tìm được lời giải đày đủ của bài toán hoặc tất cả các đương đều đã duyệt qua nhưng không cho kết quả.
a) Chọn một đỉnh chưa được xét trong đồ thị tìm kiếm.
b) Áp dụng các luật suy diễn trên các ràng buộc đối với đỉnh đã chọn để tạo ra tập các ràng buộc mới.
c) Nếu tập các ràng buộc mới có mâu thuẫn thì đưa ra thông báo đường đi hện thời tới nút đang xét dẫn tới bế tắc.
d) Nếu tập ràng buộc mô tả lời giải đầy đủ của bài toán thì dừng và đưa ra thông báo thành công. Ngược lai, sang bước sau.
e) Áp dụng các luật biến đổi không gian trạng thái tương ứng để tạo ra lời giải bộ phận, tương hợp với tập các ràng buộc hiện thời. Thêm các lời giải bộ phận này vào đồ thị tìm kiếm.
* Ví dụ: Xét bài toán điền các chữ số phân biệt thay cho các chữ cái S, E, N, D, M, O, R, Y sao cho phép cộng sau là đúng:
SEND
MORE
MONEY
Các ràng buộc ban đầu:
- Các chữ cái khác nhau không nhận cùng một giá trị.
- Các ràng buộc số học (cộng có nhớ hoặc không có nhớ.
Giải
Gọi C1, C2, C3, C4 lần lượt lá số nhớ của các cột từ phải sang trái. Khi đó ta xây dựng các ràng buộc cụ thể như sau:
E, N, D,O, R, Y thuộc tập {0 ..9} (1)
S, M thuộc tập {1..9} (2)
C1, C2, C3, C4 thuộc tập {0,1} (3)
D + E = Y + 10*C1 (4)
N + R + C1 = E + 10*C2 (5)
E + O + C2 = N + 10*C3 (6)
S + M + C3 = O + 10*C4 (7)
M = C4 (8)
Từ ràng buộc (2) (3) và (8) suy ra M = 1 và C4=1(9)
Từ ràng buộc (7) và (9) suy ra S +C3 = O + 9, lúc này có hai phương án để lựa chọn:
Phương án 1:
C3 = 0, khi đó ta có S = O + 9, như vậy S = 9 và O = 0 (10-1)
Từ ràng buộc (6) ta có E + C2 = N, suy ra C2 = 1 và
E + 1 = N (11-1)
Từ ràng buộc (5), ta có R + C1 = 9, như vậy R = 8 và C1 = 1 (12-1)
(do kết hợp với các ràng buộc (2) (3) và (10-1)).
Từ ràng buộc (4) ta có D + E = Y +10. Đến bước này ta có thể khẳng định các giá trị của D, E, Y chỉ có thể nhận trong tập {2, 3, 4, 5, 6, 7}. Ngoài ra D + E >= 12. Vì vậy chỉ có các khả năng sau có thể xảy ra:
- D = 5 và E = 7
- D = 7 và E = 5 (hai truờng hợp này Y = 2)
- D = 6 và E = 7
- D = 7 và E = 6 (hai trường hợp sau Y = 3)
Xét khả năng thứ nhất. Từ ràng buộc (11-1) ta suy ra N = 8 mâu thuẫn với (12-1) nên bị loại.
Xét khả năng thứ hai. Từ ràng buộc (11-1) ta suy ra N= 6. Kiểm tra điều kiện bài toán đều thoả mãn. Vậy ta có nghiệm là:
S = 9, E = 5, N= 6, D = 7, M= 1, O = 0, R = 8, Y = 2.
Xét khả năng thứ ba. Từ ràng buộc (11-1) suy ra N = 8 mâu thuẫn với (12-1).
Xét khả năng thứ tư. Từ ràng buộc (11-1) suy ra N=7 = D mâu thuẫn.
Phương án 2:
C3 = 1. Từ ràng buộc (7) ta có S = O + 8, suy ra S = 8 và O = 0 (10-2)
(vì M=1 và S <= 9).
Từ ràng buộc (6) ta có E + C2 = N +10
C2=1 thì E= N+9 mâu thuẫn với ràng buộc (1) và (10-2).
C2=0 thì E=N+10 mâu thuẫn với ràng buộc (1).
Vậy phương án 2 không có lời giải.
Bạn đang đọc truyện trên: Truyen2U.Pro