Bài giảng Trí tuệ nhân tạo - Bài 4: Giải quyết vấn đề. Tìm kiếm (Tiếp theo) - Thân Quang Khoát
Trí Tuệ Nhân Tạo
(Artificial Intelligence)
Thân Quang Khoát
Viện Công nghệ thông tin và Truyền thông
Trường Đại Học Bách Khoa Hà Nội
Năm học 2020
Nội dung môn học:
n Giới thiệu về Trí tuệ nhân tạo
n Tác tử
n Giải quyết vấn đề: Tìm kiếm, Thỏa mãn ràng buộc
q Tìm kiếm với tri thức bổ sung (Informed search)
n Logic và suy diễn
n Biểu diễn tri thức
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
n 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
n 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
q 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ớ)
n 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
q Các giải thuật tìm kiếm best-first (Greedy best-first, A*)
q Các giải thuật tìm kiếm cục bộ (Hill-climbing, Simulated annealing,
Local beam, Genetic algorithms)
q 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
n Ý 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
q Để đá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
n Cài đặt giải thuật
q 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
n Các trường hợp đặc biệt của giải thuật Best-first search
q Greedy best-first search
q A* search
Trí tuệ nhân tạo
5
Greedy best-first search
n Hàm đánh giá f(n) là hàm heuristic h(n)
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)
n 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
n 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
n Tính hoàn chỉnh?
q 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 à…
n Độ phức tạp về thời gian?
q O(bm)
q Một hàm heuristic tốt có thể mang lại cải thiện lớn
n Độ phức tạp về bộ nhớ?
q O(bm) – Lưu giữ tất cả các nút trong bộ nhớ
n Tính tối ưu?
q Không
Trí tuệ nhân tạo
12
A* search
n Ý 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
n Sử dụng hàm đánh giá f(n) = g(n) + h(n)
q g(n) = chi phí từ nút gốc cho đến nút hiện tại n
q h(n) = chi phí ước lượng từ nút hiện tại n tới đích
q 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 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 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 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
n Khi nào thì A* tối ưu?
Trí tuệ nhân tạo
20
Tải về để xem bản đầy đủ
67 trang
18340
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 (Tiếp theo) - Thân Quang Khoát", để 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_tiep_theo.pdf
