Bài giảng Trí tuệ nhân tạo - Nguyễn Thị Thúy Loan

TRÍ TUỆ NHÂN TẠO ThS. Nguyễn Thị Thúy Loan 6/8/2010 Nguyễn Thị Thúy Loan 2 Cách đánh giá  Thực hành: 30%  Bài tập: 20%  Lý thuyết: 50% 6/8/2010 Nguyễn Thị Thúy Loan 3 Tài liệu tham khảo [1]. Bài giảng của Nguyễn Thị Thúy Loan [2]. Trí tuệ nhân tạo, Đỗ Trung Tuấn, NXB Giáo dục, 1998. [3]. Bạch Hưng Khang – Hoàng Kiếm, Trí tuệ nhân tạo, NXB KHKT - 1989. [4]. Lập trình C cho TTNT, 3C soft (dịch), NXB Đại học và Trung học chuyên nghiệp Hà nội – 1990. [5]. Trang web Engineering-and-Computer-Science/index.htm 6/8/2010 Nguyễn Thị Thúy Loan 4 NỘI DUNG  Các thuật giải tô màu đồ thị.  Các thuật giải tìm kiếm trên đồ thị.  Biểu diễn và xử lý tri thức.  Phân lớp. ThS. Nguyễn Thị Thúy Loan Chương I CÁC THUẬT GIẢI TÔ MÀU ĐỒ THỊ 6/8/2010 Nguyễn Thị Thúy Loan 6 6 Bài toán  Cho một đồ thị gồm n đỉnh. Quan hệ giữa đỉnh i và đỉnh j, kí hiệu Qhij, là 1 nếu đỉnh i có nối với đỉnh j và 0 nếu ngược lại.  Bài toán đặt ra là làm thế nào để tô màu đồ thị sao cho không tồn tại hai đỉnh có quan hệ với nhau được tô chung một màu với số màu cần tô là ít nhất? 6/8/2010 Nguyễn Thị Thúy Loan 7 7 Tô 3 màu Ít nhất chưa? a b c d p h e Ví dụ 6/8/2010 Nguyễn Thị Thúy Loan 8 8 Thuật giải tô màu “Tối ưu” Bước 1: [Tô màu] Tô màu i (i bắt đầu xét từ 1) cho đỉnh có bậc lớn nhất. Bước 2: [Hạ bậc & cấm tô] 2.1. Bậc của đỉnh được tô màu i thì bậc:=0. 2.2. Bậc của đỉnh có quan hệ với đỉnh được tô màu i thì bậc:= bâc – 1. 2.3. Cấm tô màu i cho đỉnh có quan hệ với đỉnh được tô màu i. Bước 3: Lặp lại bước 1 cho đến khi tất cả các đỉnh đều được tô màu. 6/8/2010 Nguyễn Thị Thúy Loan 9 9 Minh họa d b p c e h a 10 Một công ty có 8 đài phát thanh A, B, C, D, E, F, G, H có khoảng cách (km) được cho trong ma trận sau: Do yêu cầu kỹ thuật nên các đài có khoảng cách  100km không được dùng chung một trạm phát sóng. Hãy lắp đặt các trạm phát sóng sao cho số trạm cần lắp là nhỏ nhất. A B C D E F G H A 0 100 50 30 200 150 40 120 B 0 30 80 120 50 200 150 C 0 120 100 30 80 50 D 0 50 120 150 30 E 0 200 120 120 F 0 180 150 G 0 50 H 0 Ví dụ 6/8/2010 Nguyễn Thị Thúy Loan 11 11 1. Xác định đồ thị a) Đỉnh: b) Cung: A B C D E F G H A 0 100 50 30 200 150 40 120 B 0 30 80 120 50 200 150 C 0 120 100 30 80 50 D 0 50 120 150 30 E 0 200 120 120 F 0 180 150 G 0 50 H 0 Giải quyết 6/8/2010 Nguyễn Thị Thúy Loan 12 12 2. Áp dụng thuật giải để tô màu Kết quả: Giải quyết 6/8/2010 Nguyễn Thị Thúy Loan 13 13 Thuật giải tham lam (Greedy) Bước 1: i := 0 Bước 2: i := i+1 Tô màu i cho tất cả các đỉnh có thể tô được. Bước 3: Lặp lại bước 2 cho đến khi tất cả các đỉnh đều được tô màu. 14 Ví dụ Cho ma trận bên  AC AD AF BC BD BE CE DE DF EF AC 0 1 1 1 0 0 1 0 0 0 AD 1 0 1 0 1 0 0 1 1 0 AF 1 1 0 0 0 0 0 0 1 1 BC 1 0 0 0 1 1 1 0 0 0 BD 0 1 0 1 0 1 0 1 1 0 BE 0 0 0 1 1 0 1 1 0 1 CE 1 0 0 1 0 1 0 1 0 1 DE 0 1 0 0 1 1 1 0 1 1 DF 0 1 1 0 1 0 0 1 0 1 EF 0 0 1 0 0 1 1 1 1 0 AC AD AF BC BD BE CE DE DF EF i=1 1    i 1   i 1 AD AF BC BE CE DE DF i=2 2   2   AF BE CE DE DF i=3 3 3   CE DE DF i=4 4 i=4 4  4 DE i=5 5 6/8/2010 Nguyễn Thị Thúy Loan 15 15 Thuật giải sắp thứ tự + tham lam Bước 1: Sắp xếp các đỉnh theo chiều giảm dần của bậc. i := 0 Bước 2: i := i+1 Tô màu i cho tất cả các đỉnh có thể tô được (xét từ trái sang). Bước 3: Lặp lại bước 2 cho đến khi tất cả các đỉnh đều được tô màu. 16 Ví dụ Cho ma trận bên  AC AD AF BC BD BE CE DE DF EF Bậc AC 0 1 1 1 0 0 1 0 0 0 4 AD 1 0 1 0 1 0 0 1 1 0 5 AF 1 1 0 0 0 0 0 0 1 1 4 BC 1 0 0 0 1 1 1 0 0 0 4 BD 0 1 0 1 0 1 0 1 1 0 5 BE 0 0 0 1 1 0 1 1 0 1 5 CE 1 0 0 1 0 1 0 1 0 1 5 DE 0 1 0 0 1 1 1 0 1 1 6 DF 0 1 1 0 1 0 0 1 0 1 5 EF 0 0 1 0 0 1 1 1 1 0 5 DE AD BD BE CE DF EF AC AF BC i=1 1       1   AD BD BE CE DF EF AF BC i=2 2   2    BD CE DF EF AF BC i=3 3  3  3 DF EF BC i=4 4  4 EF i=5 5 6/8/2010 Nguyễn Thị Thúy Loan 17 17 Ví dụ Một cuộc hội thảo có 9 chủ đề a, b, c, d, e, f, g, h, i biết rằng các chủ đề sau không được phép diễn ra trong cùng một buổi: ac, bde, adg, cdf, dfg, egh, ghi. Hãy sắp xếp các chủ đề vào các buổi sao cho số buổi diễn ra là ít nhất. 6/8/2010 Nguyễn Thị Thúy Loan 18 18 Ví dụ Học kì II năm 2009 -2010, Phòng ĐT muốn tổ chức thi các môn A,B,C,D,E,F,G,H,I biết rằng các môn sau không được thi chung một buổi. ABC, AE, BCD, BHI, EFG, EI, GHI. Hãy sắp xếp lịch thi sao cho số buổi thi cần sắp là ít nhất. 6/8/2010 Nguyễn Thị Thúy Loan 19 19 Ví dụ Cho ngã năm giao thông như sau trong đó BE là đường 1 chiều: B A E D C Yêu cầu: 1. Xác định đồ thị. 2. Tô màu đồ thị. Sao cho tại mỗi thời điểm, các tuyến lưu thông không giao nhau. ThS. Nguyễn Thị Thúy Loan Chương II CÁC PHƯƠNG PHÁP TÌM KIẾM LỜI GIẢI Ref: Phần 1 6/8/2010 Nguyễn Thị Thúy Loan 21 Nội dung  Bài toán tìm kiếm  Tìm kiếm Theo chiều Rộng  Tìm kiếm Theo chiều Sâu 6/8/2010 Nguyễn Thị Thúy Loan 22 Bài toán tìm kiếm Làm sao đi từ S đến G? Số bước đi ít nhất có thể là bao nhiêu? Đi qua các đỉnh nào? S G d b p q c e h a f r START GOAL 6/8/2010 Nguyễn Thị Thúy Loan 23 Bài toán tìm kiếm Một bài toán tìm kiếm gồm năm thành phần: Q , S , G , succs , cost  Q là một tập hữu hạn các trạng thái.  S  Q một tập khác rỗng các trạng thái đầu (START).  G  Q một tập khác rỗng các trạng thái đích (GOAL). 6/8/2010 Nguyễn Thị Thúy Loan 24 Bài toán tìm kiếm  succs: Q  P(Q) là một hàm nhận một trạng thái làm đầu vào và trả về kết quả là một tập trạng thái. succs(s) nghĩa là “tập các trạng thái có thể đến từ s trong một bước”.  cost: Q  Q  R là một hàm nhận hai trạng thái s và s’ làm đầu vào. Nó trả về chi phí một bước của việc di chuyển từ s đến s’. Hàm chi phí chỉ được xác định khi và chỉ khi s’ là trạng thái con của s, nghĩa là s’  succs(s) Q = {START, a , b , c , d , e , f , h , p , q , r , GOAL} S = { START } G = { GOAL } succs(b) = { a } succs(e) = { h , r } succs(a) = {}, … cost(s,s’) = 1 cho tất cả các biến đổi START GOAL d b p q c e h a f r Bài toán tìm kiếm Q = {START, a , b , c , d , e , f , h , p , q , r , GOAL} S = { START } G = { GOAL } succs(b) = { a } succs(e) = { h , r } succs(a) = {} cost(s,s’) = 1 cho tất cả các biến đổi START GOAL d b p q c e h a f r T ạ i s a o t a q u a n t â m ? B à i t o á n n à o g i ố n g n h ư v ậ y ? Bài toán tìm kiếm Các bài toán tìm kiếm 6/8/2010 Nguyễn Thị Thúy Loan 28 Các bài toán tìm kiếm Lập lịch 8-Hậu Gì nữa? Giải toán 6/8/2010 Nguyễn Thị Thúy Loan 29 Tìm kiếm theo chiều rộng (BFS – Breadth First Search) START GOAL d b p q c e h a f r 6/8/2010 Nguyễn Thị Thúy Loan 30 Tìm kiếm theo chiều rộng (BFS – Breadth First Search)  Gán nhãn tất cả trạng thái có thể đi đến được từ S trong 1 bước.  Sau đó gán nhãn tất cả trạng thái có thể đi đến được từ S trong 2 bước nhưng không thể đi đến được trong ít hơn 2 bước. 6/8/2010 Nguyễn Thị Thúy Loan 31 Tìm kiếm theo chiều rộng (BFS – Breadth First Search)  Sau đó gán nhãn tất cả trạng thái có thể đi đến được từ S trong 3 bước nhưng không thể đi đến được trong ít hơn 3 bước.  v.v… cho đến khi đạt được trạng thái G hoặc không còn đi tiếp được nữa. 6/8/2010 Nguyễn Thị Thúy Loan 32 Tìm kiếm theo chiều rộng START GOAL d b p q c e h a f r 0 bước từ start 6/8/2010 Nguyễn Thị Thúy Loan 33 START GOAL d b p q c e h a f r 0 bước từ start 1 bước từ start Tìm kiếm theo chiều rộng 6/8/2010 Nguyễn Thị Thúy Loan 34 START GOAL d b p q c e h a f r 0 bước từ start 1 bước từ start 2 bước từ start Tìm kiếm theo chiều rộng 6/8/2010 Nguyễn Thị Thúy Loan 35 START GOAL d b p q c e h a f r 0 bước từ start 1 bước từ start 2 bước từ start 3 bước từ start Tìm kiếm theo chiều rộng 6/8/2010 Nguyễn Thị Thúy Loan 36 START GOAL d b p q c e h a f r 0 bước từ start 1 bước từ start 2 bước từ start 3 bước từ start 4 bước từ start Tìm kiếm theo chiều rộng 6/8/2010 Nguyễn Thị Thúy Loan 37 Ghi nhớ đường đi! START GOAL d b p q c e h a f r 6/8/2010 Nguyễn Thị Thúy Loan 38 Ghi nhớ đường đi! Khi gán nhãn một trạng thái, ghi nhận trạng thái trước đó. Ghi nhận này được gọi là con trỏ quay lui. Lịch sử trước đó được dùng để phát sinh con đường lời giải, khi đã tìm được đích: “Tôi đã đến đích. Tôi thấy mình đã ở f trước đó. Và tôi đã ở r trước khi tới f. Và… …. do đó con đường lời giải là S  e r f G” 6/8/2010 Nguyễn Thị Thúy Loan 39 Con trỏ quay lui START GOAL d b p q c e h a f r 0 bước từ start 1 bước từ start 2 bước từ start 3 bước từ start 4 bước từ start 6/8/2010 Nguyễn Thị Thúy Loan 40 START GOAL d b p q c e h a f r 0 bước từ start 1 bước từ start 2 bước từ start 3 bước từ start 4 bước từ start Con trỏ quay lui 6/8/2010 Nguyễn Thị Thúy Loan 41 Tìm kiếm theo chiều rộng Với bất kỳ trạng thái s nào đã gán nhãn, ghi nhớ:  previous(s) là trạng thái trước đó trên đường đi ngắn nhất từ trạng thái START đến s.  Trong vòng lặp thứ k của thuật toán ta bắt đầu với Vk được định nghĩa là tập các trạng thái mà từ trạng thái START đi đến có đúng k bước 6/8/2010 Nguyễn Thị Thúy Loan 42  Sau đó, trong suốt vòng lặp, ta sẽ tính Vk+1, được định nghĩa là tập các trạng thái mà từ trạng thái START đi đến có đúng k+1 bước  Chúng ta bắt đầu với k = 0, V0 = {START} và định nghĩa, previous(START) = NULL  Sau đó ta sẽ thêm vào những trạng thái một bước từ START vào V1. Và tiếp tục. Tìm kiếm theo chiều rộng 6/8/2010 Nguyễn Thị Thúy Loan 43 START GOAL d b p q c e h a f rV0 BFS 6/8/2010 Nguyễn Thị Thúy Loan 44 START GOAL d b p q c e h a f rV0 V1 BFS 6/8/2010 Nguyễn Thị Thúy Loan 45 START GOAL d b p q c e h a f rV0 V1 V2 BFS 6/8/2010 Nguyễn Thị Thúy Loan 46 START GOAL d b p q c e h a f rV0 V1 V2 V3 BFS 6/8/2010 Nguyễn Thị Thúy Loan 47 START GOAL d b p q c e h a f r V4 V0 V1 V2 V3 BFS 6/8/2010 Nguyễn Thị Thúy Loan 48 START GOAL d b p q c e h a f r V4 V0 V1 V2 V3 G i ả s ử k h ô n g g i a n t ì m k i ế m c h o p h é p c h ú n g t a l ấ y đ ư ợ c t r ạ n g t h á i t r ư ớ c m ộ t c á c h t h u ậ n t i ệ n • C ó t h ể n g h ĩ r a m ộ t c á c h k h á c c h o B F S ? • C ó t h ể k h ô n g c ầ n p h ả i l ư u t r ữ n h ữ n g g ì t r ư ớ c đ ó p h ả i l ư u ? BFS 6/8/2010 Nguyễn Thị Thúy Loan 49 Chi phí chuyển đổi START GOAL d b p q c e h a f r 2 9 9 81 1 2 3 5 34 4 15 1 5 5 2 6/8/2010 Nguyễn Thị Thúy Loan 50  Lưu ý rằng BFS tìm đường đi ngắn nhất theo số bước. Nó không tìm thấy đường đi có chi phí thấp nhất.  Bây giờ chúng ta xem xét một thuật toán tìm đường đi với chi phí thấp nhất. Trong vòng lặp thứ k, với bất kỳ trạng thái S nào, đặt g(s) là chi phí đường đi có chi phí nhỏ nhất đến S trong k bước hay ít hơn. Chi phí chuyển đổi 6/8/2010 Nguyễn Thị Thúy Loan 51 Tìm kiếm với chi phí đồng nhất (UCS – Uniform Cost Search)  Một cách tiếp cận BFS đơn giản về mặt khái niệm khi có chi phí chuyển đổi  Dùng hàng đợi ưu tiên Hàng đợi ưu tiên Một hàng đợi ưu tiên là một cấu trúc dữ liệu trong đó ta có thể thêm và lấy các cặp (thing, value) với các thao tác sau: Init-PriQueue(PQ) khởi tạo PQ rỗng. Insert-PriQueue(PQ, thing, value) thêm (thing, value) vào hàng đợi. Pop-least(PQ) trả về cặp (thing, value) với giá trị thấp nhất, và loại bỏ nó khỏi hàng đợi. Hàng đợi ưu tiên có thể được cài đặt theo một cách sao cho chi phí của các toán tử thêm vào và lấy ra là: Rất nhỏ (dù không tuyệt đối) O(log(số mục trong hàng đợi ưu tiên)) 6/8/2010 Nguyễn Thị Thúy Loan 53 UCS  Một cách tiếp cận BFS đơn giản về mặt khái niệm khi có chi phí chuyển đổi  Dùng hàng đợi ưu tiên PQ = Tập trạng thái đã được mở Độ ưu tiên của trạng thái s là g(s) = chi phí đến s sử dụng đường đi được cho bởi con trỏ quay lui. 6/8/2010 Nguyễn Thị Thúy Loan 54 Bắt đầu UCS PQ = { (s,0, null) } START GOAL d b p q c e h a f r 2 9 9 81 1 2 3 5 34 4 15 1 2 5 2 PQ = { (s,0,null) } START GOAL d b p q c e h a f r 2 9 9 81 1 2 3 5 34 4 15 1 2 5 2 Lặp: 1. Lấy trạng thái có chi phí thấp nhất từ PQ 2. Thêm các con vào PQ Lặp UCS n = (s,0) PQ = { (p,1,s), (d,3,s), (e,9,s) } START GOAL d b p q c e h a f r 2 9 9 81 1 2 3 5 34 4 15 1 2 5 2 Lặp UCS Lặp: 1. Lấy trạng thái có chi phí thấp nhất từ PQ 2. Thêm các con vào PQ n = (p,1) PQ = { (d,3,s), (e,9,s), (q,16,p) } START GOAL d b p q c e h a f r 2 9 9 81 1 2 3 5 34 4 15 1 2 5 2 Lặp UCS Lặp: 1. Lấy trạng thái có chi phí thấp nhất từ PQ 2. Thêm các con vào PQ n = (d,3) PQ = { (b,4,d), (e,5,d), (c,11,d), (q,16,p) } START GOAL d b p q c e h a f r 2 9 9 81 1 2 3 5 34 4 15 1 2 5 2 Lặp UCS Lặp: 1. Lấy trạng thái có chi phí thấp nhất từ PQ 2. Thêm các con vào PQ Lặp: 1. Lấy trạng thái chi phí thấp nhất từ PQ 2. Thêm các con START GOAL d b p q c e h a f r 2 9 9 81 1 2 3 5 34 4 15 1 2 5 2 n = (d,3) PQ = { (b,4,d), (e,5,d), (c,11,d), (q,16,p) } Lặp UCS START GOAL d b p q c e h a f r 2 9 9 81 1 2 3 5 34 4 15 1 2 5 2 Lặp: 1. Lấy trạng thái chi phí thấp nhất từ PQ 2. Thêm các con n = (b,4) PQ = { (e,5,d), (a,6,b), (c,11,d), (q,16,p) } Lặp UCS n = (e,5) PQ = { (a,6,b),(h,6,e),(c,11,e),(r,14,e),(q,16,p) } START GOAL d b p q c e h a f r 2 9 9 81 1 2 3 5 34 4 15 1 2 5 2 Lặp: 1. Lấy trạng thái chi phí thấp nhất từ PQ 2. Thêm các con Lặp UCS n = (a,6) PQ = { (h,6,e),(c,11,e),(r,14,e),(q,16,p) } START GOAL d b p q c e h a f r 2 9 9 81 1 2 3 5 34 4 15 1 2 5 2 Lặp: 1. Lấy trạng thái chi phí thấp nhất từ PQ 2. Thêm các con Lặp UCS n = (h,6) PQ = { (q,10,h), (c,11,e),(r,14,e) } START GOAL d b p q c e h a f r 2 9 9 81 1 2 3 5 34 4 15 1 2 5 2 Lặp: 1. Lấy trạng thái chi phí thấp nhất từ PQ 2. Thêm các con Lặp UCS n = (h,6) PQ = { (q,10,h), (c,11,d),(r,14,e) } START GOAL d b p q c e h a f r 2 9 9 81 1 2 3 5 34 4 15 1 2 5 2 Lặp: 1. Lấy trạng thái chi phí thấp nhất từ PQ 2. Thêm các con Lặp UCS n = (q,10) PQ = { (c,11,d),(r,14,e) } START GOAL d b p q c e h a f r 2 9 9 81 1 2 3 5 34 4 15 1 2 5 2 Lặp: 1. Lấy trạng thái chi phí thấp nhất từ PQ 2. Thêm các con Lặp UCS n = (c,11) PQ = {(r,13,q) } START GOAL d b p q c e h a f r 2 9 9 81 1 2 3 5 34 4 15 1 2 5 2 Lặp: 1. Lấy trạng thái chi phí thấp nhất từ PQ 2. Thêm các con Lặp UCS n = (r,13) PQ = { (f,18,r) } START GOAL d b p q c e h a f r 2 9 9 81 1 2 3 5 34 4 15 1 2 5 2 Lặp: 1. Lấy trạng thái chi phí thấp nhất từ PQ 2. Thêm các con Lặp UCS n =(f,18) PQ = { (G,23,f) } START GOAL d b p q c e h a f r 2 9 9 81 1 2 3 5 34 4 15 1 2 5 2 Lặp UCS Lặp: 1. Lấy trạng thái chi phí thấp nhất từ PQ 2. Thêm các con n = (g, 23) PQ = {} START GOAL d b p q c e h a f r 2 9 9 81 1 2 3 5 34 4 15 1 2 5 2 Lặp UCS Lặp: 1. Lấy trạng thái chi phí thấp nhất từ PQ 2. Thêm các con START GOAL d b p q c e h a f r 2 9 9 81 1 2 3 5 34 4 15 1 2 5 2 n = (g, 23) PQ = { (G,23,f) } Lặp UCS Lặp: 1. Lấy trạng thái chi phí thấp nhất từ PQ 2. Thêm các con PQ = { } START GOAL d b p q c e h a f r 2 9 9 81 1 2 3 5 34 4 15 1 2 5 2 Kết thúc UCS Lặp: 1. Lấy trạng thái chi phí thấp nhất từ PQ 2. Thêm các con Biểu diễn cây tìm kiếm START GOAL d b p q c e h a f r C h ú n g t a d u y ệ t c â y t ì m k i ế m v ớ i B F S t h e o t h ứ t ự n à o ? START GOAL d b p q c e h a f r Biểu diễn cây tìm kiếm START GOAL d b p q c e h a f r Biểu diễn cây tìm kiếm START GOAL d b p q c e h a f r Biểu diễn cây tìm kiếm START GOAL d b p q c e h a f r Là đích, dừng Biểu diễn cây tìm kiếm Tìm kiếm theo chiều sâu Một thay thế cho BFS. Luôn mở từ node vừa mới mở nhất, nếu nó có bất kỳ node con nào chưa thử. Ngược lại quay lại node trước đó trên đường đi. START GOAL d b p q c e h a f r 2 9 9 81 1 2 3 5 34 4 15 1 5 5 2 DFS trên thực tế START START d START d b START d b a START d c START d c a START d e START d e r START d e r f START d e r f c START d e r f c a START d e r f GOAL START GOAL d b p q c e h a f r Duyệt cây tìm kiếm DFS Thứ tự mà trong đó các node của cây tìm kiếm được viếng? Là đích, dừng 6/8/2010 Nguyễn Thị Thúy Loan 80 Bài tập A B C D E F G A 0 1 0 0 0 0 2 B 0 0 4 0 0 3 0 C 0 0 0 8 0 3 0 D 3 0 0 0 3 0 0 E 0 0 0 0 0 0 12 F 0 0 0 1 3 0 0 G 0 0 1 7 0 5 0 S G ThS. Nguyễn Thị Thúy Loan Chương II CÁC THUẬT GIẢI TÌM KIẾM HEURISTICS Phần 2 6/8/2010 Nguyễn Thị Thúy Loan 82 Nội dung  Tìm kiếm với tri thức bổ sung o Tháp Hà nội o Taci o Đong sữa  Bài toán người bán hàng (TSP – Traveling Salesman Problem)  Thuật giải min – max 6/8/2010 Nguyễn Thị Thúy Loan 83 Thuật giải tìm kiếm với tri thức bổ sung 6/8/2010 Nguyễn Thị Thúy Loan 84 AT (Algorithm for Tree Search) 1. Mọi đỉnh n, mọi hàm g đều ẩn. o Mở đỉnh S0 o Gán g(S0) = 0 2. Chọn đỉnh mở với hàm g là nhỏ nhất và gọi là đỉnh n. o Nếu u là đích thì đường đi từ S0  u là đường đi ngắn nhất. 6/8/2010 Nguyễn Thị Thúy Loan 85 o Nếu tồn tại nhiều hơn một đỉnh n có hàm g là nhỏ nhất thì ta kiểm tra xem trong đó có đỉnh nào là đích hay không, nếu có dừng. Nếu không thì chọn ngẫu nhiên 1 đỉnh gọi là đỉnh u. o Nếu không tồn tại đỉnh mở tương ứng thì cây biểu diễn vấn đề không có đường đi ngắn nhất đến đích. Dừng lại. AT (Algorithm for Tree Search) 6/8/2010 Nguyễn Thị Thúy Loan 86 3. Đóng n và mở mọi đỉnh sau n (có cùng hướng từ u đến) o  đỉnh S sau n: o G(s) = g(u) + giá thành (u s)// cost(u,s) 4. Lặp lại bước 2. AT (Algorithm for Tree Search) 6/8/2010 Nguyễn Thị Thúy Loan 87 Ví dụ  Cho cây tìm kiếm sau: A B C D RJHF E G I SL 2 1 3 3 24 15 6 3 3 1  Tìm đường đi ngắn nhất từ A  đích 6/8/2010 Nguyễn Thị Thúy Loan 88 Thuật giải AKT B1: Mọi đỉnh n, mọi hàm g,h,f đều ẩn. Mở đỉnh đầu tiên S0 Gán g(S0) = 0 Sử dụng tri thức bổ sung ước lượng h(S0) F(S0) = h(S0) 6/8/2010 Nguyễn Thị Thúy Loan 89 Thuật giải AKT B2: Chọn đỉnh mở tương ứng với hàm f là nhỏ nhất và gọi đỉnh này là đỉnh n.  Nếu n là đích thì đường đi từ S0  n là đường đi ngắn nhất đến đích nên dừng (thành công).  Nếu không tồn tại đỉnh mở tương ứng nào thì cây biểu diễn vấn đề không có đường đi đến đích nên dừng (thất bại). 6/8/2010 Nguyễn Thị Thúy Loan 90 Thuật giải AKT  Nếu tồn tại nhiều hơn 1 đỉnh mở cùng hàm f là nhỏ nhất thì kiểm tra xem trong số này có đỉnh nào là đích hay không? Nếu có thì dừng, nếu không thì chọn ngẫu nhiên 1 đỉnh gọi là đỉnh n. B3: Đóng đỉnh n và mọi đỉnh sau n (đỉnh sau n là đỉnh có cung hướng từ n đến) 6/8/2010 Nguyễn Thị Thúy Loan 91 Thuật giải AKT đỉnh S sau n:  g(S) = g(n) + chi phí từ n đến S  Sử dụng tri thức bổ sung ước lượng h(S)  f(S) = g(S) + h(S) B4: Quay lại B2. 6/8/2010 Nguyễn Thị Thúy Loan 92 Ví dụ tháp hà nội ? A B C 6/8/2010 Nguyễn Thị Thúy Loan 93 Với N = 3 Hàm h (heuristic) = Số lần ít nhất phải di chuyển đĩa để đạt trạng thái đích (chỉ xét các tình trạng của cột đích) 0 1 2 3 3 4 4 5 6/8/2010 Nguyễn Thị Thúy Loan 94 g = 0 h = 3 f = 3 g = 1 h = 3 f = 4 g = 1 h = 4 f = 5 g = 2 h = 4 f = 6 g = 2 h = 4 f = 6X Với N = 3 6/8/2010 Nguyễn Thị Thúy Loan 95 g = 0 h = 3 f = 3 g = 1 h = 3 f = 4 g = 1 h = 4 f = 5 g = 2, h = 4,f = 6 g = 2,h = 4,f = 6g = 2,h = 3,f = 5 …. Với N = 3 X 6/8/2010