Tìm kiếm

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

Thêm vào BST

Báo xấu

92
lượt xem 12
download

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

Tài liệu tham khảo bài giảng Tìm kiếm khoa công nghệ thông tin

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

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.vn Ref: 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 q Là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 m M 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 q Q = {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 q Q = {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 6
Các Bài toán Tìm ki m 7
Cá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 q Gán nhãn t t c tr ng thái có th đi đ n đư c t S trong 1 bư c như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 2 bư 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 3 bư 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 GOAL a c b 0 bư c t e d start f START h p r q 10
Tìm ki m Theo Chi u R ng 1 bư c t start GOAL a c b 0 bư c t e d start f START h p r q 11
Tìm ki m Theo Chi u R ng 1 bư c t start GOAL a c b 0 bư c t e d start f START h p r q 2 bư c t start 12
Tìm ki m Theo Chi u R ng 1 bư c t start GOAL a c b 0 bư c t e d start f START h 3 bư c t start p r q 2 bư c t start 13
4 bư c t Tìm ki m Theo Chi u R ng start 1 bư c t start GOAL a c b 0 bư c t e d start f START h 3 bư c t start p r q 2 bư c t start 14
Ghi nh đư ng đi! GOAL a c b e d f START h p r q Ngoài ra, khi gán nhãn m t tr ng thái, ghi nh n tr ng thái trư c đó. Ghi nh n này đư c g i là con tr quay lui. L ch s trư c đó đư c dùng đ phát sinh con đư ng l i gi i, khi đã tìm đư c đích: “Tôi đã đ n đích. Tôi th y mình đã f trư c đó. Và tôi đã r trư c khi t i f. Và… …. do đó con đư ng l i gi i là S e r f G” 15
4 bư c t Con tr quay lui start 1 bư c t start GOAL a c b 0 bư c t e d start f START h 3 bư c t start p r q 2 bư c t start 16
4 bư c t Con tr quay lui start 1 bư c t start GOAL a c b 0 bư c t e d start f START h 3 bư c t start p r q 2 bư c t start 17
B t đ u Tìm ki m Theo chi u R ng V i b t kỳ tr ng thái s nào đã gán nhãn, ghi nh : •previous(s) là tr ng thái trư c đó trên đư ng đi ng n nh t t tr ng thái START đ n s. Trong vòng l p th k c a thu t toán ta b t đ u v i Vk đư c đ nh nghĩa là t p các tr ng thái mà t tr ng thái start đi đ n có đúng k bư c Sau đó, trong su t vòng l p, ta s tính Vk+1, đư c đ nh nghĩa là t p các tr ng thái mà t tr ng thái start đi đ n có đúng k+1 bư c Chúng ta b t đ u v i k = 0, V0 = {START} và đ nh nghĩa, previous(START) = NULL Sau đó ta s thêm vào nh ng tr ng thái m t bư c t START vào V1. Và ti p t c. 18
BFS GOAL a c b e d f START h V0 p r q 19
BFS GOAL a c b e d f START h V0 p r q V1 20