zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

Bài giảng Trí tuệ nhân tạo (Tuần 1 - Bài 2)

Chia sẻ: Lê Na | Ngày: | Loại File: PDF | Số trang:8

Báo xấu

77
lượt xem 6
download

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

Bài giảng Trí tuệ nhân tạo (Tuần 1 - Bài 2) trình bày tổng quan về giải quyết vấn đề, phân loại vấn đề, hệ thống biết giải toán, lời giải của bài toán, mục tiêu của bài toán tìm kiếm trên không gian trạng thái, hệ thống biết lập luận. Mời các bạn cùng tham khảo.

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 Trí tuệ nhân tạo (Tuần 1 - Bài 2)

1/19/2014 Tuần 1 (Bài 2) Pham Van Hai HUST 1 AI cung cấp phương pháp luận để xây dựng hệ thống thông minh: Hệ thống biết giải toán (bằng tìm kiếm) Hệ thống biết lập luận Hệ thống biết học 2 Cơ sở của các bài toán là: trạng thái đầu (trạng thái xuất phát), các hành động biến đổi trạng thái và trạng thái kết thúc (trạng thái đích). Không gian trạng thái: là tập các trạng thái có thể đạt được bằng cách thực hiện chuỗi các hành động xuất phát từ trạng thái ban đầu. Giải bài toán : xác định trạng thái xuất phát, tìm dãy các hành động hoặc phép biến đổi (toán tử) các trạng thái sao cho từ trạng thái xuất phát có thể dẫn đến trạng thái đích. Hàm chi phí: Giá trị đánh giá chi phí thực hiện biến đổi trạng thái. 3 1
1/19/2014 Bài toán bằng kỹ thuật tìm kiếm, bài toán đó nên được xác định bởi 4 thành phần sau: ◦ Trạng thái đầu (Initial states) ◦ Trạng thái đích (Goal state) ◦ Các thao tác chuyển từ một trạng thái sang các trạng thái kế tiếp ◦ Chi phí của các thao tác 4 • ;ường đi từ trạng thái đầu đến trạng thái đích trong không gian các trạng thái của bài toán • Một trạng thái tường minh là tối ưu một hàm liên quan đến chi phí và thỏa mãn các ràng buộc của bài toán. ◦ Bài toán tìm kiếm là xác định trong không gian tìm kiếm (miền) những đối tượng mà thỏa mãn các điều kiện đặt ra. 5 Phương pháp Data-Driven-Search: Quá trình search sẽ đi từ trạng thái hiện thời áp dụng các luật để đi đến trạng thái kế tiếp và cứ thế cho đến khi đạt được một goal. Phương pháp Goal-Driven-Search: Quá trình search sẽ đi từ trạng thái hiện tại (goal tạm thời) tìm xem luật nào có thể sinh ra trạng thái này. Các điều kiện để áp dụng được các luật đó trở thành subgoal. Quá trình lặp lại cho đến khi lui về đến các sự kiện ban đầu. 6 2
1/19/2014 Không gian trạng tr ng thái (State Space) Cơ sở dữ liệu li u (Database) Không gian tìm kiếm thường là Không gian tìm kiếm là một một đồ thị (graph) danh sách (list) hay cây (tree) Mục tiêu tìm kiếm là một path Tìm kiếm một record/nút Phải lưu trữ toàn bộ không gian Phần tử đã duyệt qua là trong quá trình tìm kiếm không còn dùng tới Không gian tìm kiếm biến động Không gian tìm kiếm là cố liên tục trong quá trình tìm định trong quá trình tìm kiếm kiếm Thuộc tính của một ;ặc tính của trạng thái/nút là record/nút là cố định phức tạp & biến động 7 ◦ N: là tập nút của Graph. Mỗi nút là một trạng thái của quá trình giải quyết vấn đề ◦ A: Tập các cung nối giữa các nút N. Mỗi cung là một bước trong giải quyết vấn đề. Cung có thể có hướng ◦ S: Tập các trạng thái bắt đầu. S khác rỗng. ◦ GD: Tập các trạng thái đích. GD Không rỗng. Solution path: path Là một đường (path) đi từ một nút bắt đầu Si đến một nút kết thúc GDj . Mục tiêu của các giải thuật tìm kiếm là tìm ra một đường (path) tốt nhất. 8 Hai V Pham hai@spice.ci.ritsumei.ac.jp 9 3
1/19/2014 10 Một tập các tri thức đã biết và việc suy diễn thường được tuân theo các luật biễu diễn logics Tri thức đã biết được gọi Cơ sở tri thức (KB), tri thức muốn suy diễn ra gọi là Truy vấn (q) 11 Các đối tượng (được mô tả bởi dữ liệu) có gán nhãn (tập huấn luyện), hệ thống có khả năng khái quát hóa các đặc trưng của tập huấn luyện mà hệ thống có khả năng nhận diện hoặc dự đoán nhãn của đối tượng này. Neural Networks, SOM .. Và một số hệ học ứng dụng khác 12 4
1/19/2014 Tìm gia phả họ hàng qua các thế hệ: cụ - >ông/bà-> cha/mẹ-> con -> cháu -> chắt Trong bài toán này: ◦ Không gian trạng thái là cây phả hệ (graph) ◦ Mục tiêu tìm kiếm là đường gia phả (path) nối giữa cháu với cụ Data-Driven-Search: Tìm từ Cháu đến Cụ. nếu trung bình mỗi thế hệ có X con (Children) thì số trạng thái cần xét là X5 Goal-Driven search: Tìm từ Cụ đến Cháu Nếu mỗi người chỉ có 1 cha và 1 mẹ. Số trạng thai cần xét là 25. Phương pháp nào được áp dụng để giải quyết bài toán? 13 Tìm kiếm Các kỹ thuật tìm kiếm 14 Tìm đường đi tối ưu biểu diễn không gian trạng thái từ Arad đến Bucharest theo sơ đồ dưới đây. Sau đó viết thủ tục tìm kiếm bằng ngôn ngữ đặc tả C++, Pascal hoặc Java Hai V Pham hai@spice.ci.ritsumei.ac.jp 15 5
1/19/2014 Anh/chị hãy nêu một ví dụ ứng dụng cụ thể của một trong các hệ thống dưới đây: ◦ Hệ thống biết giải toán (bằng tìm kiếm) ◦ Hệ thống biết lập luận ◦ Hệ thống biết học Sau đó anh/chị nêu và biểu diễn bài toán ví dụ nêu trên theo các đề mục dưới đây: ◦ Phát biểu bài toán ◦ Không gian trạng thái ◦ Phương pháp giải bài toán. ◦ Hàm chi phí 16 Bài toán phát biểu chỉnh: Bài toán biết rõ đầu vào, đầu ra có thể áp dụng thuật toán một cách tường minh Bài toán phát biểu không chỉnh: Bài toán có thể giải được hoặc không giải được 17 Biểu diễn không gian trạng thái: ◦ Mỗi hình trạng tương ứng với một trạng thái (stage) ◦ Mỗi phép biến đổi hình trạng tương ứng với biến đổi của toán tử (operator) Qui bài toán tổng thể thành các bài toán con Sử dụng logic hình thức ◦ Logic mệnh đề ◦ Logic vị từ Lựa chọn các phương pháp: chia để trị, lọc thông tin, đơn giản hóa các thao tác Biểu diễn trong máy 18 6
1/19/2014 Biểu diễn trong máy 19 Giải thuật graph search tìm tất cả các path có thể có để tìm được nghiệm Graph search thực hiện bằng cách tìm theo các nhánh của graph. Khi gặp nhánh không đi tiếp được, giải thuật phải có khả năng quay lui lại trạng thái trước BACK TRACKING. Giải thuật graph search tìm tất cả các path có thể có để tìm được nghiệm Graph search thực hiện bằng cách tìm theo các nhánh của graph. Khi gặp nhánh không đi tiếp được, giải thuật phải có khả năng quay lui lại trạng thái trước BACK TRACKING. 7
1/19/2014 Procedure backtrack; Begin Cs:= first element of NSL; S:=[start]; NLS:=[start]; De:=[ ]; end; CS:=start; add CS to SL; While (NSL#[ ]) do End; Begin Else begin if CS = Goal then return(SL); add children of CS (Except if CS has no children (Except node in DE,SL and NSL) to NSL node in DE, Sl and NSL) then CS:= first element of NSL; begin add CS to SL; while ((SL#[ ]) and end; CS=First element of SL)) do end; begin add CS to DE End; {end while} remove first element from SL; Return FAIL; remove first element End; from NSL; 8

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.