View Single Post
  #1  
Old 07-19-2012, 06:55 PM
die die is offline
Senior Member
 
Tham gia: Apr 2012
Tổng số bài gởi: 8,890
Send a message via Yahoo to die


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

Trả Lời Với Trích Dẫn