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! | THUẬT TOÁN THUẬT GIẢI MỘ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án 06 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ước 06 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 gt 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à S 06 10 2009 Nhập môn Trí tuệ nhân tạo 7 Thuật toán Thuật toán có thể được thể hiện qua Ngôn ngữ tự nhiên Lưu đồ Mã giả NN lập trình Ngoài ra thuật toán còn phải đạt hiệu quả cao hay có độ phức tạp thấp 06 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 .
