Thạc Sĩ Bài Toán tìm kiếm văn bản sử dụng giải thuật di truyền

MỤC LỤC
Trang
Trang phụ bìa
Lời cam đoan
Mục lục i
Danh mục các thuật ngữ . iv
Danh mục các hình vẽ, bảng biểu . v
MỞ ĐẦU: 1
1. ĐẶT VẤN ĐỀ 1
2. MỤC ĐÍCH CỦA LUẬN VĂN 2
3. NỘI DUNG CỦA LUẬN VĂN 2
4. PHƯƠNG PHÁP NGHIÊN CỨU 2
NỘI DUNG .
CHƯƠNG 1. MỘT SỐ KỸ THUẬT TÌM KIẾM Văn bản 3
1.1. Bài toán tìm kiếm Văn bản . 3
1.2. Các thuật toán 4
1.2.1. Thuật toán Brute Force . 4
1.2.2. Thuật toán Knuth-Morris-Pratt . 5
1.2.3. Thuật toán Deterministic Finite Automaton (máy automat hữu hạn) . 7
1.2.4. Thuật toán Boyer-Moore 10
1.2.5. Thuật toán Karp-Rabin . 15
1.2.6. Các thuật toán khác 17
CHƯƠNG 2. GIỚI THIỆU VỀ GIẢI THUẬT DI TRUYỀN . 20
2.1. Tổng quan về giải thuật di truyền 20
2.1.1. Giới thiệu . 20
2.1.2. Sự khác biệt của giải thuật di truyền so với các giải thuật khác . 21
2.1.3. Tính chất quan trọng của giải thuật di truyền 21
2.2. Giải thuật di truyền cổ điển . 22
2.2.1. Giới thiệu . 22
2.2.2. Các toán tử di truyền 24
2.2.2.1. Toán tử chọn lọc 24
2.2.2.2. Toán tử lai ghép . 25
2.2.2.3. Toán tử đột biến . 26
2.2.3. Các bước quan trọng trong việc áp dụng giải thuật di truyền cổ điển 26
2.2.4. Ví dụ 27
CHƯƠNG 3. SỬ DỤNG GIẢI THUẬT DI TRUYỀN ĐỂ TÌM KIẾM
Văn bản . 33
3.1. Yêu cầu đặt ra cho bài toán tìm kiếm văn bản 33
3.2. Xây dựng hàm tìm kiếm Văn bản . 34
3.3. Phát biểu bài toán tìm kiếm Văn bản theo hướng tiếp cận di truyền . 35
3.4. Tìm độ dài xâu con chung lớn nhất bằng quy hoạch động . 38
3.5. Áp dụng giải thuật di truyền 39
3.5.1. Biểu diễn nhiễm sắc thể 39
3.5.2. Khởi tạo quần thể . 40
3.5.3. Hàm mục tiêu . 40
3.5.4. Các toán tử di truyền 41
3.5.5. Các tham số 42
3.5.6. Chi phí thời gian . 42
CHƯƠNG 4. KẾT QUẢ THỰC NGHIỆM VÀ Phát triển PHẦN
MỀM ỨNG DỤNG . 44
4.1. Các kết quả thử nghiệm . 44
4.1.1. Kết quả thử nghiệm tìm kiếm tuyến tính . 44
4.1.1.1. Tìm kiếm tuyến tính bằng so khớp chuỗi . 44
4.1.1.2. Tìm kiếm tuyến tính sử dụng hàm quy hoạch động 45
4.1.2. Kết quả thử nghiệm tìm kiếm bằng giải thuật di truyền 46
4.2. Phát triển phần mềm ứng dụng 50
KẾT LUẬN VÀ ĐỀ NGHỊ 51
TÀI LIỆU THAM KHẢO 52
PHỤ LỤC 54