intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Trí tuệ nhân tạo: Giải quết vấn đề - Nguyễn Nhật Quang (TT)

Chia sẻ: Nguyên Phương | Ngày: | Loại File: PDF | Số trang:67

Thêm vào BST
Báo xấu
78
lượt xem 10
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Trí tuệ nhân tạo - Giải quết vấn đề: Các chiến lược tìm kiếm với tri thức bổ sung" trình bày các nội dung: Tìm kiếm theo cấu trúc cây, tìm kiếm với tri thức bổ sung, các đặc điểm, các ước lượng chấp nhận được, các ước lượng kiên định, các giải thuật tìm kiếm cục bộ,... Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Trí tuệ nhân tạo: Giải quết vấn đề - Nguyễn Nhật Quang (TT)

  1. Trí Tuệ Nhân Tạo Nguyễn Nhật Quang quangnn-fit@mail.hut.edu.vn 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
  2. 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 g chắc chắn „ Học máy Trí tuệ nhân tạo 2
  3. Nhắc lại: Tìm kiếm theo cấu trúc cây „ Một ộ chiến lược ợ (p (phương gp pháp) 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
  4. Tìm kiếm với tri thức bổ sung g „ 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á giải Các ả thuật ậ tìm ì kiếm ế cục bộ ộ (Hill-climbing, ( S 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
  5. 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 best first search ‰ A* search Trí tuệ nhân tạo 5
  6. 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 ( chim bay”) bay ) từ thành phố hiện tại n đến Bucharest „ Phương pháp tìm kiếm Greedy best-first 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
  7. Greedyy best-first search – Ví dụ ((1)) Trí tuệ nhân tạo 7
  8. Greedy best-first search – Ví dụ (2) Trí tuệ nhân tạo 8
  9. Greedy best-first search – Ví dụ (3) Trí tuệ nhân tạo 9
  10. Greedy best-first search – Ví dụ (4) Trí tuệ nhân tạo 10
  11. Greedy best-first search – Ví dụ (5) Trí tuệ nhân tạo 11
  12. Greedy best-first search – Các đặc điểm „ Tính hoàn chỉnh? ‰ Không – Vì có thể vướng ớng (chết tắc) trong các vòng òng lặp kiểu kiể như: 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 g Trí tuệ nhân tạo 12
  13. 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 đị h ((cho h đến đế thời điểm điể hiện hiệ tại) t i) là có ó chi hi phí hí 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 p phí ước lượng ợ g 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
  14. A* search – Ví dụ (1) Trí tuệ nhân tạo 14
  15. A* search – Ví dụ (2) Trí tuệ nhân tạo 15
  16. A* search – Ví dụ (3) Trí tuệ nhân tạo 16
  17. A* search – Ví dụ (4) Trí tuệ nhân tạo 17
  18. A* search – Ví dụ (5) Trí tuệ nhân tạo 18
  19. A* search – Ví dụ (6) Trí tuệ nhân tạo 19
  20. 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á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 Nế khô gian i cácá ttrạng thái là vô ôhhạn, thì giải iải th thuật ậ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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2