Xem mẫu
- 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
nguon tai.lieu . vn
