Khoa học máy tính - Tìm kiếm (Seaching)

Chia sẻ: Nguyen Van Dai | Ngày: | Loại File: PDF | Số trang:6

Thêm vào BST

Báo xấu

188
lượt xem 36
download

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

Trong ngành khoa học máy tính, một giải thuật tìm kiếm là một thuật toán lấy đầu vào là một bài toán và trả về kết quả là một lời giải cho bài toán đó, thường là sau khi cân nhắc giữa một loạt các lời giải có thể. Hầu hết các thuật toán được nghiên cứu bởi các nhà khoa học máy tính để giải quyết các bài toán đều là các thuật toán tìm kiếm.

Chủ đề:

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

Lưu

Nội dung Text: Khoa học máy tính - Tìm kiếm (Seaching)

Tìm ki m (searching) Lê S Vinh B môn Khoa H c Máy Tính – Khoa CNTT i H c Công Ngh - HQGHN Email: vinhbio@gmail.com
Các v n Tìm ki m trên danh sách: Có m t danh sách các i tư ng A, tìm xem m t i tư ng X có thu c vào danh sách này hay không Ví d : – Tìm m t sinh viên – m t s i n tho i – Tìm 1 t trong t i n – Tìm 1 lo i hàng hóa
Các v n Tìm ki m trên văn b n (text matching): Tim ki m s xu t hi n c a m t o n văn b n (1 t , 1 câu, 1 o n…) trong m t văn b n l n. o n văn b n có th xu t hi n chính xác ho c g n chính xác trong văn b n l n. Ví Ví d Search and replace in editors – Search engine (yahoo, google…) –
Tìm ki m trên danh sách Input: • Danh sách các i tư ng A = (a0,…,an) i tư ng c n tìm X • Output: • i: v trí xu t hi n c a tư ng X trong A (i = -1 n u X không xu t hi n) Thu t toán: Duy t l n lư t trên danh sách A và so sánh xem X có trong danh sách hay không. Nêu có tr l i v trí xu t hi n u tiên, n u không tr l i (-1) ph c t p: O(n)
Tìm ki m trên danh sách ã ư c s p x p Input: • Danh sách các i tư ng ã ư c s p x p A = (a0,…,an) | ai ≤ ai+1 i tư ng c n tìm X • Output: i: v trí xu t hi n c a tư ng X trong A (i = -1 n u X không xu t hi n) Tìm ki m nh phân: So sánh X v i ph n t gi a danh sách , n u N u b ng → X n m v trí gi a danh sách 1. N u nh hơn, Tìm ki m X trên n a u c a danh sách 2. N u l n hơn, Tìm ki m X trên n a cu i c a danh sách 3. ph c t p: O (log n)
T c • Boyer-Moore • Knuth-Moris-Pratt