TR NG CAO Đ NG CNTT H U NGH Vi T - HÀNƯỜ Ẳ Ữ Ị Ệ
KHOA KHOA H C MÁY TÍNHỌ
***
TRÍ TUỆ NHÂN TẠO
(Artificial Intelligence - AI)
Nguyễn Thanh Cẩm
12/04/10 2
Contents
Tổng quan về khoa học trí tuệ nhân tạo
1
Các phương pháp giải quyết vấn đề cơ bản
2
Tri thức và các phương pháp biểu diễn tri thức
3
Máy học
4
Mạng Nơron
5
12/04/10 3
Chương 2
Các ph ng pháp gi i quy t v n đ c b nươ ả ế ấ ề ơ ả
Các ph ng pháp gi i quy t v n đ c b nươ ả ế ấ ề ơ ả
2.1
2.2
2.3
Biểu diễn bài toán trong không gian trạng thái
Tìm kiếm lời giải trong không gian trạng thái
Tìm kiếm lời giải trên đồ thị và/hoặc
12/04/10 4
2.1.1
2.1.2

Mô t tr ng tháiả ạ
Toán t chuy n tr ng tháiử ể ạ
Không gian tr ng thái c a bài toánạ ủ
2.1 Biểu diễn bài toán trong không gian trạng thá i
Bi u di n không gian tr ng thái d i d ng đ ể ễ ạ ướ ạ ồ
thị
2.1.5
12/04/10 7
2.1 Biểu diễn bài toán trong không gian trạng thá i

Mô tả trạng thái bài toán:

các xâu ký hiệu,

véctơ,

mảng hai chiều,

cây,

danh sách.

Mỗi trạng thái là một hình trạng của bài toán:

hình trạng đầu gọi là trạng thái đầu

hình trạng cuối gọi là trạng thái cuối.
2.1.2. Mô tả trạng thá i
12/04/10 8
2.1 Biểu diễn bài toán trong không gian trạng thá i

1
2
3
8
4
7
6
5
Hình trạng đầu Hình trạng cuối
Ví dụ: Bài toán trò chơi 8 số
12/04/10 11
2.1 Biểu diễn bài toán trong không gian trạng thá i

Có th mô t tr ng thái c a bài toán b ng m t ma tr n ể ả ạ ủ ằ ộ ậ
A
3*3
= (a
ij
) , a
ij
∈{0 8}, a
ij
<> a
kl
, ∀i<>k, j<> l







Trong mỗi cọc không cho phép đĩa to nằm trên đĩa nhỏ hơn.
2.1.2. Mô tả trạng thá i
1 2 3
Ví dụ: Bài toán tháp Hà Nội
12/04/10 13
2.1 Biểu diễn bài toán trong không gian trạng thá i
Ví dụ: Bài toán tháp Hà Nội

Bài toán xác định khi biết từng đĩa đang nằm ở cọc nào.

Cách 1:

Cọc 1 hiện đang chứa những đĩa nào?

Cọc 2 hiện đang chứa những đĩa nào?

Và cọc 3 đang chứa những đĩa nào.

Cách 2:

Đĩa lớn thứ i hiện đang nằm ở cọc nào?
(i = 1 n)
2.1.2. Mô tả trạng thá i
Như vậy cách mô tả trạng thái bài toán không duy nhất, vấn đề là chọn
cách mô tả nào để đạt được mục đích dễ dàng nhất.
12/04/10 14
2.1 Biểu diễn bài toán trong không gian trạng thá i

Cách 1 ta phải dùng 3 danh sách động.

Toán t chuy n tr ng tháiử ể ạ
Không gian tr ng thái c a bài toánạ ủ
2.1 Biểu diễn bài toán trong không gian trạng thá i
Bi u di n không gian tr ng thái d i d ng đ ể ễ ạ ướ ạ ồ
thị
2.1.5
12/04/10 16
2.1 Biểu diễn bài toán trong không gian trạng thá i

Là các phép biến đổi đưa từ trạng thái này sang trạng
thái khác.

Có hai cách biểu diễn các toán tử:

Biểu diễn hàm xác định trên tập các trạng thái và nhận
giá trị cũng trong tập này.

Biểu diễn dưới dạng các quy tắc sản xuất S→A có nghĩa
là nếu có trạng thái S thì có thể đưa đến trạng thái A.
2.1.3. Toán tử chuyển trạng thái
12/04/10 17
2.1 Biểu diễn bài toán trong không gian trạng thá i
Ví dụ: Bài toán đong nước

Các thao tác sử dụng để chuyển trạng thái này sang
trạng thái khác gồm:

Đổ đầy một bình,

đổ hết nước trong một bình ra ngoài,

thái A (A= (a
ij
)) lên trên, nghĩa là: B= f
u
(A), giả sử ô trống đang ở
vị trí (i
0
, j
0
) (hay nói cách khác a
i0 j0
= 0) thì hàm f
u
được xác định
như sau:
2.1.2. Mô tả trạng thá i
12/04/10 21
2.1 Biểu diễn bài toán trong không gian trạng thá i
2.1.2. Mô tả trạng thá i
Phép chuy n ô tr ng xu ng d i fể ố ố ướ
d
, qua trái f
l
, qua ph i fả
r
nh sau:ư
12/04/10 22
2.1 Biểu diễn bài toán trong không gian trạng thá i
Ví dụ: Bài toán Tháp Hà Nội với n = 3



KGTT là một bộ bốn: K= (T, S, G, F). Trong đó:

T: tập tất cả các trạng thái có thể có của bài toán

S: trạng thái đầu

G: tập các trạng thái đích

F: tập các toán tử
2.1.4. Không gian trạng thái của bài toán