Chương 2 : Các phương pháp giải quyết vấn đề cơ bản

hàm heuristic. Cho h(n) là hàm heuristic đó là một ước lượng khỏang cách của nút n đến nút đích, h(n) phải thỏa mãn các tính chất sau : h(n) >= 0 cho mọi nút n h(n) = 0, suy ra rằng nút n là trạng thái đích h(n) = vô cùng, suy ra rằng nút n là trạng thái cụt đó là trạng thái không dẫn đến đích. Ví dụ : Heuristic của bài tóan trò chơi 8 số là số viên ngói đặt không đúng chổ so với trạng thái đích. Heuristic của bài tóan hành trình người bán hàng đó là khỏang cách giữa hai thành phố kề nhau. Tại mỗi trạng thái hiện hành, phương pháp tìm kiếm heuristic phát sinh ra các trạng thái con, ước lượng heuristic cho tất cả các trạng thái con và chọn lọc một trong những con có giá trị heuristic nhỏ nhất để tiếp tục quá trình tiếp kiếm trong không gian trạng thái của bài tóan. Example : Xét bài tóan trò chơi 8 số với cấu hình đầu và đích cho như hình Goal state Initial state Phương pháp tìm kiếm heuristic giải bài tóan này sử dụng heuristic được mô tả bằng cây tìm kiếm như hình h(a) = 4 h(b) = 5 h(c) =3 h(d) =5 h(e) =3 h(f) =3 h(g) =4 h(i) =4 h(h) =3 h(j) =2 h(k) =4 h(l) =1 h(n) =0 Goal h(m) =2 Giải Thuật Tìm kiếm Best-First search Một trong các phương pháp tìm kiếm heuristic được trạng bị bằng heuristic để tìm lời giải hầu như tốt nhất với bài tóan đó là giải thuật Best-First-Search. Giống như giải thuật tìm kiếm theo chiều rộng, giải thuật sử dụng hai danh sách OPEN và CLOSED để giữ đường của quá trình tìm kiếm trong không gian trạng thái của bài tóan. OPEN : Giữ đường tìm kiếm hiện hành ( các trạng thái chưa được viếng thăm ) CLOSED : Ghi nhận các trạng thái đã được viếng thăm. Giải thuật được mô tả chi tiết như sau : Procedure best-first-search Begin OPEN := [Start]; CLOSED = [ ]; While OPEN  [ ] Begin -Lọai bỏ trạng thái đầu tiên từ OPEN, gọi nó là X; - If X = đích Then return đường lới giải từ trạng thái ban đầu đến X Else begin Phát sinh các con của X áp dụng các luật ứng dụng; Cho mỗi con của X, thực hiện một trong các trường hợp sau : Case : Con chưa có mặt trên OPEN or CLOSED Begin - Ước lượng heuristic cho con; - Cộng con vào danh sách OPEN;; End Case : Con đã có mặt trên OPEN Begin -Nếu mới tốt hơn cũ, lọai bỏ cũ từ danh sách OPEn, Đặt mới vào danh sách OPEN; - Mặt khác, giữ cũ và lọai bỏ mới;. End Case :Con đã có mặt trên CLOSED Begin -Nếu mới tốt hơn cũ, lọai bỏ cũ từ danh sách CLOSED, đặt mới vào danh sách OPEN; - Mặt khác giữ cũ và lọai bỏ mới; End Đặt X vào danh sách closed; Sắp xếp lại các trạng thái rong danh sách OPEN theo thứ từ từ đầu danh sách đến cuối tương ứng với trạng thái có heuristic tốt nhất đến trạng thái có heuristic xấu nhất; End; Return failure End. Giải thuật Best-First-Search giải bài tóan trò chơi 8 số với các vòng lặp cho là Iteration OPEN CLOSED 1 [a4] [ ] 2 [c3,b5,d5] [a4] 3 [ e3,f3,g4,b5,c5] [c3,a4] 4 [f3,h3,g4,i4,b5,c5] [e3,c3,a3] 5 [j2,h3,g4,i4,k4,b5,c5] [f3,e3,c3,a3] 6 [l1,h3,g4,I4,k4,b5,c5] [j2,f3,e3,c3,a3] 7 [n0,m2,h3,g4,I4,k4,b5,c5] [l1, j2,f3,e3,c3,a3] 8 success, n = goal Hàm Đánh Giá Heuristic : Giải thuật tìm kiếm best-first-search sử dụng hàm heuristic h(n) ước lượng khỏang cách từ trạng thái n đến trạng thái đích. Bây giờ, giả sử hai hoặc nhiều trạng thái xuất hiện có cùng giá trị heuristic, trạng thái nào gần gốc của cây nhất đó được xem như là trạng thái tốt nhất. Vì khả năng trạng thái này dẫn đến đích là đường đi tốt nhất. Với lý do này, một hàm đánh giá heuristic f(n) để đánh giá tại mỗi trạng thái n được đề xuất đó là tổng của hai thành phần được thiết lập là f(n) = g(n) + h(n) Trong đó, g(n) là hàm chi phí đo giá chi phí từ trạng thái ban đầu đến trạng thái n, h(n) là hàm heuristic ước lượng khỏang cách từ trạng thái n đến trạng thái đích. Giải thuật tìm kiếm heuristic được trang bị bằng hàm đánh giá heuristic được gọi là giải thuật A. Ví dụ : Cho bản đồ của Romania với các khỏang cách thực sự và đường chim bay đến thành phố Bucharest như hình Ared Siblu Timisoara Zerind Ared Fagaras Oradea Rimnicu Cralova Pitestf Siblu Rimnicu Cralova Bucharest f=0+366 =366 f=140+253=393 f=118+329=447 f=75+374=44 9 f=280+366=646 f=239+178=417 f=146+380=526 f=220+193=413 f=366+160=526 f=366+160=526 f=300+253=553 f=467+0=467 f=504+160=660 f=463+193=656 Goal * Cho g(n) là hàm chi phí đo khỏang cách thực sự từ thành phố bắt đầu Ared đến thành phố n. * Cho h(n) là hàm heuristic ước lượng khỏang cách đường chim bay từ thành phố n đến thành phố đích Bucharest.* Qúa trình tìm kiếm đường đi ngắn nhất từ Ared đến Bucharest dùng hàm đánh giá heuristic bằng cây được mô tả như hình Thỏa Mãn Ràng Buộc Ràng buộc là mối quan hệ giữa hai hoặc nhiều đối tượng trong miền xác định. Bài tóan thỏa mãn ràng buộc là tìm các giá trị cho các đối tượng sao cho thỏa mãn các ràng buộc của bài tóan đặt ra. Ví dụ : Xét các bài tóan cộng rao số học thể hiện dưới dạng các chữ cái cho là Bài tóan đặt ra là tìm các chữ số gán cho các chữ cái sao cho biểu thức số học của nó là đúng. Không cho phép hai chữ cái khác nhau có thể được gán cùng một chữ số. Những bài tóan này được gọi các bài tóan ràng buộc cộng rao số học. Để giải các bài tóan ràng buộc này, Đầu tiên áp dụng các luật suy diễn ràng buộc để tạo ra các ràng buộc quan hệ mới bất kỳ. Kế theo gán chữ số cho mỗi chữ cái trong các ràng buộc hiện hữu để phát sinh ra các ràng buộc mới cho vòng quét tìm kiếm kế theo. Ví dụ : Giải bài tóan rao số học cho là Với bài tóan này, trạng thái ban đầu của bài tóan cho là S = ? C1 = ? E = ? C2 = ? N = ? C3 = ? D = ? C4 = ? M = ? O = ? R = ? Y = ? Trong đó C1, C2, C3 và C4 là các số nhớ. Trạng thái đích của bài tóan là trạng thái mà trong đó tất cả các chữ cái, mỗi của chúng được gán bằng một chữ số sao cho tất cả các ràng buộc của bài tóan được thỏa mãn. Các luật suy diễn ràng buộc của bài tóan được viết với dạng là Constraint1 : D + E = Y nhớ C1 Constraint2 : N + R + C1 = E nhớ C2 Constraint3 : E + O + C2 = N nhớ C3 Constraint4 : S + M + C3 = 0 nhớ C4 = M. Constraint5 : Tất cả các chữ số khác nhau cho (S, E, N, D, M ,O, R, Y). Quá trình giải bài tóan này có thể tiến hành các vòng tìm kiếm quét vòng như sau : Đầu tiên, xét constraint4 đó là S + M + C3 = 0 nhớ C4 = M. M = 1, vì tổng của hai chữ số nhớ C4 không thể lớn hơn 19. O = 0, do S + M(1) + C3(= 9 (số nhớ C4 = 1) và M = 1, vì thế S + C3 > 8 và C3 có thể là một hoặc không. Vòng quét vòng kế theo, xét constraint3 đó là biểu thức E + O + C2 = N nhớ C3. N = E + 1 , do O đã là 0, số nhớ C3 phải là 0 và số nhớ C2 phải là 1. Nếu C3 là 1, ràng buộc có thể được viết là 10 + N = E + C2. Điều này dẫn đến mâu thuẩn vì chữ số E không thể là số lớn 9. Do đó, C3 phải là 0. Vì C3 = 0, biểu thức được viết lại là N = E + C2. Với biểu thức này, nếu C2 = 0 điều này dẫn đến mẫu thuẩn vì N = E; do đó C2 phải là 1. S = 9, do S + 1 + C3 = 10 với C3 = 0. R + N + C1 = 10 + E, vì số C2 là 1 và constraint2 : N + R + C1 = E nhớ C2 = 1, điều đó có thể viết với dạng là R + N + C1 = 10 + E. D + E = Y or D + Y = 10 + Y, do C1 có thể là 0 hoặc có thể là 1. Bây giờ, ta có thể tiến hành giải bài tóan bằng cách xây dựng một hình cây để phỏng đóan các giá trị của E được mô tả như hình Initial state M = 1, C4 = 1 O = 0, C3 = 0 S = 9, C2 = 1 Guess E with 2, 3, 4, 5. N = E + 1 R + N = 10 + E R + N = 9 + E D + E = Y D + E = 10 + Y C1 = 0 C1 = 1 Đóan E = 2, ta có N = 3. Nếu C1 = 0, R = 10 + E – N = 9. Điều này dẫn đến mâu thuẩn vì S đã là 9. Nếu C1 = 1, R = 9 + E – N = 8 và D = 10 + Y – E = 8 + Y. Với Y = 4, D = 12, điều này dẫn đến mâu thuẩn vì D là một chữ số. Đóan E = 3,ta có N = 4. Nếu C1 = 0, R = 10 + E – N = 9. Điều này dẫn đếm mâu thuẩn vì S đã là 9. Nếu C1 = 1, R = 9 + E – N = 8 và D = 10 + Y – E = 7 + Y. Với Y = 2, D = 9, điều này dẫn đến mâu tuẩn vì S đã là 9. Đóan E = 4, ta có N = 5. Nếu C1 = 0, R = 10 + E – N = 9. Điều này dẫn đến mẫu thuẩn vì S đã là 9. Nếu C1 = 1, R = 9 + E – N = 8 và D = 10 + Y – 4. Với Y = 2, D = 8, điều này dẫn đến mâu thuẩn vì R đã là 8. Với Y = 3 D = 9, điều này cũng dẫn đến mâu thuẩn vì S đã là 9. Đóan E = 5, ta có N = 6. Nếu C1 = 0, R = 10 + E – N = 9. Điều này dẫn đến mâu thuẩn vì S đã là 9. Nếu C1 = 1, R = 9 + E – N = 8 và D = 10 + Y – 5. Với Y = 2, ta có D = 7. Điều này dẫn đến trạng thái đích của bài tóan với S = 9, M = 1, O = 0, E = 5, N = 6, R = 8, D = 7, Y = 2, C4 = 1, C3 = 0, C2 = 1 và C1 = 1 thỏa mãn tất cả các ràng buộc của bài tóan cho trên. Do vậy, đáp án của bài tóan cho là