TAILIEUCHUNG - bài giảng các chuyên đề phần 5

Cấu trúc dữ liệu và giải thuật TÌM KIẾM (SEARCHING) I. BÀI TOÁN TÌM KIẾM Cùng với sắp xếp, tìm kiếm là một đòi hỏi rất thường xuyên trong các ứng dụng tin học. Bài toán tìm kiếm có thể phát biểu như sau: Cho một dãy gồm n bản ghi r1, r2, ., rn. Mỗi bản ghi ri (1 ≤ i ≤ n) tương ứng với một khoá ki. Hãy tìm bản ghi có giá trị khoá bằng X cho trước. X được gọi là khoá tìm kiếm hay đối trị tìm . | Cấu trúc dữ liệu và giải thuật 70 8. TÌM KIẾM SEARCHING I. BÀI TOÁN TÌM KIẾM Cùng với sắp xếp tìm kiếm là một đòi hỏi rất thường xuyên trong các ứng dụng tin học. Bài toán tìm kiếm có thể phát biểu như sau Cho một dãy gồm n bản ghi r1 r2 . rn. Mỗi bản ghi ri 1 i n tương ứng với một khoá ki. Hãy tìm bản ghi có giá trị khoá bằng X cho trước. X được gọi là khoá tìm kiếm hay đối trị tìm kiếm argument . Công việc tìm kiếm sẽ hoàn thành nếu như có một trong hai tình huống sau xảy ra Tìm được bản ghi có khoá tương ứng bằng X lúc đó phép tìm kiếm thành công successful . Không tìm được bản ghi nào có khoá tìm kiếm bằng X cả phép tìm kiếm thất bại unsuccessful . Tương tự như sắp xếp ta coi khoá của một bản ghi là đại diện cho bản ghi đó. Và trong một số thuật toán sẽ trình bày dưới đây ta coi kiểu dữ liệu cho mỗi khoá cũng có tên gọi là TKey. const n . Số khoá trong dãy khoá có thể khai dưới dạng biến số nguyên để tuỳ biến hơn type TKey . Kiểu dữ liệu một khoá TArray array of TKey var k TArray Dãy khoá II. TÌM KIẾM TUẦN Tự SEQUENTIAL SEARCH Tìm kiếm tuần tự là một kỹ thuật tìm kiếm đơn giản. Nội dung của nó như sau Bắt đầu từ bản ghi đầu tiên lần lượt so sánh khoá tìm kiếm với khoá tương ứng của các bản ghi trong danh sách cho tới khi tìm thấy bản ghi mong muốn hoặc đã duyệt hết danh sách mà chưa thấy Tìm kiếm tuần tự trên dãy khoá ki k2 . kr hàm này thử tìm xem trong dãy có khoá nào X không nếu thấy nó trả về chỉ số của khoá ấy nếu không thấy nó trả về 0. Có sử dụng một khoá phụ kì 1 được gán giá trị X function SequentialSearch X TKey Integer var i Integer begin i 1 while i n and ki X do i i 1 if i n 1 then SequentialSearch 0 else SequentialSearch i end Dễ thấy rằng độ phức tạp của thuật toán tìm kiếm tuần tự trong trường hợp tốt nhất là O 1 trong trường hợp xấu nhất là O n và trong trường hợp trung bình cũng là O n . III. TÌM KIẾM NHỊ PHÂN BINARY SEARCH Phép tìm kiếm nhị phân có thể áp dụng trên dãy khoá đã có thứ tự k1 k2 . kn. Giả sử ta cần tìm trong đoạn kinf kinf 1

• Cơ sở dữ liệu
• thuật toán tìm kiếm
• các chuyên đề thuật toán
• lập trình pascal
• lập trình các giải thuật
• Các thuật toán tìm kiếm
• Tìm kiếm trên đồ thị
• Bài toán tìm kiếm trên đồ thị
• Thuật toán tìm kiếm theo chiều rộng
• Thuật toán tìm kiếm theo chiều sâu
• Tìm kiếm tuần tự
• Tìm kiếm nhị phân
• Tìm kiếm dựa trên quy hoạch động
• Tìm kiếm dựa trên đệ quy
• Tìm kiếm dựa trên phân vùng
• Khái niệm tìm kiếm
• Bài toán tìm kiếm
• Tìm kiếm trên dãy chưa sắp
• Cấu trúc dữ liệu
• Kỹ thuật tìm kiếm
• Tìm kiếm trên mảng
• Giải thuật tìm kiếm
• Tìm kiếm trên tập tin
• Tìm kiến tuyến tính
• Thuật toán tìm kiếm tối ưu
• Tìm kiếm cứu nạn
• Thuật toán vi khuẩn
• Tính toán phương án tìm kiếm tối ưu
• Tàu tìm kiếm cứu nạn
• Lý thuyết đồ thị
• Bài giảng Lý thuyết đồ thị
• Thuật toán tìm kiếm trên đồ thị
• Ứng dụng thuật toán tìm kiếm đồ thị
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu và giải thuật
• Khái niệm về tìm kiếm
• Phương pháp tìm kiếm tuần tự
• Phương pháp tìm kiếm nhị phân
• Thuật toán tìm kiếm nhị phân
• Thuật toán tìm kiếm nhị phân cơ bản
• Thuật toán Quicksort
• Cách tìm kiếm nhị phân
• chiến lược tìm kiếm mù
• Tìm kiếm beam
• Tìm kiếm leo đồi
• tìm kiếm tối ưu
• Tìm kiếm có đối thủ
• Tìm kiếm mô phỏng sự tiến hóa
• Thuật toán di truyền
• Bài toán giải thuật
• Chiến lược tìm kiếm
• Tìm kiếm trình tự
• Lập trình C
• Bài giảng Lập trình căn bản
• Bài toán sắp xếp
• Thuật toán tìm kiếm tuần tự
• Thuật toán sắp xếp nổi bọt
• khoa học
• tự nhiên
• toán học
• Các thuật toán tìm kiếm trên đồ thị
• Các giải thuật tìm kiếm
• Giải thuật tìm kiếm tuyến tính
• Giải thuật Tìm kiếm nhị phân
• Các giải thuật sắp xếp
• Tóm tắt Luận án Thạc sĩ
• Hệ thống thông tin
• Tìm kiếm chuỗi DNA
• Tìm kiếm tương tự nhanh
• Bài giảng Toán rời rạc 2
• Toán rời rạc 2
• Toán rời rạc
• Ứng dụng của thuật toán tìm kiếm
• Bài giảng Tìm kiếm heuristic leo đồi
• Thuật giải di truyền
• Thuật giải leo đồi
• Các thuật toán tìm kiếm cục bộ
• Lựa chọn của thuật giải di truyền
• Nội dung về thuật giải leo đồi
• Bài giảng Cấu trúc dữ liệu
• Tìm kiếm trên danh sách
• Tìm kiếm trên văn bản
• Bài giảng Tìm kiếm
• Kỹ thuật lập trình
• Bài giảng Các hệ thống thông minh nhân tạo
• Hệ thống thông minh nhân tạo
• Bài toán tìm kiếm 1
• Cây tìm kiếm
• Thuật toán tìm kiếm mù
• Bài toán tìm đường đi
• Thuật giải HEURISTIC
• phương pháp tìm kiếm HEURISTIC
• thuật toán tìm kiếm leo đồi
• tìm kiếm ưu tiên tối ưu
• ứng dụng giải bài toán ta canh
• chiến lược tìm kiếm lai
• Bài giảng Thuật toán Ứng dụng
• Thuật toán Ứng dụng
• Cấu trúc dữ liệu trừu tượng
• Cài đặt tìm kiếm ở thư viện
• tài liệu học đại học
• bài giảng quy hoạch tuyến tính
• Khoa học máy tính
• tìm kiếm tuyến tính
• Tìm kiếm theo chiều sâu
• Tìm kiếm theo chiều rộng
• Ứng dụng các thuật toán
• Bài giảng Tìm kiếm đối kháng
• Tìm kiếm đối kháng
• Tìm kiếm đối kháng trò chơi
• Thuật toán MINIMAX
• Hàm lượng giá
• Tìm kiếm cắt nhánh