BÁO CÁO TỐT NGHIỆP: TÌM HIỂU VÀ ĐÁNH GIÁ MỘT SỐ THUẬT TOÁN TÌM KIẾM TRUYỀN THỐNG ỨNG DỤNG TRONG TIN HỌC

BÁO CÁO TỐT NGHIỆP .TÌM HIỂU VÀ ĐÁNH GIÁ MỘT SỐ THUẬT TOÁN TÌM KIẾM TRUYỀN THỐNG ỨNG DỤNG TRONG TIN HỌC Phương pháp tạo sinh và thử, phương pháp leo núi, Kỹ thuật HEURISTICS, Các chương trình minh họa....
Nội dung trích xuất từ tài liệu:
BÁO CÁO TỐT NGHIỆP: TÌM HIỂU VÀ ĐÁNH GIÁ MỘT SỐ THUẬT TOÁN TÌM KIẾM TRUYỀN THỐNG ỨNG DỤNG TRONG TIN HỌC BÁO CÁO TỐT NGHIỆP TÌM HIỂU VÀ ĐÁNH GIÁ MỘT SỐ THUẬT TOÁN TÌM KIẾM TRUYỀN THỐNG ỨNG DỤNG TRONG TIN HỌC Giáo viên hướng dẫn: PGS.TS Đỗ Đức Giáo Sinh viên thực hiện: Nguyễn Thị Minh Tâm Lớp: K96C2 - CNTT THỂ HIỆN TRI THỨC Tri thức là sự hiểu biết về một miền chủ đề. Thể hiện tri thức là phương pháp dùng để mã hoá tri thức trong cơ sở tri thức của hệ thống. Có năm phương pháp thể hiện tri thức: CẶP BA ĐỐI TƯỢNG - THUỘC TÍNH - GIÁ TRỊ Ví dụ: Mệnh đề “quả bóng màu đỏ” được thể hiện như sau Màu Quả bóng Đỏ Đối tượng Thuộc tính Giá trị CÁC LUẬT Ví dụ: IF trời mưa AND không có áo mưa THEN nghỉ học ELSE đi học CÁC MẠNG NGỮ NGHĨA Ví dụ: Cánh Có IS - A Chíp chíp Chim Có thể Bay CÁC KHUNG Tên khung Mơ Tên lớp Người Thuộc tính Địa chỉ Hàng Bồ Nam/Nữ Không biết Cao 1.58 mét Nặng 48 kg Nghề nghiệp Không biết Khung thể hiện đối với một đối tượng cụ thể là “Mơ” thuộc lớp “Người” LOGIC Logic gồm hai loại: - Logic mệnh đề thể hiện và suy lý với các mệnh đề. Ví dụ: A ∩ B →C Đặc biệt một số phép toán có thể được suy diễn từ các phép toán khác A →B ≡ ¬ A ∪ B - Logic vị từ là mở rộng của phép toán mệnh đề để thể hiện rõ hơn các tri thức. Ví dụ: Thich(X,Y) ∩ Thich(Z, Y) → ¬ Thich(X, Z) CÁC PHƯƠNG PHÁP GIẢI BÀI TOÁN TÌM KIẾM CÁC PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ BIỂU DIỄN VẤN ĐỀ TRONG KHÔNG GIAN TRẠNG THÁI Để thực hiện được phương pháp này, ta phải xác định được trạng thái đầu, sau đó áp dụng các dãy toán tử để tạo ra dãy các trạng thái liên tiếp cho đến khi đến được trạng thái đích. Ví dụ: Trạng thái đầu là (1, 1), trạng thái đích là (3, 5) ta có không gian trạng thái như sau: (1, 1) (2, 1) (1, 2) (1, 3) (3, 2) (2, 3) (3, 1) (1, 4) (4, 3) (3, 5) (5, 3) PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ NHỜ PHÂN RÃ RA CÁC BÀI TOÁN NHỎ Ví dụ: Với bài toán tích phân sau ∫ (x2 + 2*x + 3)dx = ∫ x2dx + ∫ 2*xdx + ∫ 3dx = x3/3 + x2 + 3*x PHƯƠNG PHÁP GIẢI VẤN ĐỀ NHỜ LOGIC HÌNH THỨC Khi giải bài toán nhờ phương pháp này cần chú ý: • Mọi biểu thức logic mệnh đề đều có thể đưa về dạng biểu thức tương đương chỉ chứa phép OR (∨), AND (∧) và NOT (¬). • Các phép ∨, ∧ có tính giao hoán, kết hợp, phân phối. • Thứ tự của các phép toán: phủ định, kéo theo, tương đương, hội, tuyển. Ví dụ: Biểu thức ¬ (a → b) ∪ (c ∩ d) có thể đưa về thành (a ∩ ¬ b) ∪ (c ∩ d) và đều cho kết quả TRUE CÁC PHƯƠNG PHÁP TÌM KIẾM CƠ BẢN PHƯƠNG PHÁP TÌM KIẾM THEO CHIỀU RỘNG Tìm rộng là kỹ thuật tìm kiếm lời giải trên tất cả các nút của một mức trong không gian bài toán trước khi chuyển sang các nút của mức tiếp theo. Ví dụ: Với bài toán hai số (1, 1) ta có thể tìm kiếm theo chiều rộng, các nhánh đi được đánh số như sau: 1 (1, 1) 2 (2, 1) (1, 2) 3 4 6 5 (3, 1) (2, 3) (1, 3) 7 8 (3, 2) (5, 2) (2, 5) PHƯƠNG PHÁP TÌM KIẾM THEO CHIỀU SÂU Tìm sâu là kỹ thuật tìm lời giải theo các cung của không gian bài toán theo chiều dọc, rồi xử lí theo trật tự xác định, thí dụ từ trái sang phải. 1 (1, 1) 6 (2, 1) (1, 2) 2 3 8 7 (3, 1) (2, 3) (1, 3) 4 5 (3, 2) (5, 2) (2, 5) PHƯƠNG PHÁP TẠO SINH VÀ THỬ Thuật toán gồm ba bước: Bước 1: Trước hết tạo một lời giải thử nghiệm. Cụ thể là chọn một lời giải trong không gian các lời giải, hay tạo ra một đường đi. Bước 2: Kiểm tra xem lời giải có thích hợp không bằng cách so sánh với phương án khác hay so với điểm cuối cần suy diễn. Bước 3: Nếu lời giải đạt được thì dừng và đưa ra thông báo thành công, ngược lại thì lặp lại bước một với nút khác. PHƯƠNG PHÁP LEO NÚI Thuật toán gồm năm bước: Bước 1: Tạo một phương án thử nghiệm như phương pháp tạo sinh và thử. Nếu may mắn phương án này là lời giải thì dừng, ngược lại tiếp tục thực hiện các bước sau: Bước 2: áp dụng một vài luật đối với phương án giả định để tạo ra tập các lời giải khác. Bước 3:Với mỗi lời giải vừa nhận được thực hiện các bước sau: • Kiểm tra nếu nó là lời giải cần tìm thì kết thúc công việc. • Nếu chưa được lời giải mong muốn, kiểm tra lời giải này có tốt hơn hay gần bằng lời giải đã có không. Nếu đúng thì ghi nhận phương án này, không thì bỏ qua. Bước 4: Lấy ra lời giải tốt nhất trong số các lời giải và coi nó là lời giải thử nghiệm mới. Bước này tương ứng với việc chuyển không gian bài toán theo hướng đến đích nhanh nhất. Bước 5: Tiếp tục lặp lại từ bước 2. Một ví dụ minh hoạ cho phương pháp này là việc xoay các khối màu về một vị trí xác định. Mỗi khi ...