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 Hệ thống thông minh: Phần 2 - Biểu diễn vấn đề trong không gian trạng thái

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:36

Báo xấu

2
lượt xem 0
download

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

Bài giảng "Hệ thống thông minh: Phần 2 - Biểu diễn vấn đề trong không gian trạng thái" bao gồm các nội dung chính sau đây: Định nghĩa không gian trạng thái; tìm kiếm trong không gian trạng thái; các hệ sản xuất; các đặc trưng bài toán; các đặc trưng hệ sản xuất; các vấn đề trong thiết kế các chương trình tìm kiếm. 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 Hệ thống thông minh: Phần 2 - Biểu diễn vấn đề trong không gian trạng thái

BIỂU DIỄN VẤN ĐỀ TRONG KHÔNG GIAN TRẠNG THÁI Modelling the Problem By State Space
NỘI DUNG 1. Định nghĩa không gian trạng thái 2. Tìm kiếm trong không gian trạng thái 3. Các hệ sản xuất 4. Các đặc trưng bài toán 5. Các đặc trưng hệ sản xuất 6. Các vấn đề trong thiết kế các chương trình tìm kiếm 7. Bài tập 2
ĐỊNH NGHĨA KHÔNG GIAN TRẠNG THÁI (KGTT) • Một không gian trạng thái là một bộ bốn , trong đó: • N là một tập các trạng thái/ nút • A là một tập các liên kết/ cung giữa các trạng thái/ nút • S là một tập con không rỗng của N, bao gồm các trạng thái ban đầu của bài toán • GD là một tập con không rỗng của N, bao gồm các trạng thái đích của bài toán. Tập GD được xác định bởi: – Một liệt kê các trạng thái/ một tính chất có thể đo lường được của các trạng thái cần đạt tới trong quá trình tìm kiếm – Một tính chất của đường đi (path) • Một đường đi lời giải là một đường đi trong đồ thị KGTT, dẫn từ một trạng thái trong S đến một trạng thái trong GD 3
ĐỊNH NGHĨA KHÔNG GIAN TRẠNG THÁI (KGTT) (cont.) • Ví dụ: bài toán (n2-1)-puzzle một lưới nxn ô vuông, n2-1 ô chứa các số nguyên 1, 2, …, n2-1, ô còn lại trống. Xuất phát từ một cấu hình đã cho, bằng một dãy các di chuyển các ô số sang ô trống để đạt tới một cấu hình cho trước. • 15-puzzle Trạng thái ban đầu Trạng thái đích 11 14 4 7 1 2 3 4 10 6 5 12 13 14 5 1 2 13 15 11 15 6 9 12 8 3 10 9 8 7 Biểu diễn bài toán như thế nào ? 4
ĐỊNH NGHĨA KHÔNG GIAN TRẠNG THÁI (KGTT) (cont.) • Tập các trạng thái: Lưới (mảng hai chiều) các ô, trong đó n2 – 1 ô chứa các số từ 1 đến n2 – 1 và một ô trống • Tập các cung « biến đổi trạng thái » (các toán tử): – L(eft): phép dịch chuyển ô trống sang trái – U(p): phép dịch chuyển ô trống lên trên – R(ight): phép dịch chuyển ô trống sang phải – D(own): phép dịch chuyển ô trống xuống dưới ? Điều kiện để các phép biến đổi này có thể thực hiện được  (tiền điều kiện – precondition) dạng của một toán tử: → 5
ĐỊNH NGHĨA KHÔNG GIAN TRẠNG THÁI (KGTT) (cont.) L(s): (hoành độ ô trống > 1) → (hoán vị ô trống với ô bên trái nó) Gọi (x(s), y(s)) là toạ độ ô trống trong s, toán tử L(s) có thể viết như sau: if (x(s) > 1) { ; t=ss[x(s)-1][y(s)]; ss[x(s)-1][y(s)]=ss[x(s)][y(s)]; ss[x(s)][y(s)]=t; } Tương tự với các toán tử còn lại • Tập các trạng thái ban đầu: cấu hình xuất phát • Tập các trạng thái đích: cấu hình đích 6
ĐỊNH NGHĨA KHÔNG GIAN TRẠNG THÁI (KGTT) (cont.) Có khả năng xảy ra vòng lặp không? 7
ĐỊNH NGHĨA KHÔNG GIAN TRẠNG THÁI (KGTT) (cont.) Bài toán TSP(Traveling Saleman Problem) Biểu diễn bài toán ? 8
ĐỊNH NGHĨA KHÔNG GIAN TRẠNG THÁI (KGTT) (cont.) Mỗi cung được đánh dấu bằng tổng giá của con đường từ nút bắt đầu đến nút hiện tại. 9
ĐỊNH NGHĨA KHÔNG GIAN TRẠNG THÁI (KGTT) (cont.) • Sau khi biểu diễn vấn đề trong không gian trạng thái, việc tìm lời giải cho vấn đề = tìm kiếm trong không gian trạng thái. • Đích của tìm kiếm có thể là: – Một trạng thái đích – Một đường đi lời giải – Một đường đi thoả điều kiện GD 10
TÌM KIẾM TRONG KHÔNG GIAN TRẠNG THÁI • Các chiến lược tìm kiếm trong không gian trạng thái – Tìm kiếm hướng dữ liệu (Data Driven Search)/ tìm kiếm tiến/ dây chuyền tiến (Forward Chaining): Tìm kiếm xuất phát từ một trạng thái khởi đầu, tìm các trạng thái có thể đạt tới từ nó bởi « một phép biến đổi », tiếp tục tìm kiếm như vậy đối với các trạng thái vừa tìm thấy … đến khi tìm thấy một trạng thái đích hoặc thất bại – Tìm kiếm hướng mục tiêu (Goal Driven Search)/ tìm kiếm lùi/ dây chuyền lùi (Backward Chaining): Tìm kiếm xuất phát từ đích, tìm các trạng thái có thể đạt tới đích bởi « một phép biến đổi », tìm các trạng thái có thể đạt tới các trạng thái tìm thấy ở bước trước bằng « một phép biến đổi » … đến khi tìm thấy một trạng thái khởi đầu hoặc thất bại. – Tìm kiếm hai hướng: hướng dữ liệu, hướng mục tiêu, kiểm tra tập « đạt tới » của tìm hướng DL, và tập « có thể đi đến đích » của tìm hướng mục tiêu có « điểm chung » nếu có tìm được một lời giải 11
TÌM KIẾM TRONG KHÔNG GIAN TRẠNG THÁI (cont.) Việc tìm kiếm đi từ dữ liệu đến mục tiêu • Thích hợp khi: – Tất cả hoặc một phần dữ liệu được cho từ đầu. – Có nhiều mục tiêu, nhưng chỉ có một số ít các phép toán có thể áp dụng cho một trạng thái bài toán. – Rất khó đưa ra một mục tiêu hoặc giả thuyết ngay lúc đầu. 12
TÌM KIẾM TRONG KHÔNG GIAN TRẠNG THÁI (cont.) Việc tìm kiếm đi từ mục tiêu trở về dữ liệu. • Thích hợp khi: – Có thể đưa ra mục tiêu hoặc giả thuyết ngay lúc đầu. – Có nhiều phép toán có thể áp dụng trên 1 trạng thái của bài toán => sự bùng nổ số lượng các trạng thái. – Các dữ liệu của bài toán không được cho trước, nhưng hệ thống phải đạt được trong quá trình tìm kiếm. 13
TÌM KIẾM TRONG KHÔNG GIAN TRẠNG THÁI (cont.) • Các phương pháp tìm kiếm trên đồ thị KGTT (tìm kiếm thiếu thông tin – tìm kiếm mù) – Tìm kiếm rộng (Breath First Search) – Tìm kiếm sâu (Depth First Search) – Tìm kiếm sâu dần (Depth First Search With Iterative deepening) 14
TÌM KIẾM TRONG KHÔNG GIAN TRẠNG THÁI (cont.) Function breath_first_search; Var Open: Queue of Node; Closed: Set of Node; Begin Open := [Start]; Closed :=[ ]; while not Empty(Open) do begin X:= Front(Open); Dequeue(Open); If then return( success ) else begin For mỗi toán tử trạng thái Op có thể áp dụng lên Xdo begin If not member(Op(X), Open) and not member(Op(X), Closed) then Enqueue(O(X), Open); Insert(X, Closed); end; end; return( fail) End; 15
TÌM KIẾM TRONG KHÔNG GIAN TRẠNG THÁI (cont.) Tìm kiếm rộng – Breath First Search Open = [A]; closed = [] Open = [B,C,D]; closed = [A] Open = [C,D,E,F]; closed = [B,A] Open = [D,E,F,G,H]; closed = [C,B,A] Open = [E,F,G,H,I,J]; closed = [D,C,B,A] Open = [F,G,H,I,J,K,L]; closed = [E,D,C,B,A] Open = [G,H,I,J,K,L,M]; (vì Lđã có trong open); closed = [F,E,D,C,B,A] … 16
TÌM KIẾM TRONG KHÔNG GIAN TRẠNG THÁI (cont.) Function depth_first_search; Var Open: Stack of node; Closed: Set of node; Begin Open := [Start]; Closed := [ ]; while not Empty(Open) dobegin X:= Top(Open); Pop(Open); if then return( success ) else begin For mỗi toán tử O có thể áp dụng lên Xdo If not member(O(X), Open) and not member(O(X), Closed) then Push(O(X), Open) Insert(X, Closed); end; end; return( fail ); End; 17
TÌM KIẾM TRONG KHÔNG GIAN TRẠNG THÁI (cont.) Tìm kiếm sâu – Depth First Search Open = [A]; closed = [] Open = [B,C,D]; closed = [A] Open = [E,F,C,D];closed = [B,A] Open = [K,L,F,C,D]; closed = [E,B,A] Open = [S,L,F,C,D]; closed = [K,E,B,A] Open = [L,F,C,D]; closed = [S,K,E,B,A] Open = [T,F,C,D]; closed = [L,S,K,E,B,A] Open = [F,C,D]; closed = [T,L,S,K,E,B,A] … 18
TÌM KIẾM TRONG KHÔNG GIAN TRẠNG THÁI (cont.) • Tìm kiếm sâu dần (depth first search with iterative deepening) – Định độ sâu tìm kiếm: h – Tìm kiếm sâu đến độ sâu h – Nếu không tìm thấy trạng thái đích nào, tăng h: h = h+Δh – Tiếp tục tìm kiếm đến độ sâu h mới – … 19
TÌM KIẾM TRONG KHÔNG GIAN TRẠNG THÁI (cont.) • Ưu nhược điểm của tìm kiếm sâu: – Đòi hỏi ít bộ nhớ – Có thể không tìm thấy lời giải, dù bài toán có lời giải – Nếu tìm thấy một lời giải, tìm kiếm sâu dừng • Ưu nhược điểm của tìm kiếm rộng: – Nếu bài toán có lời giải, tìm kiếm sâu luôn tìm thấy một, hơn nữa lời giải tìm thấy của tìm kiếm rộng là một lời giải tối ưu theo nghĩa: đường đi lời giải là ngắn nhất – Đòi hỏi nhiều bộ nhớ 20

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 ©2025 TaiLieu.VN. All rights reserved.