Bài giảng Trí tuệ nhân tạo: Giải quyết vấn đề bằng tìm kiếm - Trường Đại học Thủy Lợi

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:34

Thêm vào BST

Báo xấu

35
lượt xem 5
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”, một môn cơ sở chuyên ngành trong chương trình đào tạo cử nhân tin học, ngoài mục đích xây dựng nhiều bài giảng trên một khung chương trình đào tạo, mà còn giúp cho sinh viên có tài liệu học tập phù hợp với hoàn cảnh thực tế của Đại học Thủy Lợi. Nội dung Chương 2a của tài liệu trình bày Giải quyết vấn đề bằng tìm kiếm.

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 quyết vấn đề bằng tìm kiếm - Trường Đại học Thủy Lợi

Giải quyết vấn đề bằng tìm kiếm Russell and Norvig 3rd ed., chap. 3.1-3.2 1
Các trò chơi đố! 2
Bài toán ba thầy tu và ba con quỷ  Mục tiêu: đưa tất cả người và quỷ sang bờ phải của con sông an toàn.  Điều kiện: □ Nếu số người ở mỗi bờ ít hơn số quỷ thì người sẽ bị quỷ ăn thịt □ Mỗi lượt thuyền chỉ chở được nhiều nhất 2 người và không được trống 3
Biểu diễn bài toán  Một biểu diễn trạng thái cho phép mô tả trạng thái và mục tiêu của bài toán: (ML, CL, B) ML: số lượng thầy tu ở bờ trái CL: số lượng quỷ ở bờ trái B: vị trí của con thuyền  Trạng thái ban đầu: (3,3,L) Mục tiêu: (0,0,R) 4
Tác nhân giải quyết bài toán  Biểu diễn bài toán □ Các trạng thái và hành động (hàm kế vị).  Biểu diễn mục tiêu □ Trạng thái mong muốn của thế giới.  Tìm kiếm □ Xác định chuỗi các hành động có thể có để dẫn tới các trạng thái đã biết giá trị và sau đó chọn chuỗi tốt nhất.  Thực thi □ Căn cứ vào giải pháp, thực hiện các hành động.  Giả định: □ Môi trường là có thể quan sát đầy đủ, xác định trước □ Tác nhân biết ảnh hưởng của các hành động của nó 5
Biểu diễn đồ thị của bài toán  Các nút: Tất cả các trạng thái có thể có  Các cạnh: có cạnh từ trạng thái u tới trạng thái v nếu v là có thể đạt đến từ u (bằng một hành động của tác nhân)  Các cạnh của bài toán 3 thầy tu và 3 con quỷ?  Bài toán bây giờ là tìm một đường đi từ (3,3,L) tới (0,0,R).  Thông thường, các đường đi sẽ có thông tin chi phí đi kèm, do vậy bài toán sẽ là tìm đường đi có chi phí thấp nhất từ trạng thái ban đầu đến đích. 6
Biểu diễn vấn đề như một bài toán tìm kiếm  Không gian trạng thái S (các nút)  Hàm kế vị: các trạng thái có thể di chuyển tới bằng cách thực hiện một hành động (cạnh) từ trạng thái hiện tại  Trạng thái ban đầu  Kiểm tra mục tiêu liệu trạng thái x có phải là đích không?  Chi phí 7
Quay trở lại bài toán ban đầu 33L CCR CR CMR 31R 32R 22R Các hành động (các thao tác): CCR – chuyển hai con quỷ sang bờ phải MCL – chuyển một thầy tu và một con quỷ sang bờ trái Tổng cộng có bao nhiêu hành động? Tại sao không có MMR từ trạng thái này? 8
Đồ thị tìm kiếm (mở rộng một phần) 33L CCR CR CMR 31R 32R 22R CL CCL CL ML 32L 33L 33L 32L CCR CR MR MCR 30R 31R 22R 21R CCL CR 32L 31L Các hành động: CCR – chuyển hai con quỷ sang bờ phải MCL – chuyển một thầy tu và một con quỷ sang bờ trái 9
Các trạng thái lặp 33L 31R 32R 22R 32L 33L 33L 32L 30R 31R 22R 21R 32L 31L Đồ thị tìm kiếm không nhất thiết là một cây! 10
Tìm kiếm không gian trạng thái  Thông thường việc xây dựng một biểu diễn hoàn chỉnh của đồ thị trạng thái là không khả thi (hoặc quá đắt)  Một bộ giải quyết vấn đề phải tìm ra một giải pháp bằng cách khám phá một phần nhỏ của đồ thị 11
Tìm kiếm không gian trạng thái Cây tìm kiếm 12
Tìm kiếm không gian trạng thái Cây tìm kiếm 13
Tìm kiếm không gian trạng thái Cây tìm kiếm 14
Tìm kiếm không gian trạng thái Cây tìm kiếm 15
Tìm kiếm không gian trạng thái Cây tìm kiếm 16
Trò chơi 8 miếng ghép  Các trạng thái?  Trạng thái ban đầu?  Các hành động?  Kiểm tra mục tiêu?  Chi phí đường đi? 17
Trò chơi 8 miếng ghép  Các trạng thái? Vị trí của mỗi quân  Trạng thái ban đầu? Bất kỳ trạng thái nào  Các hành động? (quân, hướng) trong đó hướng là một trong {Trái, Phải, Trên, Dưới}  Kiểm tra mục tiêu? Kiểm tra liệu đã đạt được cấu hình đích hay chưa  Chi phí đường đi? Số lượng các hành động để đạt tới đích  Đồ thị tìm kiếm có phải là một cây? 18
Trò chơi (n2-1) miếng ghép …. 8 2 1 2 3 4 3 4 7 5 6 7 8 5 1 6 9 10 11 12 13 14 15 19
Trò chơi 15 miếng ghép • Sam Loyd đã treo giải $1,000 cho người đầu tiên giải được bài toán sau đây: 1 2 3 4 1 2 3 4 5 6 7 8 ? 5 6 7 8 9 10 11 12 9 10 11 12 13 14 15 13 15 14 20