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 Đối tượng Thuộc tính Giá trị 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 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ÁC KHUNG 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: 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: 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. 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 xoay các khối màu chuyển trạng thái. Người ta xoay các khối màu với hi vọng đưa chúng về càng gần đích càng tốt. KỸ THUẬT HEURISTICS KHÁI NIỆM May rủi là thuật ngữ chỉ các luật suy đoán có phương pháp, kinh nghiệm, kiểm chứng theo cảm tính hay cảm giác chung đơn sơ. CÁC HÀM SỐ HEURISTICS Dạng tổng quát f(p) = f( t1, t2,..., tn) Ở đây ứng với mỗi khả năng p, hàm đánh giá f cho một giá trị f( t1, t2,..., tn) là hàm giải tích phụ thuộc vào các giá trị của các tham số t1, t2,..., tn đặc trưng cho khả năng p. Ví dụ: Xét bài toán tìm đường đi ngắn nhất, với mỗi đỉnh p hàm đánh giá f(p) là ước lượng đường chim bay từ p tới đích. CÁC CHƯƠNG TRÌNH MINH HOẠ BÀI TOÁN BIẾN ĐỔI CẶP SỐ Input: Cặp số (a, b) và số N. Output: Dãy phép biến đổi sao cho a hoặc b bằng N. Ta có thể biểu diễn trên cây như sau: BÀI TOÁN BỐC DIÊM Input: Ba số nguyên dương a, b, c. Output: Dãy trạng thái mô tả các lần bốc diêm để thu được trạng thái ba đống diêm có số lượng bằng nhau (a' = b' = c'). Ta có thể biểu diễn trên cây như sau: BÀI TOÁN THÁP HÀ NỘI Input: Số lượng đĩa n, trạng thái ban đầu T0 và trạng thái đích Tđ. Output: Dãy mô tả sự dịch chuyển n đĩa từ trạng thái xuất phát đến trạng thái đích. Hàm Heuristics: h(T) = khoảng cách từ trạng thái hiện tại đến trạng thái đích. Ví dụ: Số đĩa là 4 Trạng thái các đĩa: 3 3 3 3 khi đó h(T) = 4 - 4 + 0 = 0 Trạng thái các đĩa: 3 x 3 3 khi đó h(T) = 4 -1 + 2 = 5 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