Bài giảng Trí tuệ nhân tạo - Bài 4: Giải quyết vấn đề Tìm kiếm, Thỏa mãn ràng buộc (Phần 2) - Nguyễn Nhật Quang
Trí Tuệ Nhân Tạo
Nguyễn Nhật Quang
Trường Đại học Bách Khoa Hà Nội
Viện Công nghệ Thông tin và Truyền thông
Năm học 2012-2013
Nội dung môn học:
Giới thiệu về Trí tuệ nhân tạo
Tác tử
Giải quyết vấn đề: Tìm kiếm, Thỏa mãn ràng buộc
Tìm kiếm với tri thức bổ sung (Informed search)
Logic và suy diễn
Biểu diễn tri thức
Biểu diễn tri thức không chắc chắn
Học máy
Trí tuệ nhân tạo
2
Nhắc lại: Tìm kiếm theo cấu trúc cây
Mt chiến lc (phương pháp) tìm kiếm = Mt 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
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
Để đá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
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á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 Æ…
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?
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
= chi phí ước lng từ nút hin ti 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
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 (không đảm bảo tìm được
lời giải)
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 (không đảm bảo tìm được lời giải)
Trí tuệ nhân tạo
20
Tải về để xem bản đầy đủ
67 trang
24060
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Trí tuệ nhân tạo - Bài 4: Giải quyết vấn đề Tìm kiếm, Thỏa mãn ràng buộc (Phần 2) - Nguyễn Nhật Quang", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_tri_tue_nhan_tao_bai_4_giai_quyet_van_de_tim_kiem.pdf
