Bài giảng Tìm Kiếm - Tô Hoài Việt

Bài toán tìm kiếm, tìm kiếm theo chiều rộng, tính tối ưu, tính đầy đủ, độ phức tạp thời gian và không gian, cây tìm kiếm, tìm kiếm theo chiều sâu là những nội dung chính trong "Bài giảng Tìm Kiếm - Tô Hoài Việt". Mời các bạn tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Tìm Kiếm - Tô Hoài Việt TÌM KIẾM 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.vnRef: http://www.cs.cmu.edu/~awm/tutorials 1 Tổng quát• Bài toán tìm kiếm• Tìm kiếm Theo chiều Rộng• Tính tối ưu, Tính đầy đủ, Độ phức tạp thời gian và không gian• Cây Tìm kiếm• Tìm kiếm Theo chiều Sâu 2 Một bài toán Tìm kiếm a GOAL b c e d f START h p r qLàm sao để đi từ S đến G? Và số biến đổi có thểít nhất là gì? 3 Hình thức hoá một bài toán tìm kiếmMột bài toán tìm kiếm có năm thành phần:Q , S , G , succs , cost• Q là một tập hữu hạn các trạng thái.• S Q một tập khác rỗng các trạng thái ban đầu.• G Q một tập khác rỗng các trạng thái đích.• succs : Q  P(Q) là một hàm nhận một trạng thái làm đầu vào và trả về kết quả là một tập trạng thái. succs(s) nghĩa là “tập các trạng thái có thể đến từ s trong một bước”.• cost : Q , Q  Số Dương là một hàm nhận hai trạng thái, s và s’, làm đầu vào. Nó trả về chi phí một bước của việc di chuyển từ s đến s’. Hàm chi phí chỉ được định nghĩa khi s’ là trạng thái con của s. 4 Bài toán Tìm kiếm a GOAL b c e d f START h p r qQ = {START, a , b , c , d , e , f , h , p , q , r , GOAL}S = { START }G = { GOAL }succs(b) = { a }succs(e) = { h , r }succs(a) = NULL … etc.cost(s,s’) = 1 cho tất cả các biến đổi 5 Bài toán Tìm kiếm a GOAL b c e d f START h p r q m ?Q = {START, a , b , c , d , e , f , h , p , q , r , GOAL} tâ h ư a n gnS = { START } q u iốnG = { GOAL } t a og s a o n àsuccs(b) = { a } isuccs(e) = { h , r } Tạ i toánsuccs(a) = NULL … etc. Bà ?cost(s,s’) = 1 cho tất cả các biến đổi v ậ y 6Các Bài toán Tìm kiếm 7Các Bài toán Tìm kiếm Lập lịch 8-Hậu Gì nữa? Giải toán 8 Tìm kiếm Theo Chiều Rộng a GOAL b c e d f START h p r qGán nhãn tất cả trạng thái có thể đi đến được từ S trong 1 bướcnhưng không thể đi đến được trong ít hơn 1 bước.Sau đó gán nhãn tất cả trạng thái có thể đi đến được từ S trong 2bước nhưng không thể đi đến được trong ít hơn 2 bước.Sau đó gán nhãn tất cả trạng thái có thể đi đến được từ S trong 3bước nhưng không thể đi đến được trong ít hơn 3 bước.V.v… đến khi trạng thái Goal được đi đến. 9 Tìm kiếm Theo Chiều Rộng a GOAL b c0 bước từ estart d f START h p r q 10 Tìm 1 bước từ kiếm Theo Chiều Rộng start GOAL a b c0 bước từ estart d f START h p r q 11 Tìm 1 bước từ kiếm Theo Chiều Rộng start GOAL a ...