Bài giảng Cơ sở Trí tuệ nhân tạo‎: Chương 2 - ThS. Phạm Thi Vương

Bài giảng Cơ sở Trí tuệ nhân tạo‎: Chương 2 Thuật toán, thuật giải một số phương pháp giải quyết vấn đề, cung cấp cho người học những kiến thức như: Vấn đề, giải quyết vấn đề; Khái niệm về thuật toán, thuật giải; Các nguyên lý của thuật giải heuristic; Các chiến lược tìm kiếm và Thuật giải A. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Cơ sở Trí tuệ nhân tạo‎: Chương 2 - ThS. Phạm Thi Vương THUẬT TOÁN, THUẬT GIẢIMỘT SỐ PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ Nội dung• Vấn đề, giải quyết vấn đề• Khái niệm về thuật toán, thuật giải• Các nguyên lý của thuật giải heuristic• Các chiến lược tìm kiếm và Thuật giải A*06/10/2009 Nhập môn Trí tuệ nhân tạo 2 Vấn đề? Những vướng mắc khó khăn cần giải quyết Một yêu cầu tìm kiếm xử lý trong một ngữ cảnh cụ thể Bao gồm: - các sự kiện - các thông tin - những ràng buộc nhất định. vấn đề = bài toán06/10/2009 Nhập môn Trí tuệ nhân tạo 3 Mô hình vấn đề AB A: giả thiết, điều kiện ban đầu B: kết luận cần đạt đến : suy luận hay giải pháp cần xác định = một số hữu hạn bước06/10/2009 Nhập môn Trí tuệ nhân tạo 4 Phân loại vấn đề• Xác định rõ - A, B đều rõ• Chưa rõ - A rõ, B chưa rõ - A chưa rõ, B rõ - A, B đều chưa rõ06/10/2009 Nhập môn Trí tuệ nhân tạo 5 Thuật toán• Thuật toán là giải pháp viết dưới dạng thủ tục và thỏa 3 tiêu chuẩn Xác định : không mập mờ và có thể thực thi được Hữu hạn Đúng Thuật toán là một dãy hữu hạn các bước không mập mờ và có thể thực thi được, quá trình hành động theo các bước này phải dừng và cho kết quả mong muốn.06/10/2009 Nhập môn Trí tuệ nhân tạo 6 Thuật toán• Tính tổng các số nguyên dương lẻ từ 1n – B1: S=0; – B2: i=1 – B3: Nếu i=n+1 i>n thì sang bước 7, ngược lại sang bước 4 – B4: S=S+i – B5: i=i+2 – B6: Quay lại 3 – B7: Tổng cần tìm là S06/10/2009 Nhập môn Trí tuệ nhân tạo 7 Thuật toánThuật toán có thể được thể hiện qua: Ngôn ngữ tự nhiên Lưu đồ Mã giả NN lập trìnhNgoài ra thuật toán còn phải đạt hiệu quả cao hay có độ phức tạp thấp06/10/2009 Nhập môn Trí tuệ nhân tạo 8 Thuật toán O(log2 n)   O(n)   O(nlog2 n) ®é phøc t¹p ®a thøc  chÊp nhËn ®îc  O(n 2 )  O(n k )  O(2n )  ®é phøc t¹p cao  khã chÊp nhËn n! 06/10/2009 Nhập môn Trí tuệ nhân tạo 9 Một số ví dụ về bài toán có độ phức tạp cao• Bài toán phân công công việc Một đề án gồm n công việc và các việc sẽ đưọc thực hiên bởi m máy như nhau. Giả sử biết thời gian để 1 máy thực hiện viêc thứ j là tj Yêu cầu: Tìm phương án phân công sao cho thời gian hoàn thành toàn bộ công việc là thấp nhất. Mẫu số liệu n=10, m=3 tj = 4 9 5 2 7 6 10 8 7 506/10/2009 Nhập môn Trí tuệ nhân tạo 10 Một số ví dụ về bài toán có độ phức tạp cao• Bài toán tô màu Giả sử ta có bản đồ các 9 quốc gia trên thế giới, ta 1 6 muốn tô màu các quốc gia này sao cho các nước khác nhau được tô khác 0 2 5 màu. 7 8 Yêu cầu tìm cách tô sao 3 4 cho số màu sử dụng là ít nhất.06/10/2009 Nhập môn Trí tuệ nhân tạo 1106/10/2009 Nhập môn Trí tuệ nhân tạo 12 Một số ví dụ về bài toán có độ phức tạp caoBài toán người đưa thư• Giả sử có một đồ thị có trọng số dương, tìm đường đi ngắn nhất qua tất cả các đỉnh của đồ thị rồi trở về đỉnh ban đầu A 5 1 E 3 B 7 2 2 4 3 406/10/2009 Nhập môn Trí tuệ nhân tạoD 1 C 13 Thuật giải• Thuật giải: giải pháp được viết ...