Giáo trình Trí Tuệ Nhân Tạo Chương II

Chia sẻ: Bum Ba La | Ngày: | Loại File: PDF | Số trang:131

Thêm vào BST

Báo xấu

81
lượt xem 22
download

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

Khi giải quyết bài toán bằng phương pháp tìm kiếm: phải xác định không gian tìm kiếm.

Chủ đề:

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

Lưu

Nội dung Text: Giáo trình Trí Tuệ Nhân Tạo Chương II

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
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 2
Chương 2 Các phương pháp giải quyết vấn đề cơ bản Biểu diễn bài toán trong không gian trạng thái 2.1 Tìm kiếm lời giải trong không gian trạng thái 2.2 Tìm kiếm lời giải trên đồ thị và/hoặc 2.3 12/04/10 3
2.1 Biểu diễn bài toán trong không gian trạng thái 2.1.1 Đặt vấn đề Mô tả trạng thái 2.1.2 Toán tử chuyển trạng thái 2.1.3 Không gian trạng thái của bài toán 2.1.4 Biểu diễn không gian trạng thái dưới dạng đồ 2.1.5 thị 12/04/10 4
2.1 Biểu diễn bài toán trong không gian trạng thái 2.1.1. Đặt vấn đề  Khi giải quyết bài toán bằng phương pháp tìm kiếm: phải xác định không gian tìm kiếm.  Phương pháp giải quyết vấn đề dựa trên: khái niệm trạng thái (state) và  toán tử (operator)  được gọi là cách tiếp cận giải quyết vấn đề nhờ không gian trạng thái. 12/04/10 5
2.1 Biểu diễn bài toán trong không gian trạng thái 2.1.1 Đặt vấn đề Mô tả trạng thái 2.1.2 Toán tử chuyển trạng thái 2.1.3 Không gian trạng thái của bài toán 2.1.4 Biểu diễn không gian trạng thái dưới dạng đồ 2.1.5 thị 12/04/10 6
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  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.  12/04/10 7
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 Ví dụ: Bài toán đong nước m lit. n lit Cần đong k lit nước. giả thiết k
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 Ví dụ: Bài toán đong nước  Gọi x là lượng nước hiện có trong bình dung tích m  và y là lượng nước hiện có trong bình dung tích n.  bộ có thứ tự (x,y) có thể xem là trạng thái của bài toán.  Trạng thái đầu: (0,0)  Trạng thái cuối: (x,k) hoặc (k,y), 0 ≤ x ≤ m , 0 ≤ y ≤ n 12/04/10 9
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 Ví dụ: Bài toán trò chơi 8 số 2 8 3 1 2 3 8 4 1 6 4 7 5 7 6 5 Hình trạng đầu Hình trạng cuối 12/04/10 10
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  Có thể mô tả trạng thái của bài toán bằng một ma trận A3*3 = (aij) , aij∈ {0..8}, aij akl, ∀ ik, j l  1 2 3  2 8 3      8 0 4 1 6 4  7 6 5 7 0 5     Trạng thái cuối Trạng thái đầu 12/04/10 11
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 Ví dụ: Bài toán tháp Hà Nội 1 2 3 Hãy dịch chuyển n đĩa ở cọc 1 sang cọc 3 sao cho:  Mỗi lần chỉ chuyển một đĩa.  Trong mỗi cọc không cho phép đĩa to nằm trên đĩa nhỏ hơn.  12/04/10 12
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 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) 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 13
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  Cách 1 ta phải dùng 3 danh sách động.  Cách 2 mô tả bài toán hiệu quả hơn. Nếu gọi xi là cọc chứa đĩa lớn thứ i, trong đó xi∈ {1, 2, 3},  i∈ {1..n}. Khi đó bộ có thứ tự (x1, x2, . . ,xn) là dạng mô tả trạng thái  đang xét của bài toán. Trạng thái đầu là (1,1,. . .,1)  Trạng thái cuối là (3,3,. . .,3)  12/04/10 14
2.1 Biểu diễn bài toán trong không gian trạng thái 2.1.1 Đặt vấn đề Mô tả trạng thái 2.1.2 Toán tử chuyển trạng thái 2.1.3 Không gian trạng thái của bài toán 2.1.4 Biểu diễn không gian trạng thái dưới dạng đồ 2.1.5 thị 12/04/10 15
2.1 Biểu diễn bài toán trong không gian trạng thái 2.1.3. Toán tử chuyển 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. 12/04/10 16
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 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,  đổ nước từ bình này sang bình khác.  12/04/10 17
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  Nếu trạng thái đang xét là (x,y) thì các trạng thái kế tiếp có thể chuyển đến sẽ là: 12/04/10 18
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 Ví dụ: Trò chơi 8 số  Các thao tác để chuyển trạng thái tương ứng với việc chuyển ô trống sang phải, sang trái, lên, xuống nếu có thể được.  Biểu diễn theo quy tắc sản xuất 12/04/10 19
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 Biểu diễn theo một hàm   Gọi f là hàm biểu diễn toán tử chuyển ô trống lên trên; u Gọi B (B= (bij)) là trạng thái sau khi di chuyển ô trống ở trạng  thái A (A= (aij)) lên trên, nghĩa là: B= fu(A), giả sử ô trống đang ở vị trí (i0, j0) (hay nói cách khác ai0 j0 = 0) thì hàm fu được xác định như sau: 12/04/10 20