Bài giảng Cơ sở Trí tuệ nhân tạo‎: Chương 2 - Trần Minh Thái

Chia sẻ: Năm Tháng Tĩnh Lặng | Ngày: | Loại File: PPTX | Số trang:83

Thêm vào BST

Báo xấu

88
lượt xem 14
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Cơ sở Trí tuệ nhân tạo‎: Chương 2 trình bày các nội dung: Thuật toán là gì? Thuật toán và thuật giải, thuật giải Heuristic & các nguyên lý, tìm kiếm chiều sâu & tìm kiếm chiều rộng, tìm kiếm leo đồi, tìm kiếm ưu tiên tối ưu, một số thuật giải cơ bản. Mời các bạn cùng tham khảo để nắm bắt các nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cơ sở Trí tuệ nhân tạo‎: Chương 2 - Trần Minh Thái

Chương 2. Thuật toán – Thuật giải TRẦN MINH THÁI Email: minhthai@huflit.edu.vn Website: www.minhthai.edu.vn 1 Cập nhật: 05 tháng 09 năm 2015
Nội dung #2 1. Thuật toán? 2. Thuật toán vs Thuật giải 3. Thuật giải Heuristic & các nguyên lý 4. Tìm kiếm chiều sâu & Tìm kiếm chiều rộng 5. Tìm kiếm leo đồi 6. Tìm kiếm ưu tiên tối ưu 7. Một số thuật giải cơ bản
Thuật toán? #3 • Là một thủ tục tính toán xác định nhận các giá trị hoặc một tập các giá trị (input) và sinh ra một vài giá trị hoặc tập giá trị (output) è Cách thức/ quy trình thực hiện hoàn thành một công việc xác định cụ thể nào đó. VD Cộng 2 số, tính tổng dãy Fibonaci, …
Đặc trưng của Thuật toán #4 1. Tính đúng đắn 2. Tính dừng 3. Tính xác định 4. Tính hiệu quả 5. Tính phổ quát ??? Đặc trưng nào quan trọng nhất ???
Đặc trưng của Thuật toán … #5 [1] Tính đúng đắn * Đảm bảo kết quả đúng sau khi thực hiện đối với bộ dữ liệu đầu vào [2] Tính dừng Dừng  Sau một vài bước thực hiện
Đặc trưng của Thuật toán … #6 [3] Tính xác định - Rõ ràng, cụ thể - Không nhập nhằng, gây hiểu lầm  hiểu, cài đặt [4] Tính hiệu quả - Giải quyết trong thời gian, điều kiện cho phép - Đáp ứng yêu cầu người dùng [5] Tính phổ quát Có thể giải quyết được một lớp bài toán tương tự
Cách biểu diễn thuật toán #7 02 cách phổ biến [1] Mô tả các bước thực hiện của thuật toán [2] Sử dụng sơ đồ thuật toán
Cách biểu diễn thuật toán #8 [1] Mô tả các bước thực hiện của thuật toán - Ngôn ngữ tự nhiên - Mã giả (Pseudocode): Lai ghép ngôn ngữ tự nhiên với mã của ngôn ngữ lập trình
VD Mô tả các bước thực hiện của thuật toán tìm USCLN của hai số nguyên – NN tự nhiên #9 • Input: Hai số nguyên a, b • Output: USCLN của a và b • Thuật toán: • Bước 1: Nếu a = b thì USCLN là a • Bước 2: Nếu a > b thì tìm USCLN của a - b và b, quay lại Bước 1 • Bước 3: Nếu a < b thì tìm USCLN của a và b - a, quay lại Bước 1
VD Mô tả các bước thực hiện của thuật toán tìm USCLN của hai số nguyên – Mã giả #10 • Input: Hai số nguyên a, b • Output: USCLN của a và b • Thuật toán: WHILE (a ≠ b) DO IF (a > b) THEN a = a – b; ELSE b = b – a; END WHILE RETURN a;
Một số từ khóa mã giả cơ bản #11 IF THEN …ENDIF IF THEN ... ELSE ... ENDIF WHILE DO … ENDWHILE DO … UNTIL DISPLAY … RETURN …
Cách biểu diễn thuật toán #12 [2] Sử dụng sơ đồ thuật toán (flowchart) Dùng các ký hiệu hình học để biểu diễn quá trình thực hiện Nhập/ xuất Bắt đầu/ kết thúc Trả về giá trị Điều Rẽ nhánh kiện Khối xử lý Luồng xử lý
VD Sơ đồ thuật toán tìm trị tuyệt đối của số nguyên #13 • Input: Số nguyên n • Output: Giá trị tuyệt đối của n • Thuật toán:
Độ phức tạp thuật toán #14 • Đánh giá độ tốt/ xấu của thuật toán cùng loại • Đơn giản, dễ hiểu, dễ cài đặt • Thời gian thực hiện, sử dụng tài nguyên hệ thống ??? Thực tế ??? - Thuật toán hiệu quả  Dễ hiểu, dễ cài đặt? - Ước lượng số phép tính thực hiện  Thời gian?
VD Thuật toán sắp xếp mảng một chiều bằng phương pháp đổi chỗ trực tiếp #15 • Input: Mảng một chiều a, kích thước N • Ouput: Mảng a có thứ tự tăng dần • Thuật toán: Bước 1: i=1; Bước 2: j = i+1; Bước 3: Trong khi j
Thuật toán vs Thuật giải #16 Tuy nhiên • Nhiều bài toán chưa tìm ra một cách giải theo kiểu thuật toán/ không biết là có tồn tại thuật toán? • Nhiều bài toán đã có thuật toán nhưng không chấp nhận được vì thời gian quá lớn/ điều kiện khó đáp ứng • Nhiều bài toán được giải theo những cách giải vi phạm thuật toán nhưng vẫn chấp nhận được
Thuật toán vs Thuật giải #17 • Tiêu chuẩn: tính xác định và tính đúng đắn được mở rộng  Tính xác định thay đổi: giải thuật đệ quy và ngẫu nhiên  Tính đúng không còn bắt buộc: cách giải gần đúng  Chấp nhận các cách giải thường cho kết quả tốt (nhưng không phải lúc nào cũng tốt) nhưng ít phức tạp và hiệu quả.
Thuật toán vs Thuật giải #18 Lựa chọn? “giải một bài toán bằng thuật toán tối ưu đòi hỏi máy tính thực hiện nhiều năm” hay “một giải pháp gần tối ưu mà chỉ cần máy tính chạy trong vài ngày hoặc vài giờ”
Khái niệm thuật giải #19 • Cách giải chấp nhận được nhưng không hoàn toàn đáp ứng đầy đủ các tiêu chuẩn của thuật toán thường được gọi là các thuật giải  Dễ dàng hơn trong việc tìm kiếm phương pháp để giải quyết các bài toán được đặt ra  Trong AI thường sử dụng cách giải theo kiểu Heuristic
Đặc điểm thuật giải Heuristic #20 • Thường tìm được lời giải tốt (nhưng không chắc là lời giải tốt nhất) • Dễ dàng và nhanh chóng đưa ra kết quả hơn so với giải thuật tối ưu  chi phí thấp hơn • Thể hiện khá tự nhiên, gần gũi với cách suy nghĩ và hành động của con người