Kĩ thuật lập trình - Chương 3: Các kỹ thuật tìm kiếm Heuristics

1Chương 3: Các kỹ thuật tìm kiếm Heuristics 2Nội dung
Khái niệm
Tìm kiếm tốt nhất trước
Phương pháp leo ñồi
Cài ñặt hàm ñánh giá
Thu giảm ràng buộc
Giải thuật cắt tỉa α-β 3Giới hạn của duyệt hệ thống
8-puzzle  Lời giải cần trung bình 22 cấp (depth)  ðộ rộng của bước ~ 3  Tìm kiếm vét cạn cho 22 cấp cần
3.1 x 1010 states  Nếu chỉ giới hạn ở d=12, cần trung bình 3.6 triệu trạng thái [24 puzzle có 1024 trạng thái]
Cần chiến lược tìm kiếm heuristic 4Khái niệm: Heuristic
Heuristics: là các phỏng ñoán, ước chừng dựa trên kinh nghiệm, trực giác
Các hệ giải quyết AI sử dụng heuristic trong hai tình huống cơ bản:  Bài toán ñược ñịnh nghĩa chính xác nhưng chi phí tìm lời giải vét cạn là không thể chấp nhận VD: Sự bùng nổ KGTT trong trò chơi cờ vua  Vấn ñề với nhiều sự mơ hồ trong lời phát biểu bài toán hay dữ liệu cũng như tri thức sẵn có VD: Chẩn ñoán trong y học 5Khái niệm: Giải thuật Heuristics
Một giải thuật heuristic có thể ñược xem gồm 2 phần:  Phép ño heuristic: thể hiện qua hàm ñánh giá heuristic (evaluation function f(n) - EF), dùng ñể ñánh giá các ñặc ñiểm của một trạng thái trong KGTT  Giải thuật tìm kiếm heuristic:
TK tốt nhất (best-first search)
A* search
Giải thuật leo núi (hill-climbing) 6Ví dụ phép ño Heuristics 7Ví dụ phép ño Heuristics (tt) Heuristic “Số ñường thắng nhiều nhất” (theo các ñường chéo trên bàn cờ) áp dụng cho các con cờ ñầu tên ñặt vào bàn cờ trong bàn cờ tic-tac-toe 8Ví dụ phép ño Heuristics (tt) 9Giải thuật leo ñồi (Hill climbing)
Giải thuật  Xét trạng thái bắt ñầu
Nếu là ñích => dừng
Ngược lại: thiết lập khởi ñầu như TT hiện tại  Lặp ñến khi: gặp ñích OR không còn luật nào chưa ñược áp dụng vào TT hiện tại
Lựa một luật ñể áp dụng vào TT hiện tại ñể sinh ra một TT mới
Xem xét TT mới này  Nếu là ñích => dừng  Nếu không là ñích, nhưng tốt hơn TT hiện tại => thiết lập TT mới là TT hiện tại  Nếu không tốt hơn thì thì tiếp lần lặp kế 10 Giải thuật leo ñồi (tt)
Giới hạn  Giải thuật có khuynh hướng bị sa lầy ở những cực ñại cục bộ
Lời giải tìm ñược không tối ưu
Không tìm ñược lời giải mặc dù có tồn tại lời giải  Giải thuật có thể gặp vòng lặp vô hạn do không lưu giữ thông tin về các trạng thái ñã duyệt 11 Giải thuật leo ñồi (tt)
Bài toán 8 Hậu  Trang thái bắt ñầu: mỗi Hậu trên 1cột  Trạng thái ñích: các Hậu không thể tấn công nhau  Phép ño Heuristic h(n) : số lượng các cập hậu ñối kháng nhau H(n) = 17 h(n) = 1 12 Tìm kiếm tốt nhất (BFS)
Là phương pháp dung hoà của BrFS và DFS
Có sử dụng ñể ñánh giá ưu thế của mỗi trạng thái, có thể là ước lượng từ nó ñến TT ñích
Tại mỗi bước, GT sẽ chọn trạng thái mà nó cho rằng là có ưu thế nhất trong số các trạng thái ñã sinh ra ñược ñến thời ñiểm ñó
Khác với GT leo ñồi có cải tiến ở chổ: có lưu tất cả những TT ñã phát sinh ñến thời ñiểm chọn TT ñể xét tiếp
Dùng hai danh sách:  OPEN: chứa các TT sẽ ñược xét.  CLOSED: chứa các TT ñã xét qua. 13 Tìm kiếm tốt nhất (BFS)
Giải thuật  OPEN = [TT ñầu]  Lặp ñến khi: gặp ñích OR OPEN rỗng
Lấy TT tốt nhất từ OPEN
Phát sinh các con của nó
Với mỗi con:  Nếu nó chưa ñược phát sinh: gán nó trị ñánh giá, ñưa vào OPEN, ghi nhận TT cha của nó  Nếu ñã ñược phát sinh trước: Nếu ñạt ñến bởi ñường khác tốt hơn => ghi nhận lại TT cha của nó, cập nhật lại trị ñánh giá của nó và của các con của nó 14 Tìm kiếm tốt nhất (BFS) 1. open = [A5]; closed = [ ] 2. ðánh giá A5; open = [B4,C4,D6]; closed = [A5] 3. ðánh giá B4; open = [C4,E5,F5,D6]; closed = [B4,A5] 4. ðánh giá C4; open = [H3,G4,E5,F5,D6]; closed = [C4,B4,A5] 5. ðánh giá H3; open = [O2,P3,G4,E5,F5,D6]; closed = [H3,C4,B4,A5] 6. ðánh giá O2; open = [P3,G4,E5,F5,D6]; closed = [O2,H3,C4,B4,A5] 7. ðánh giá P3; tìm ñược lời giải! Open là queue, xếp theo Heuristic tăng dần 15 Cài ñặt hàm ñánh giá (EF)
Xét trò chơi 8-ô, mỗi trạng thái n, một giá trị f(n): f(n) = g(n) + h(n)  g(n) = khoảng cách thực sự từ n ñến trạng thái bắt ñầu  h(n) = hàm heuristic ñánh giá khoảng cách từ trạng thái n ñến mục tiêu. 57 461 382 57 461 382 567 41 382 57 461 382 start 567 48 321 goal g(n) = 0 g(n) = 1 6 4 6f(n) = h(n): số lượng các vị trí còn sai; 16 Ví dụ 17 Ví dụ 18 Ví dụ 19 Heuristic trong trò chơi ñối kháng
Giải thuật minimax  Hai ñấu thủ trong trò chơi ñược gọi là MIN và MAX.  Mỗi nút lá có giá trị:
1 nếu là MAX thắng,
0 nếu là MIN thắng.  Minimax sẽ truyền các giá trị này lên cao dần trên ñồ thị, qua các nút cha mẹ kế tiếp theo các luật sau:
Nếu trạng thái cha mẹ là MAX, gán cho nó giá trị lớn nhất có trong các trạng thái con.
Nếu trạng thái cha mẹ là MIN, gán cho nó giá trị nhỏ nhất có trong các trạng thái con. 20 Áp dụng GT Minimax vào Trò Chơi NIM MIN MIN MIN MAX MAX MAX 1 1 1 1 1 1 1 0 0 0 0 0 01 KẾT QUẢ CỦA MIN KẾT QUẢ CỦA MAX 21 Minimax với ñộ sâu lớp cố ñịnh
Minimax ñối với một KGTT giả ñịnh 3 là giá trị max của các nút con 2 là giá trị min của các nút con Các nút lá ñược gán các giá trị heuristic nào ñó Còn giá trị tại các nút trong là các giá trị nhận ñược dựa trên giải thuật Minimax (min hay max cua các nút con) 22 Heuristic trong trò chơi tic-tac-toe Hàm Heuristic: E(n) = M(n) – O(n) Trong ñó: M(n) là tổng số ñường thắng có thể của tôi O(n) là tổng số ñường thắng có thể của ñối thủ E(n) là trị số ñánh giá tổng cộng cho trạng thái n 23 Minimax 2 lớp ñược áp dụng vào nước ñi mở ñầu trong tic-tac-toe Max (X) có 5 ñường thắng, Min(O) có 4, hàm heuristic là -1 24 Thu giảm bài toán
ðồ thị AND-OR :  ðược dùng ñể biểu diễn KGTT cho bài toán giải ñược bằng cách phân rã ra các bài toán nhỏ hơn  Khi bài toán ñược phân rã thành N bài toán con, mà tất cả chúng phải ñược giải ñể hoàn thành bài toán lớn thì ñược biểu diễn thành cung AND chỉ ñến N trạng thái con  Nhiều cách giải cho bài toán có thể ñược dùng thì có thể biểu diễn bởi cung OR A có thể ñược thông qua hai cách: - Giải B, hoặc - Giải cả C và D 25 Thu giảm bài toán (tt)
ðồ thị AND-OR :  Nếu dùng giải thuật BFS cho việc tìm lời giải trên ñồ thị AND- OR thì có lẽ không thích hợp vì như xem xét ñồ thị sau:
Nếu giá trị ghi kề bên trạng thái là trị ước lượng cho trạng thái ñó.
Theo BFS thì trạng thái kế tiếp ñược chọn là C, như:  Khi chọn cách giải qua C thì bắt buộc phải giải cả D. Do vậy tổng chi phí cho cách giải này là: C+D+ 2 = 9, 2 là giá trị của hàm g trong BFS  Trong khi ñó nếu chọn cách giải qua B thì chi phí chỉ là: B+1 = 6. 26 Thu giảm bài toán (tt)
GT thu giảm bài toán  Khởi ñộng ñồ thị là TT bắt ñầu.  Lặp ñến khi: TT ñầu ñược gán nhãn là SOLVED OR chi phí vượt qua ngưỡng FUTILITY:
Duyệt ñồ thị bắt ñầu từ TT ñầu, theo con ñường tốt nhất hiện tại, tích luỹ tập trạng thái trên con ñường ñó mà nó chưa ñược mở rộng hoặc ñược gán nhãn SOLVED.
Lấy một TT chưa mở rộng và mở rộng nó. Nếu không có con thì gán FUTILITY bằng trị của TT này. Ngược lại, thêm các con vào ñồ thị và mỗi chúng tính f’ (sử dụng chỉ h’, bỏ qua g). Nếu f’ =0 thì gán nhãn cho TT ñó là SOLVED.
Thay ñổi f’ của TT ñã ñược mở rộng ñể phản ánh thông tin ñược cung cấp bởi con của nó. Lan truyền trị này ngược lên ñồ thị. Nếu một TT có cung mà tất cả các con của nó ñã ñược gán nhãn SOLVED thì nó cũng ñược gán nhãn SOLVED. Khi lan truyền ngược lên ñồ thị ñánh dấu cung nào là tốt nhất như là phần của con ñường tốt nhất hiện tại. 27 Thu giảm bài toán (tt)
GT Thu giảm (tt.) - từng bước: 28 Thu giảm bài toán (tt)
GT Thu giảm (tt.) - từng bước: 29 Giải thuật cắt tỉa α-β
Tìm kiếm theo kiểu depth-first.
Nút MAX có 1 giá trị α (luôn tăng)
Nút MIN có 1 giá trị β (luôn giảm)
Tìm Kiếm có thể kết thúc dưới bất kỳ:  Nút MIN nào có β ≤ α của bất kỳ nút cha MAX nào.  Nút MAX nào có α ≥ β của bất kỳ nút cha MIN nào.
Giải thuật cắt tỉa α-β thể hiện mối quan hệ giữa các nút ở lớp n và n+2, mà tại ñó toàn bộ cây có gốc tại lớp n+1 có thể cắt bỏ. 30 Cắt tỉa α (vị trí MAX) S A C MAX MIN B Có giá trị >= α α - cut Có giá trị = α MAX Có giá trị <= k Có giá trị = k X Y . Z ðiều kiện 1: Chỉ cần biết giá trị tại A và B ðiều kiện 2: Giá trị A > giá trị B ðiều kiện 3: X, Y, .. , Z ở vị trí Max Bỏ những cây con có gốc là X,Y,, Z 31 Cắt tỉa β (vị trí Min) S A C MIN MAX B β - cut MIN Có giá trị = β Có giá trị <= β Có giá trị = k Có giá trị >= k X Y . Z ðiều kiện 1: Chỉ cần biết giá trị tại A và B ðiều kiện 2: Giá trị A < giá trị B ðiều kiện 3: X, Y, .. , Z ở vị trí Min Bỏ những cây con có gốc là X,Y,, Z 32 Cắt tỉa α-β: ví dụ 33 Bài tập: bài 1 (trò ñố 8 ô như) Dùng các hàm lượng giá heuristic sau
h1 = số lượng các vị trí sai khác so với trạng thái goal.
h2 = tổng số ñộ dời ngắn nhất của các ô về vị trí ñúng (khoảng cách Manhattan) hãy triển khai không gian trạng thái của bài toán ñến mức 5 (nếu chưa tìm ñược goal): a) Theo giải thuật leo núi b) Theo giải thuật tìm kiếm rộng c) Theo giải thuật tìm kiếm sâu d) Theo giải thuật tìm kiếm tốt nhất ñầu tiên 458 76 321 Start 567 48 321 Goal 34 Trong cây tìm kiếm dưới ñây, mỗi nút có 2 giá trị ñi kèm: giá trị bên trái của nút (in nghiêng) thể hiện giá trị heuristic của nút, và giá trị bên phải nút thể hiện thứ tự nút ñược duyệt qua. Với mỗi chiến lược tìm kiếm dưới ñây, hãy viết danh sách thứ tự các nút ñược duyệt, so sánh và cho biết ta ñã dùng giải thuật tìm kiếm nào trên cây : a) Tìm kiếm rộng BFS b) Tìm kiếm sâu DFS c) Tìm kiếm tốt nhất ñầu tiên BFS d) Tìm kiếm leo núi Bài tập: bài 2 (duyệt ñồ thị) 35 Kê danh sách các nút ñược duyệt theo tìm kiếm DFS.
Thực hiện giải thuật Minimax trên cây.
Sẽ có gì khác biệt nếu như ta dùng giải thuật cắt tỉa alpha – beta ñể ñịnh trị nút gốc cho cây? Bài tập: bài 3 (minimax)