Tìm kiếm

Tài liệu tham khảo bài giảng Tìm kiếm khoa công nghệ thông tin
Nội dung trích xuất từ tài liệu:
Tìm kiếm 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 GOAL a c b 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 GOAL a c b 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 GOAL a c b 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 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 GOAL a c b 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ư c nhưngkhô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 2 bư cnhư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 3 bư cnhư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 GOAL a c b0 bư c t e dstart f START h p r q ...