Bài giảng Trí tuệ nhân tạo - Bài 3: Giải quyết vấn đề Tìm kiếm, Thỏa mãn ràng buộc (Phần 1) - 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
Các chiến lược tìm kiếm cơ bản (Uninformed 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
Giải quyết vấn đề bằng tìm kiếm
Giải quyết vấn đề bằng tìm kiếm
Tìm chuỗi các hành động cho phép đạt đến (các) trạng thái mong muốn
Các bước chính
Xác định mục tiêu cần đạt đến (goal formulation)
Là một tập hợp của các trạng thái (đích)
Dựa trên: trạng thái hiện tại (của môi trường) và đánh giá hiệu quả hành động
(của tác tử)
Phát biểu bài toán (problem formulation)
Với một mục tiêu, xác định các hành động và trạng thái cần xem xét
Quá trình tìm kiếm (search process)
Xem xét các chuỗi hành động có thể
Chọn chuỗi hành động tốt nhất
Giải thuật tìm kiếm
Đầu vào: một bài toán (cần giải quyết)
Đầu ra: một giải pháp, dưới dạng một chuỗi các hành động cần thực hiện
Trí tuệ nhân tạo
3
Tác tử giải quyết vấn đề
Trí tuệ nhân tạo
4
Giải quyết vấn đề bằng tìm kiếm
Một người du lịch đang trong chuyến đi du lịch ở Rumani
Anh ta hin thời đang Arad
Ngày mai, anh ta có chuyến bay khởi hành từ Bucharest
Bây giờ, anh ta cần di chuyển (lái xe) từ Arad đến Bucharest
Phát biểu mục tiêu:
Cần phải có mặt ở Bucharest
Phát biểu bài toán:
Các trạng thái: các thành phố (đi qua)
Các hành động: lái xe giữa các thành phố
Tìm kiếm giải pháp:
Chuỗi các thành phố cần đi qua, ví dụ: Arad, Sibiu, Fagaras,
Trí tuệ nhân tạo
5
Giải quyết vấn đề bằng tìm kiếm
Trí tuệ nhân tạo
6
Các kiểu bài toán
Xác định, có thể quan sát hoàn toàn Æ Bài toán trạng thái
đơn
Tác tử biết chính xác trạng thái tiếp theo mà nó sẽ chuyển qua
Giải pháp của bài toán: một chuỗi hành động
Không quan sát được Æ Bài toán thiếu cảm nhận
Tác tử có thể không biết là nó đang ở trạng thái nào
Giải pháp của bài toán: một chuỗi hành động
Không xác định và/hoặc có thể quan sát một phần Æ Bài
toán có sự kiện ngẫu nhiên
Các nhận thức cung cấp các thông tin mới về trạng thái hiện tại
Giải pháp của bài toán: một kế hoặch (chính sách)
Thường kết hợp đan xen giữa: tìm kiếm và thực hiện
Trí tuệ nhân tạo
7
Ví dụ: Bài toán máy hút bụi (1)
Nếu là bài toán trạng thái
đơn
Bắt đầu ở trạng thái #5.
Giải pháp?
Trí tuệ nhân tạo
8
Ví dụ: Bài toán máy hút bụi (2)
Nếu là bài toán trạng thái
đơn
Bắt đầu ở trạng thái #5.
Giải pháp?
[Sang phải, Hút bụi]
Trí tuệ nhân tạo
9
Ví dụ: Bài toán máy hút bụi (3)
Nếu là bài toán thiếu cảm
nhận
Bắt đầu (có thể) ở trạng thái
{#1,#2,#3,#4,#5,#6,#7,#8}
Luôn bắt đầu bằng di chuyển
sang phải
Giải pháp?
Trí tuệ nhân tạo
10
Ví dụ: Bài toán máy hút bụi (4)
Nếu là bài toán thiếu cảm
nhận
Bắt đầu (có thể) ở trạng thái
{#1,#2,#3,#4,#5,#6,#7,#8}
Luôn bắt đầu bằng di chuyển
sang phải
Giải pháp?
[Sang phải, Hút bụi, Sang trái,
Trí tuệ nhân tạo
11
Ví dụ: Bài toán máy hút bụi (5)
Nếu là bài toán có sự kiện
ngẫu nhiên
Bắt đầu ở trạng thái #5
làm bẩn một cái thảm sạch!
Có thể quan sát một phần: vị
thời
Trí tuệ nhân tạo
12
Ví dụ: Bài toán máy hút bụi (6)
Nếu là bài toán có sự kiện
ngẫu nhiên
Bắt đầu ở trạng thái #5
làm bẩn một cái thảm sạch!
Có thể quan sát một phần: vị
thời
[Sang phải, if Bẩn then Hút
bụi]
Trí tuệ nhân tạo
13
Phát biểu bài toán trạng thái đơn
Bài toán được định nghĩa bởi 4 thành phần:
Trạng thái đầu
Ví dụ: “đang ở thành phố Arad“
Các hành động – Xác định bởi hàm chuyển trạng thái:
S(trạng_thái_hiện_thời) = tập các cặp <hành_động, trạng_thái_tiếp_theo>
Ví dụ: S(Arad) = {<Arad Æ Zerind, Zerind>, … }
Kiểm tra mục tiêu, có thể là
Trc ti: Trng thái hin thi = “thành phBucharest"
Gián tiếp – ví dụ: HếtCờ(x), Sạch(x), …
Chi phí đường đi (giải pháp)
n,…
c(x,a,y) ≥ 0 là chi phí bước (bộ phận) – chi phí cho việc áp dụng hành
động a để chuyển từ trạng thái x sang trạng thái y
đầu đến trạng thái đích
Trí tuệ nhân tạo
14
Xác định không gian trạng thái
Các bài toán thực tế thường được mô tả phức tạp
Æ Không gian trạng thái cần được khái quát (abstracted) để phục
vụ cho việc giải quyết bài toán
Trạng thái (khái quát) = Một tập các trạng thái thực tế
Hành động (khái quát) = Một kết hợp phức tạp của các hành
động thực tế
Ví dụ: Hành động "Arad Æ Zerind" biểu diễn một tập kết hợp các
đường, đường vòng, chỗ nghỉ, …
Để đảm bảo việc thực hiện (quá trình tìm kiếm), bất kỳ trạng
thực tế khác
Giải pháp (khái quát) = Một tập các đường đi giải pháp trong
thực tế
Trí tuệ nhân tạo
15
Đồ thị không gian trạng thái (1)
Bài
toán
hút
bụi
Các trạng thái?
Các hành động?
Kiểm tra mục tiêu?
Chi phí đường đi?
Trí tuệ nhân tạo
16
Đồ thị không gian trạng thái (2)
Bài
toán
hút
bụi
Các trạng thái?
Các hành động?
Chỗ bẩn và vị trí máy hút bụi
Sang trái, sang phải, hút bụi, không làm gì
Kiểm tra mục tiêu? Không còn chỗ (vị trí) nào bẩn
Chi phí đường đi? 1 (mỗi hành động), 0 (không làm gì cả)
Trí tuệ nhân tạo
17
Ví dụ: Bài toán ô chữ (1)
Bài toán ô
chữ 8 số
Các trạng thái?
Kiểm tra mục tiêu?
Chi phí đường đi?
Trí tuệ nhân tạo
18
Ví dụ: Bài toán ô chữ (2)
Bài toán ô
chữ 8 số
Các trạng thái?
Các vị trí của các ô số
, ,
lên trên, xuống dưới
Kiểm tra mục tiêu? Đạt trạng thái đích (goal state)
Chi phí đường đi? 1 cho mỗi di chuyển
Trí tuệ nhân tạo
19
Các giải thuật tìm kiếm theo cấu trúc cây
n0
Ý tưởng:
Khám phá (xét) không gian trạng thái
bằng cách sinh ra các trạng thái kế tiếp
n
của các trạng thái đã khám phá (đã xét)
Còn gọi là phương pháp khai triển (phát
triển) các trạng thái
successors(n)
Goal
Trí tuệ nhân tạo
20
Tải về để xem bản đầy đủ
64 trang
31681
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 3: Giải quyết vấn đề Tìm kiếm, Thỏa mãn ràng buộc (Phần 1) - 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_3_giai_quyet_van_de_tim_kiem.pdf
