Ktl-icon-tai-lieu

Trí tuệ nhân tạo Tìm kiêm có thông tin heuristic, A*

Được đăng lên bởi ky-thuat
Số trang: 7 trang   |   Lượt xem: 488 lần   |   Lượt tải: 0 lần
Ref: 

TRÍ TUỆ NHÂN TẠO
Tìm kiếm có thông tin heuristic, A*

Nội dung trình bày
2

Tìm kiếm có thông tin heuristic tốt nhất
Những ñiểm không thích hợp của tìm kiếm tốt nhất
Mẹo: tính luôn chi phí ñi ñến trạng thái hiện tại.
Việc tìm kiếm kết thúc khi nào?
Heuristic chấp nhận ñược
Tìm kiếm A* là ñầy ñủ
Tìm kiếm A* luôn dừng
Khuyết ñiểm của A*
Tiết kiệm nhiều bộ nhớ với IDA* (Iterative Deepening A*)

Tìm kiếm với thông tin heuristic
3

Các phương pháp tìm kiếm mù (blind search):
thông tin về trạng thái ñích không ñóng vai trò
trong việc tìm kiếm.
Nên ñi
ñường nào?

S
a

b

c

G

Có thể sử dụng ước lượng khoảng cách ñến ñích
giữa các trạng thái ñể tìm ñường ñi?

Tìm kiếm với thông tin heuristic (tt)
4

Giả sử ngoài việc ñặc tả tìm kiếm chuẩn ta cũng có một
heuristic.

Một hàm heuristic ánh xạ một trạng thái
thành một ước lượng về chi phí ñến
ñích từ trạng thái ñó.
Bạn có thể nghĩ ra ví dụ về heuristics?
VD. ñối với bài toán 8-puzzle?
VD. ñể lập ñường ñi trong ma trận?
Ký hiệu heuristic bằng một hàm h(s)

Heuristic theo Khoảng cách Euclide
5

GOAL

a

2

2

h=0

h=8

b

c

1

h=11

2

2

e

d

3

9

h=8

1

START

h=12

5

h=4

h=5

8

p

15

9

h=4

h

4

1

f
5

h=6
4

3

r

q

h=11
h=9

h=6

ðiều cần nắm
29

Hiểu thấu ñáo A*.
Có thể chạy tay các ví dụ thực thi A*
ñơn giản.
Hiểu ñược “tính chấp nhận ñược” của
heuristics. Chứng minh tính ñầy ñủ,
bảo ñảm tính tối ưu của ñường ñi.
Có thể nhận xét về các ñánh giá.

Thắc mắc
30

...
TRÍ TUỆ NHÂN TẠO
Tìm kiếm có thông tin heuristic, A*
Ref: http://www.cs.cmu.edu/~awm/tutorials
Trí tuệ nhân tạo Tìm kiêm có thông tin heuristic, A* - Trang 2
Để xem tài liệu đầy đủ. Xin vui lòng
Trí tuệ nhân tạo Tìm kiêm có thông tin heuristic, A* - Người đăng: ky-thuat
5 Tài liệu rất hay! Được đăng lên bởi - 1 giờ trước Đúng là cái mình đang tìm. Rất hay và bổ ích. Cảm ơn bạn!
7 Vietnamese
Trí tuệ nhân tạo Tìm kiêm có thông tin heuristic, A* 9 10 451