Tìm kiếm heuristic

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

Thêm vào BST

Báo xấu

209
lượt xem 34
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tổng quan • Tìm kiếm heuristic Tối ưu kiểu “Tham lam” (“Greedy Best-First Search) • Những điểm không thích hợp của tìm kiếm heuristic “Tham lam”. • 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*)...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tìm kiếm heuristic

Tìm kiếm heuristic Tìm kiếm A* Tô Hoài Việt Khoa Công nghệ Thông tin Đại học Khoa học Tự nhiên TPHCM thviet@fit.hcmuns.edu.vn Ref: http://www.cs.cmu.edu/~awm/tutorials 1
Tổng quan • Tìm kiếm heuristic Tối ưu kiểu “Tham lam” (“Greedy Best-First Search) • Những điểm không thích hợp của tìm kiếm heuristic “Tham lam”. • 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*) 2
Tìm kiếm Heuristic - 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 S đường nào? 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? 3
Tìm kiếm Heuristic 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) tính các trạng thái thành giá trị chi phí. 4
Heuristic theo Khoảng cách Euclide GOAL a 2 2 h=0 h=8 c b 2 5 h=4 h=5 1 8 h=11 2 e d 3 f 9 1 h=8 9 h=4 START h 4 5 h=6 1 h=12 4 3 p r 15 q h=11 h=6 h=9 5
Heuristic theo Khoảng cách Euclide GOAL a 2 2 h=0 h=8 c b 2 5 h=4 h=5 1 8 h=11 2 e d 3 f 9 1 h=8 9 h=4 START h 4 5 h=6 1 h=12 4 3 p r 15 q h=11 h=6 h=9 6
Heuristic theo Khoảng cách Euclide GOAL a 2 2 h=0 h=8 c b 2 5 h=4 h=5 1 8 h=11 2 e d 3 f 9 1 h=8 9 h=4 START h 4 5 h=6 1 h=12 4 3 p r 15 q h=11 h=6 h=9 PQ = {(Start,12)} 7
Heuristic theo Khoảng cách Euclide GOAL a 2 2 h=0 h=8 c b 2 5 h=4 h=5 1 8 h=11 2 e d 3 f 9 1 h=8 9 h=4 START h 4 5 h=6 1 h=12 4 3 p r 15 q h=11 h=6 h=9 PQ = {(e,4),(d,8),(p,11)} 8
Heuristic theo Khoảng cách Euclide GOAL a 2 2 h=0 h=8 c b 2 5 h=4 h=5 1 8 h=11 2 e d 3 f 9 1 h=8 9 h=4 START h 4 5 h=6 1 h=12 4 3 p r 15 q h=11 h=6 h=9 PQ = {(h,6),(r,6),(d,8),(p,11)} 9
Heuristic theo Khoảng cách Euclide GOAL a 2 2 h=0 h=8 c b 2 5 h=4 h=5 1 8 h=11 2 e d 3 f 9 1 h=8 9 h=4 START h 4 5 h=6 1 h=12 4 3 p r 15 q h=11 h=6 h=9 PQ = {(r,6),(d,8),(q,9),(p,11)} 10
Heuristic trong bài toán 8-puzzle • Theo số ô nằm sai vị trí 1 5 123 263 h=6 456 748 78 11
Heuristic trong bài toán 8-puzzle • Theo tổng khoảng cách Manhattan 1 5 123 263 456 h=9 748 78 d = dx + dy h = 0 + 2 + 1 + 2 + 2 + 1 +0 + 1 = 9 12
Tìm kiếm “Tham lam” Init-PriQueue(PQ) Insert-PriQueue(PQ,START,h(START)) while (PQ khác rỗng và PQ không chứa trạng thái đích) (s , h ) := Pop-least(PQ) Với mỗi s’ trong succs(s) Nếu s’ không có trong PQ và s’ chưa được viếng trước đó bao giờ Insert-PriQueue(PQ,s’,h(s’)) Thuật toán Đủ Tối ưu Thời gian Không gian Best First O(min(N,BLMAX)) O(min(N,BLMAX)) BestFS C K Search Một vài cải tiến của thuật toán này có thể làm cho mọi việc tốt đẹp hơn. Nó là thứ mà chúng ta gọi là: A*…. * Việc sử dụng heuristic làm thay đổi B 13
Hãy Xem “Tham lam” Ngớ Ngẩn thế nào! 4 2 1 1 2 S A B C G h=4 h=3 h=2 h=1 h=0 • Tìm kiếm tham lam rõ ràng không đảm bảo tìm thấy lời giải mong muốn • Câu hỏi: Chúng ta có thể làm gì để tránh lỗi ngớ ngẩn này? 14
A* - Ý tưởng Cơ bản • Best-first greedy: Khi bạn mở một node n, lấy node con n' và đặt nó vào PriQueue với độ ưu tiên h(n') • A*: Khi bạn mở một node n, lấy node con n' và đặt nó vào PriQueue với độ ưu tiên (Chi phí đi đến n') + h(n') (1) Đặt g(n) = Chi phí đi đến n (2) và định nghĩa… f(n) = g(n) + h(n) (3) 15
A* Không Ngớ Ngẩn! 4 2 1 1 2 S A B C G h=0 h=4 h=3 h=2 h=1 16
A* dừng khi nào? Ý tưởng: Ngay khi nó phát sinh được trạng thái đích? Xem ví dụ sau: 1 1 S h=3 1 B h=8 h=7 A C h=2 1 7 D h=1 7 G h=0 17
Quy tắc Dừng A* Đúng Đắn: A* Dừng Chỉ Khi một Trạng Thái Đích Được Lấy ra khởi Priority Queue 1 1 S h=3 1 B h=8 h=7 A C h=2 1 7 D h=1 7 G h=0 18
Các trạng thái quay lại A* Một câu hỏi khác: Điều gì xảy ra nếu A* quay lại một trạng thái đã mở, và tìm được một đường ngắn hơn? 1 1 S h=3 1 B h=8 h=7 A C h=2 1 1/2 D h=1 Trong ví dụ này một trạng 7 thái đã mở được mở lại. Như thế nào và tại sao ? G 19
Các trạng thái quay lại A* Điều gì nếu A* thăm một trạng thái đã có trong hàng đợi? h=8 1 1 S h=3 1 B h=7 A C h=8 1 1/2 D h=1 Trong ví dụ này một trạng thái đã lưu ý rằng giá trị h có trong hàng đợi và đang đợi mở 7 G này đã thay đổi so có độ ưu tiên tăng vọt lên. Như với trang trước. thế nào và tại sao? 20