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. | TÌM KIẾM Ref: Tô Hoài Việt Khoa Công nghệ Thông tin Đại học Khoa học Tự nhiên TPHCM thviet@ 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 Một bài toán Tìm kiếm Làm sao để đi từ S đến G? Và số biến đổi có thể ít nhất là gì? START GOAL d b p q c e h a f r 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. Bài toán Tìm kiếm 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 START GOAL d b p q c e h a f r Bài toán Tìm kiếm 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 START GOAL d b p q c e h a f r Tại sao ta quan tâm? Bài toán nào giống như vậy? Các Bài toán Tìm kiếm Các Bài toán Tìm kiếm Lập lịch 8-Hậu Gì nữa? Giải toán Tìm kiếm Theo Chiều Rộng 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 . | TÌM KIẾM Ref: Tô Hoài Việt Khoa Công nghệ Thông tin Đại học Khoa học Tự nhiên TPHCM thviet@ 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 Một bài toán Tìm kiếm Làm sao để đi từ S đến G? Và số biến đổi có thể ít nhất là gì? START GOAL d b p q c e h a f r 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 .
