Xem mẫu
- CÁC HỆ THỐNG THÔNG MINH NHÂN TẠO & ỨNG DỤNG
Bài toán tìm kiếm II
THS. BÙI THỊ DANH
BM.KHMT, KHOA CNTT, ĐH.KHTN TP.HCM
- Nội dung
Heuristic
Tìm kiếm tham lam
Thuật giải A*
Sự nới lỏng
2
- Heuristic
Các thuật toán tìm kiếm mù duyệt trạng thái theo mọi hướng, không sử dụng thông tin của
trạng thái đích.
Ước lượng chi phí
đến trạng thái đích.
Liệu có tìm đường
nhanh hơn?!?
3
- Heuristic
Heuristic là một hàm ước lượng mức độ gần của một trạng thái so với trạng thái đích
◦ Kí hiệu là h(s), với s là trạng thái.
Heuristic được thiết kế cho từng bài toán tìm kiếm cụ thể
Một số hàm heuristic phổ biến:
◦ Khoảng cách Euclidean, Mahattan.
◦…
4
- Ví dụ - Tìm đường đi cho Pacman
Hàm h(s) là hàm Euclidean
5
- Ví dụ - Tìm đường đi trên bản đồ
Hàm h(s) là khoảng cách đường chim bay
6
- Ví dụ - N-Puzzle
Hàm h(s): số ô khác biệt giữa 2 puzzle…
7
- Nội dung
Heuristic
Tìm kiếm tham lam
Thuật giải A*
Sự nới lỏng
8
- Tìm kiếm tham lam (greedy search)
Chiến lược duyệt: mở rộng trạng thái được ước lượng là gần trạng thái đích nhất
◦ Hàm heuristic tương ứng h(s) có giá trị nhỏ nhất
Sử dụng hàng đợi ưu tiên để triển khai, với độ ưu tiên là h(s)
Tùy chọn: đánh dấu các trạng thái đã được xem xét
◦ Đánh dấu khi trạng thái được lấy khỏi hàng đợi
9
- Ví dụ
Goal
a
2 h=0
2 h=8
h=5
b 1 8 c 2 5
h = 11 2 e
3 d h=4
f
9 h=8
Start
1 9 h=4
4
h 5
h = 12 1 h=6
p
15 q 4 r
h = 11
h=9 h=6
S = null, PQ={(Start,12)}
10
- Ví dụ
Goal
a
2 h=0
2 h=8
h=5
b 1 8 c 2 5
h = 11 2 e
3 d h=4
f
9 h=8
Start
1 9 h=4
4
h 5
h = 12 1 h=6
p
15 q 4 r
h = 11
h=9 h=6
S = Start/12, PQ={(e, 4), (d, 8), (p,11)}
11
- Ví dụ
Goal
a
2 h=0
2 h=8
h=5
b 1 8 c 2 5
h = 11 2 e
3 d h=4
f
9 h=8
Start
1 9 h=4
4
h 5
h = 12 1 h=6
p
15 q 4 r
h = 11
h=9 h=6
S = e/4, PQ={ (h,6), (r, 6), (d, 8), (p,11),}
12
- Ví dụ
Goal
a
2 h=0
2 h=8
h=5
b 1 8 c 2 5
h = 11 2 e
3 d h=4
f
9 h=8
Start
1 9 h=4
4
h 5
h = 12 1 h=6
p
15 q 4 r
h = 11
h=9 h=6
S = h/6, PQ={(r, 6), (d, 8), (q, 9), (p,11),}
13
- Ví dụ
Goal
a
2 h=0
2 h=8
h=5
b 1 8 c 2 5
h = 11 2 e
3 d h=4
f
9 h=8
Start
1 9 h=4
4
h 5
h = 12 1 h=6
p
15 q 4 r
h = 11
h=9 h=6
S = r/6, PQ={ (f, 4), (d, 8), (q, 9), (p,11),}
14
- Ví dụ
Goal
a
2 h=0
2 h=8
h=5
b 1 8 c 2 5
h = 11 2 e
3 d h=4
f
9 h=8
Start
1 9 h=4
4
h 5
h = 12 1 h=6
p
15 q 4 r
h = 11
h=9 h=6
S = f/4, PQ={ (Goal, 0), (d, 8), (q, 9), (p,11),}
15
- Ví dụ
Goal
a
2 h=0
2 h=8
h=5
b 1 8 c 2 5
h = 11 2 e
3 d h=4
f
9 h=8
Start
1 9 h=4
4
h 5
h = 12 1 h=6
p
15 q 4 r
h = 11
h=9 h=6
S = Goal/0, PQ={ (d, 8), (q, 9), (p,11),} Đã tìm thấy Goal
16
- Tìm kiếm tham lam (greedy search)
Khởi tạo hàng đợi ưu tiên pQueue
Đưa trạng thái bắt đầu start vào pQueue
Loop
If không còn trạng thái để mở rộng then return “không có lời giải”
Chọn trạng thái s đầu hàng đợi để mở rộng
If s là trạng thái đích then return “có lời giải”
Gán nhãn cho trạng thái s
Với mỗi trạng thái mới s’ mở rộng từ s:
If s’ chưa được gán nhãn then
Tí𝑛ℎ ℎ(𝑠 ′ )
If 𝑠′ không có trong pQueue then
Thêm s’ vào pQueue
Ghi nhớ trạng thái trước của s’ là s
end
17
- Tìm kiếm tham lam (greedy search)
Tính đầy đủ:
◦ Có
Tính tối ưu:
◦ Không, vì chỉ dựa vào chi phí ước lượng
◦ Thường đưa agent tới thẳng trạng thái đích, nhưng không phải với chi phí tốt nhất
Độ phức tạp tính toán:
◦ O(min N, 𝑏 max )
Độ phức tạp lưu trữ:
◦ O(min N, 𝑏 max )
18
- Nội dung
Heuristic
Tìm kiếm tham lam
Thuật giải A*
Sự nới lỏng
19
- Thuật giải A*
Ý tưởng: kết hợp thuật toán UCS và tìm kiếm tham lam
UCS: chiến lược duyệt dựa theo chi phí từ trạng thái bắt đầu đến trạng thái đang xét, 𝑔(𝑠)
Tìm kiếm tham lam: chiến lược duyệt dựa theo chi phí ước lượng từ trạng thái đang xét
đến trạng thái cuối, ℎ(𝑠)
Thuật giải A*: chiến lược duyệt dựa theo theo giá trị tổng 𝑓 𝑠 = 𝑔 𝑠 + ℎ(𝑠)
ℎ 𝑠 ,ước lượng
Start … s … Goal
𝑔(𝑠)
20
nguon tai.lieu . vn
