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: (cid:1) Hệ thống biết giải toán (bằng tìm kiếm) (cid:1) Hệ thống biết lập luận (cid:1) Hệ thống biết học
(cid:1) 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).
(cid:1) 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.
(cid:1) 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.
(cid:1) Hàm chi phí: Giá trị đánh giá chi phí thực hiện
biến đổi trạng thái.
2
3
1
1/19/2014
(cid:1) 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
(cid:1) • ;ườ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
(cid:1) • 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.
4
(cid:1) 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.
(cid:1) 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.
5
6
2
1/19/2014
CơCơCơCơ ssssở ddddữ lilililiệuuuu ((((Database) Database) Database) Database)
Không giangiangiangian trtrtrtrạngngngng thái State Space) thái ((((State Space) Không State Space) State Space) thái thái Không Không
(cid:1) Không gian tìm kiếm là một
(cid:1) Không gian tìm kiếm thường là
danh sách (list) hay cây (tree)
một đồ thị (graph)
(cid:1) Mục tiêu tìm kiếm là một path (cid:1) Phải lưu trữ toàn bộ không gian
(cid:1) Tìm kiếm một record/nút (cid:1) Phần tử đã duyệt qua là không còn dùng tới
trong quá trình tìm kiếm
(cid:1) Không gian tìm kiếm là cố
(cid:1) Không gian tìm kiếm biến động
định trong quá trình tìm kiếm
liên tục trong quá trình tìm kiếm
(cid:1) Thuộc tính của một
record/nút là cố định
(cid:1) ;ặc tính của trạng thái/nút là
phức tạp & biến động
◦ 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: Là một đường (path) đi từ một nút bắt (cid:1) Solution path Solution path Solution path đầu Si đến một nút kết thúc GDj .
(cid:1) 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.
7
8
Hai V Pham hai@spice.ci.ritsumei.ac.jp 9
3
1/19/2014
(cid:1) 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
(cid:1) 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)
10
(cid:1) 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.
(cid:1) Neural Networks, SOM (cid:1) .. Và một số hệ học ứng dụng khác
11
12
4
1/19/2014
(cid:1) Tìm gia phả họ hàng qua các thế hệ: cụ -
>ông/bà-> cha/mẹ-> con -> cháu -> chắt
(cid:1) 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 ccccụ cháu cháucháu
(cid:1) Data-Driven-Search: Tìm từ CháuCháuCháuCháu đến CCCCụ.
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
(cid:1) Goal-Driven search: Tìm từ CCCCụ đến CháuCháuCháuChá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?
Tìm kiếm
Các kỹ thuật tìm kiếm
13
(cid:1) 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
14
Hai V Pham hai@spice.ci.ritsumei.ac.jp 15
5
1/19/2014
(cid:1) 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
(cid:1) 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
(cid:1) 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)
(cid:1) Qui bài toán tổng thể thành các bài toán con (cid:1) Sử dụng logic hình thức
◦ Logic mệnh đề ◦ Logic vị từ
(cid:1) Lựa chọn các phương pháp: chia để trị, lọc
17
thông tin, đơn giản hóa các thao tác
(cid:1) Biểu diễn trong máy
18
6
1/19/2014
(cid:1) Biểu diễn trong máy
(cid:1) Giải thuật graph search tìm tất cả các path có
19
thể có để tìm được nghiệm
(cid:1) Graph search thực hiện bằng cách tìm theo
các nhánh của graph.
(cid:1) 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.
(cid:1) Giải thuật graph search tìm tất cả các path có
thể có để tìm được nghiệm
(cid:1) Graph search thực hiện bằng cách tìm theo
các nhánh của graph.
(cid:1) 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
Cs:= first element of NSL; end;
add CS to SL; End; Else begin
Procedure backtrack; Begin S:=[start]; NLS:=[start]; De:=[ ]; CS:=start; While (NSL#[ ]) do Begin if CS = Goal then return(SL); if CS has no children (Except
node in DE, Sl and NSL) then
begin
add children of CS (Except node in DE,SL and NSL) to NSL CS:= first element of NSL; add CS to SL;
while ((SL#[ ]) and
end;
CS=First element of SL)) do
begin add CS to DE
remove first element
from SL;
end; End; {end while} Return FAIL; End;
remove first element
from NSL;
