Chương 1. Tổng quan Chương 2. Tác tử thông minh Chương 3. Giải quyết vấn đề 3.
Tìm kiếm với tri thức bổ sung 3. Tìm kiếm dựa trên thỏa mãn ràng buộc Chương 4. Tri thức và suy diễn Chương 5. Học máy 2 Nhắc lại: Tìm kiếm theo cấu trúc cây ◼ Một chiến lược (phương pháp) tìm kiếm = Một cách xác định thứ tự xét các nút của cây Trí tuệ nhân tạo 3 Tìm kiếm với tri thức bổ sung ◼ Các chiến lược tìm kiếm cơ bản (uninformed search strategies) chỉ sử dụng các thông tin chứa trong định nghĩa của bài toán ❑ Không phù hợp với nhiều bài toán thực tế (do đòi hỏi chi phí quá cao về thời gian và bộ nhớ) ◼ Các chiến lược tìm kiếm với tri thức bổ sung (informed search strategies) sử dụng các tri thức cụ thể của bài toán → Quá trình tìm kiếm hiệu quả hơn ❑ Các giải thuật tìm kiếm best-first (Greedy best-first, A*) ❑ Các giải thuật tìm kiếm cục bộ (Hill-climbing, Simulated annealing, Local beam, Genetic algorithms) ❑ Các giải thuật tìm kiếm đối kháng (MiniMax, Alpha-beta pruning) Trí tuệ nhân tạo 4 Best-first search ◼ Ý tưởng: Sử dụng một hàm đánh giá f(n) cho mỗi nút của cây tìm kiếm ❑ Để đánh giá mức độ “phù hợp” của nút đó → Trong quá trình tìm kiếm, ưu tiên xét các nút có mức độ phù hợp cao nhất ◼ Cài đặt giải thuật ❑ Sắp thứ tự các nút trong cấu trúc fringe theo trật tự giảm dần về mức độ phù hợp ◼ Các trường hợp đặc biệt của giải thuật Best-first search ❑ Greedy best-first search ❑ A* search Trí tuệ nhân tạo 5 Greedy best-first search ◼ Hàm đánh giá f(n) là hàm heuristic h(n) ◼ Hàm heuristic h(n) đánh giá chi phí để đi từ nút hiện tại n đến nút đích (mục tiêu) ◼ Ví dụ: Trong bài toán tìm đường đi từ Arad đến Bucharest, sử dụng: hSLD(n) = Ước lượng khoảng cách đường thẳng (“chim bay”) từ thành phố hiện tại n đến Bucharest ◼ Phương pháp tìm kiếm Greedy best-first search sẽ xét (phát triển) nút “có vẻ” gần với nút đích (mục tiêu) nhất Trí tuệ nhân tạo 6 Greedy best-first search – Ví dụ (1) Trí tuệ nhân tạo 7 Greedy best-first search – Ví dụ (2) Trí tuệ nhân tạo 8 Greedy best-first search – Ví dụ (3) Trí tuệ nhân tạo 9 Greedy best-first search – Ví dụ (4) Trí tuệ nhân tạo 10 Greedy best-first search – Ví dụ (5) Trí tuệ nhân tạo 11 Greedy best-first search – Các đặc điểm ◼ Tính hoàn chỉnh? ❑ Không – Vì có thể vướng (chết tắc) trong các vòng lặp kiểu như: Iasi → Neamt → Iasi → Neamt →… ◼ Độ phức tạp về thời gian? ❑ O(bm) ❑ Một hàm heuristic tốt có thể mang lại cải thiện lớn ◼ Độ phức tạp về bộ nhớ? ❑ O(bm) – Lưu giữ tất cả các nút trong bộ nhớ ◼ Tính tối ưu? ❑ Không Trí tuệ nhân tạo 12 A* search ◼ Ý tưởng: Tránh việc xét (phát triển) các nhánh tìm kiếm đã xác định (cho đến thời điểm hiện tại) là có chi phí cao ◼ Sử dụng hàm đánh giá f(n) = g(n) + h(n) ❑ g(n) = chi phí từ nút gốc cho đến nút hiện tại n ❑ h(n) = chi phí ước lượng từ nút hiện tại n tới đích ❑ f(n) = chi phí tổng thể ước lượng của đường đi qua nút hiện tại n đến đích Trí tuệ nhân tạo 13 A* search – Ví dụ (1) Trí tuệ nhân tạo 14 A* search – Ví dụ (2) Trí tuệ nhân tạo 15 A* search – Ví dụ (3) Trí tuệ nhân tạo 16 A* search – Ví dụ (4) Trí tuệ nhân tạo 17 A* search – Ví dụ (5) Trí tuệ nhân tạo 18 A* search – Ví dụ (6) Trí tuệ nhân tạo 19 LS n h(n) LC QN 20 17 90 HN 50 ST 60 HB 15 LC 75 ST 5 30 7 HB 65 HP HN 15 10 LS 70 10 NĐ 10 TB HP 80 15 90 QN 80 100 15 NB 80 TB 55 25 NĐ 45 NB 20 TH TH 15 15 V 0 V h(n): khoảng cách đường chim bay HN → V A* search: các đặc điểm ◼ Nếu không gian các trạng thái là hữu hạn và có giải pháp để tránh việc xét (lặp) lại các trạng thái, thì giải thuật A* là hoàn chỉnh (tìm được lời giải) – nhưng không đảm bảo là tối ưu ◼ Nếu không gian các trạng thái là hữu hạn và không có giải pháp để tránh việc xét (lặp) lại các trạng thái, thì giải thuật A* là không hoàn chỉnh ◼ Nếu không gian các trạng thái là vô hạn, thì giải thuật A* là không hoàn chỉnh ◼ Khi nào thì A* tối ưu? Trí tuệ nhân tạo 21 Các ước lượng chấp nhận được ◼ Một ước lượng h(n) được xem là chấp nhận được nếu đối với mọi nút n: 0 ≤ h(n) ≤ h*(n), trong đó h*(n) là chi phí thật (thực tế) để đi từ nút n đến đích ◼ Một ước lượng chấp nhận được không bao giờ đánh giá quá cao (overestimate) đối với chi phí để đi tới đích ❑ Thực chất, ước lượng chấp nhận được có xu hướng đánh giá “lạc quan” ◼ Ví dụ: Ước lượng hSLD(n) đánh giá thấp hơn khoảng cách đường đi thực tế ◼ Định lý: Nếu h(n) là đánh giá chấp nhận được, thì phương pháp tìm kiếm A* sử dụng giải thuật TREE- SEARCH là tối ưu Trí tuệ nhân tạo 22 Tính tối ưu của A* - Chứng minh (1) ◼ Giả sử có một đích không tối ưu (suboptimal goal) G2 được sinh ra và lưu trong cấu trúc fringe.
Gọi n là một nút chưa xét trong cấu trúc fringe sao cho n nằm trên một đường đi ngắn nhất đến một đích tối ưu (optimal goal) G ◼ ◼ Ta có: 1) f(G2) = g(G2) vì h(G2) = 0 ◼ Ta có: 2) g(G2) > g(G) vì G2 là đích không tối ưu ◼ Ta có: 3) f(G) = g(G) vì h(G) = 0 ◼ Từ 1)+2)+3) suy ra: 4) f(G2) > f(G) Trí tuệ nhân tạo 23 Tính tối ưu của A* - Chứng minh (2) ◼ Ta có: 5) h(n) ≤ h*(n) vì h là ước lượng chấp nhận được ◼ Từ 5) suy ra: 6) g(n) + h(n) ≤ g(n) + h*(n) ◼ Ta có: 7) g(n) + h*(n) = f(G) vì n nằm trên đường đi tới G ◼ Từ 6)+7) suy ra: 8) f(n) ≤ f(G) ◼ Từ 4)+8) suy ra: f(G2) > f(n). Tức là, giải thuật A* không bao giờ xét G2 Trí tuệ nhân tạo 24 Các ước lượng chấp nhận được (1) Ví dụ đối với trò chơi ô chữ 8 số: ◼ h1(n) = số các ô chữ nằm ở sai vị trí (so với vị trí của ô chữ đấy ở trạng thái đích) ◼ h2(n) = khoảng cách dịch chuyển (,→,,) ngắn nhất để dịch chuyển các ô chữ nằm sai vị trí về vị trí đúng ◼ h1(S) = ? ◼ h2(S) = ? Trí tuệ nhân tạo 25 Các ước lượng chấp nhận được (2) Ví dụ đối với trò chơi ô chữ 8 số: ◼ h1(n) = số các ô chữ nằm ở sai vị trí (so với vị trí của ô chữ đấy ở trạng thái đích) ◼ h2(n) = khoảng cách dịch chuyển (,→,,) ngắn nhất để dịch chuyển các ô chữ nằm sai vị trí về vị trí đúng ◼ h1(S) = 8 ◼ h2(S) = 3+1+ 2+2+ 2+3+3+2 = 18 Trí tuệ nhân tạo 26 Trò chơi Tic-tac-toe KGTT của tic-tac-toe được thu nhỏ nhờ tính đối xứng của các trạng thái Phép đo heuristic Chiếm 3 đường Chiếm 4 đường Chiếm 2 đường Heuristic “Số đường thắng nhiều nhất” áp dụng cho các nút con đầu tien trong tic-tac-toe. Phép đo heuristic 29 Ước lượng ưu thế ◼ Ước lượng h2 được gọi là ưu thế hơn / trội hơn (dominate) ước lượng h1 nếu: ❑ h*(n) ≥ h2(n) ≥ h1(n) đối với tất cả các nút n ◼ Nếu ước lượng h2 ưu thế hơn ước lượng h1, thì h2 tốt hơn (nên được sử dụng hơn) cho quá trình tìm kiếm ◼ Trong ví dụ (ô chữ 8 số) ở trên: Chi phí tìm kiếm = Số lượng trung bình của các nút phải xét: ❑ Với độ sâu d =12 ◼ IDS (Tìm kiếm sâu dần): 3.641 nút phải xét Trí tuệ nhân tạo 30 Các ước lượng kiên định ◼ Một ước lượng h được xem là kiên định (consistent), nếu với mọi nút n và với mọi nút tiếp theo n' của n (được sinh ra bởi hành động a): h(n) ≤ c(n,a,n') + h(n') ◼ Nếu ước lượng h là kiên định, ta có: f(n') = g(n') + h(n') = g(n) + c(n,a,n') + h(n') ≥ g(n) + h(n) = f(n) Nghĩa là: f(n) không giảm trong bất kỳ đường đi (tìm kiếm) nào đi qua n ◼ Định lý: Nếu h(n) là kiên định, thì phương pháp tìm kiếm A* sử dụng giải thuật GRAPH-SEARCH là tối ưu Trí tuệ nhân tạo 31 Các đặc điểm của A* ◼ Tính hoàn chỉnh? ❑ Có (trừ khi có rất nhiều các nút có chi phí f ≤ f(G) ) ◼ Độ phức tạp về thời gian? ❑ Bậc của hàm mũ – Số lượng các nút được xét là hàm mũ của độ dài đường đi của lời giải ◼ Độ phức tạp về bộ nhớ? ❑ Lưu giữ tất cả các nút trong bộ nhớ ◼ Tính tối ưu? ❑ Có (đối với điều kiện đặc biệt) Trí tuệ nhân tạo 32 A* vs. UCS ◼ Tìm kiếm với chi phí cực ◼ Tìm kiếm A* phát triển chủ yếu tiểu (UCS) phát triển theo theo hướng tới đích, nhưng mọi hướng đảm bảo tính tối ưu Trí tuệ nhân tạo 33 Các giải thuật tìm kiếm cục bộ ◼ Trong nhiều bài toán tối ưu, các đặc điểm thường phức tạp và ta không thể tìm được lời giải tối ưu.
❑ Trạng thái đích = Lời giải của bài toán phải thoả mãn ràng buộc nào đó. ◼ Ví dụ: Bài toán n quân hậu (bố trí n quân hậu trên một bàn cờ kích thước nxn, sao cho các quân hậu không ăn nhau) ❑ Bài toán tối ưu có nhiều điểm cực trị địa phương. ◼ Trong những bài toán như thế, chúng ta có thể sử dụng các giải thuật tìm kiếm cục bộ ◼ Tại mỗi thời điểm, chỉ lưu một trạng thái “hiện thời" duy nhất.