intTypePromotion=1

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

0
64
lượt xem
12
download

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

Mô tả tài liệu
  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ủ đề:
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

  1. 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
  2. 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
  3. 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, …
  4. Đặ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 ???
  5. Đặ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
  6. Đặ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ự
  7. 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
  8. 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
  9. 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
  10. 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;
  11. 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 …
  12. 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ý
  13. 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:
  14. Độ 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?
  15. 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
  16. 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
  17. 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ả.
  18. 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ờ”
  19. 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
  20. Đặ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
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2