Giáo trình Trí tuệ nhân tạo - Chương 2, Phần a: Giải quyết vấn đề bằng tìm kiếm - Lý Anh Tuấn
Các giả định trong tìm kiếm
căn bản
Thế giới là tĩnh
Thế giới là có thể rời rạc hóa
Thế giới là có thể quan sát đầy đủ
Các hành động là xác định trước
Tuy nhiên nhiều giả định này có thể bị loại bỏ, và
tìm kiếm tiếp tục là một công cụ giải quyết vấn
đề quan trọng
32Tìm kiếm và AI
Các phương pháp tìm kiếm có mặt mọi chỗ mọi nơi trong các
hệ thống AI. Chúng thường là xương sống cho cả các mô đun
lõi và các mô đun ngoại vi
Một rô bốt tự hành sử dụng tìm kiếm để quyết định thực hiện
hành động nào và thi hành thao tác cảm biến nào, để nhanh
chóng lường trước sự va chạm, để lập kế hoạch đường đi,.
Các công ty hậu cần sử dụng tìm kiếm để định vị các tài
nguyên, lập kế hoạch lộ trình, sắp lịch cho nhân viên
Các tác nhân hoặc các thành phần trong trò chơi sử dụng tìm
kiếm để điều hướng, lựa chọn nước đi, lường trước các hành
động của tác nhân khác, và quyết định các hành động của
bản thân nó.
33Các ứng dụng
Tìm kiếm đóng vai trò chính trong nhiều ứng
dụng, ví dụ:
□ Tìm đường (bản đồ trực tuyến, internet, hàng không)
□ Bài trí VLSI
□ Điều hướng rô bốt
□ Thiết kế dược phẩm, thiết kế protein
□ Các trò chơi video
34 trang |
Chia sẻ: thucuc2301 | Lượt xem: 754 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Giáo trình Trí tuệ nhân tạo - Chương 2, Phần a: Giải quyết vấn đề bằng tìm kiếm - Lý Anh Tuấn, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
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
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?
33L
32R 31R 22R
CCR CR CMR
8
Đồ thị tìm kiếm (mở rộng
một phần)
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
33L
32R
33L
21R
31R 22R
32L 33L 32L
30R 31R 22R
32L 31L
CCL
CCR CR CMR
CL
CCL CL ML
CCR
CR MR MCR
CR
9
Các trạng thái lặp
Đồ thị tìm kiếm không nhất thiết là một cây!
33L
32R
33L
21R
31R 22R
32L 33L 32L
30R 31R 22R
32L 31L
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
3 4 7
5 1 6
1 2 3 4
5 6 7 8
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
5 6 7 8
9 10 11 12
13 14 15
1 2 3 4
5 6 7 8
9 10 11 12
13 15 14
?
20
Nhưng đã không có ai thắng giải !!
21
Tại sao?
22
Giải pháp cho bài toán tìm kiếm
Một giải pháp là một đường đi kết nối nút ban đầu với
một nút đích (bất kỳ nút đích nào)
I
G
23
Giải pháp cho bài toán tìm kiếm
Một giải pháp là một đường đi kết nối nút ban đầu tới
một nút đích (bất kỳ nút đích nào)
Chi phí đường đi là tổng các chi phí cung dọc theo
đường đi
Giải pháp tối ưu là đường đi giải pháp có chi phí tối thiểu
Có thể không có
giải pháp!
I
G
24
Chi phí đường đi
Chi phí cạnh là một số dương đại diện cho chi
phí thực hiện hành động tương ứng với cạnh, ví
dụ:
□ 1 trong ví dụ trò chơi 8 miếng ghép
Chúng ta giả sử rằng với bất kỳ bài toán nào chi
phí c của một cung luôn luôn thỏa mãn:
𝑐 ≥ 𝜀 > 0, trong đó 𝜀 là một hằng
□ Tại sao? Phải làm việc được với chi phí của các
đường đi dài tùy ý
25
Trạng thái đích
Nó có thể được mô tả một cách rõ ràng:
hoặc được mô tả một phần:
hoặc được mô tả bởi một điều kiện,
ví dụ, tổng các số trên tất cả các hàng, tất cả các cột, và
tất cả các đường chéo đều bằng 30
1 2 3
4 5 6
7 8 1 a a
a 5 a
a 8 a
15 1 2 12
4 10 9 7
8 6 5 11
3 13 14
(“a” đại diện cho một số
“bất kỳ” khác 1, 5 và 8)
26
Ví dụ khác: Bài toán quân 8 hậu
Biểu diễn gia tăng và biểu diễn trạng thái hoàn
chỉnh:
□ Biểu diễn gia tăng bắt đầu với một trạng thái trống và
bao gồm các thao tác làm gia tăng mô tả trạng thái.
□ Biểu diễn trạng thái hoàn chỉnh bắt đầu với tất cả 8
quân hậu trên bàn cờ và di chuyển chúng vòng
quanh
27
Bài toán 8 quân hậu:
sự biểu diễn là chìa khóa!
Biểu diễn gia tăng
Các trạng thái? Bất kỳ sự sắp xếp nào gồm từ 0 đến 8 quân hậu
trên bàn cờ
Trạng thái bắt đầu? Không có quân hậu nào
Các hành động? Thêm các quân hậu vào các ô trống
Kiểm tra mục tiêu? 8 quân hậu trên bàn cờ và không ăn lẫn
nhau
Chi phí đường đi? Không có
64 x 63 x 57 ~ 3 x 1014 trạng thái để khám phá
Đồ thị tìm kiếm có phải là một cây không?
28
Một biểu diễn tốt hơn
Một biểu diễn gia tăng khác:
Các trạng thái? n (giữa 0 và 8) quân hậu trên bàn cờ, mỗi quân
nằm trên mỗi cột trong n cột bên trái; các quân hậu không ăn lẫn
nhau.
Trạng thái ban đầu? Không có con hậu nào
Các hành động? Thêm hậu vào cột bên trái nhất còn trống sao
cho nó không ăn bất kỳ quân hậu nào đã có trên bàn cờ.
Kiểm tra mục tiêu? 8 quân hậu trên bàn cờ
có 2057 chuỗi để khám phá
29
Bài toán n quân hậu
Một giải pháp là một nút đích, không phải là một
đường đi tới nút này (đặc trưng của bài toán
thiết kế)
Số lượng các trạng thái trong không gian tìm
kiếm:
□ 8 quân hậu => 2.057
□ 100 quân hậu => 1052
Tuy nhiên tồn tại các kỹ thuật để giải các bài
toán n quân hậu hiệu quả cho các giá trị n lớn
30
Lập kế hoạch đường đi
Không gian trạng thái là gì?
31
Các giả định trong tìm kiếm
căn bản
Thế giới là tĩnh
Thế giới là có thể rời rạc hóa
Thế giới là có thể quan sát đầy đủ
Các hành động là xác định trước
Tuy nhiên nhiều giả định này có thể bị loại bỏ, và
tìm kiếm tiếp tục là một công cụ giải quyết vấn
đề quan trọng
32
Tìm kiếm và AI
Các phương pháp tìm kiếm có mặt mọi chỗ mọi nơi trong các
hệ thống AI. Chúng thường là xương sống cho cả các mô đun
lõi và các mô đun ngoại vi
Một rô bốt tự hành sử dụng tìm kiếm để quyết định thực hiện
hành động nào và thi hành thao tác cảm biến nào, để nhanh
chóng lường trước sự va chạm, để lập kế hoạch đường đi,..
Các công ty hậu cần sử dụng tìm kiếm để định vị các tài
nguyên, lập kế hoạch lộ trình, sắp lịch cho nhân viên
Các tác nhân hoặc các thành phần trong trò chơi sử dụng tìm
kiếm để điều hướng, lựa chọn nước đi, lường trước các hành
động của tác nhân khác, và quyết định các hành động của
bản thân nó.
33
Các ứng dụng
Tìm kiếm đóng vai trò chính trong nhiều ứng
dụng, ví dụ:
□ Tìm đường (bản đồ trực tuyến, internet, hàng không)
□ Bài trí VLSI
□ Điều hướng rô bốt
□ Thiết kế dược phẩm, thiết kế protein
□ Các trò chơi video
34
Các file đính kèm theo tài liệu này:
- ttn_chuong2a_8375_2001689.pdf