5.6. Tìm kiếm trên đồ thị và/hoặc Thông thường, sử dụng tìm kiếm theo chiều sâu để tìm lời giải cho bài toán. Tìm đến đỉnh u, đỉnh này có thể giải được hay không tùy thuộc nó thuộc lớp bài toán nào. Hàm Solvable sau sẽ trả về TRUE nếu giải được, nếu không là FALSE. Function Solvable[u]; Begin If u là đỉnh kết thúc then {Solvable[u] ← true; stop } If u không là đỉnh kết thúc và không có đỉnh kề then {Solvable[u] ← false; stop } For mỗi toán tử R áp dụng được tại u do { Ok ← true; For mỗi v kề u theo R do If Solvable[v] = false then {Ok ← false; exit } If Ok then Solvable[u] ← true; Operator[u] ← R; stop} Solvable[u] ← false; End;5.6. Tìm kiếm trên đồ thị và/hoặc[tiếp]
Bạn đang xem trước 20 trang tài liệu Giáo trình Nhập môn Trí tuệ nhân tạo - Chương 3: Không gian trạng thái và Các phương pháp tìm kiếm mù - Ngô Hữu Phước, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Chương 3 Không gian trạng thái và Các phương pháp tìm kiếm mù Biên soạn: TS Ngô Hữu Phúc Bộ môn Khoa học máy tính ĐT: 098 56 96 580 eMail: Chương 3: Không gian trạng thái và Tìm kiếm mù Trí tuệ nhân tạo 1 Thông tin chung Thông tin về nhóm môn học: Thời gian, địa điểm làm việc: Bộ môn Khoa học máy tính Tầng 2, nhà A1. Địa chỉ liên hệ: Bộ môn Khoa học máy tính, khoa Công nghệ thông tin. Điện thoại, email: 069-515-329, . TTNT - Học viện Kỹ thuật Quân sự2 TT Họ tên giáo viên Học hàm Học vị Đơn vị công tác [Bộ môn] 1 Ngô Hữu Phúc GVC TS BM Khoa học máy tính 2 Trần Nguyên Ngọc GVC TS BM Khoa học máy tính 3 Hà Chí Trung GVC TS BM Khoa học máy tính 4 Trần Cao Trưởng GV ThS BM Khoa học máy tính Cấu trúc môn học Chương 1: Giới thiệu chung. Chương 2: Logic hình thức. Chương 3: Các phương pháp tìm kiếm mù. Chương 4: Các phương pháp tìm kiếm có sử dụng thông tin. Chương 5: Các chiến lược tìm kiếm có đối thủ. Chương 6: Các bài toán thỏa rằng buộc. Chương 7: Nhập môn học máy. TTNT - Học viện Kỹ thuật Quân sự3 Bài 3: Tìm kiếm mù TTNT - Học viện Kỹ thuật Quân sự Chương 3, mục: 3.1 – 3.6 Tiết: 1-3; Tuần thứ: 4. Mục đích, yêu cầu: 1. Nắm được phương pháp giải quyết vấn đề. 2. Nắm được các khái niệm về không gian trạng thái. 3. Nắm được các phương pháp tìm kiếm yếu; qua đó nắm được ưu, nhược điểm của các phương pháp trên. Hình thức tổ chức dạy học: Lý thuyết. Thời gian: 3 tiết. Địa điểm: Giảng đường do Phòng Đào tạo phân công Nội dung chính: [Slides] 4 Nội dung bài học Chương 3: Không gian trạng thái và Tìm kiếm mù 5 1. Khái niệm về “Giải quyết một số vấn đề”. 2. Không gian trạng thái. 3. Phân loại vấn đề. 4. Các chiến lược tìm kiếm trên không gian trạng thái: Tìm kiếm hướng từ dữ liệu [data – driven] Tìm kiếm hướng từ mục tiêu [goal – driven]. 5. Tìm kiếm trên không gian trạng thái: Tìm kiếm rộng [breath – first search]. Tìm kiếm sâu [depth – first search]. Tìm kiếm sâu bằng cách đào sâu nhiều lần [depth – first search with iterative deepening]. 6. Đồ thị and/or. 1. Khái niệm về “Giải quyết một số vấn đề” Chương 3: Không gian trạng thái và Tìm kiếm mù 6 Giải quyết vấn đề là gì? Để giải quyết vấn đề: 1. Phát biểu chính xác bài toán Hiện trạng ban đầu, Kết quả mong muốn,.. 2. Phân tích bài toán. 3. Thu thập và biểu diễn dữ liệu, tri thức cần thiết để giải bài toán. 4. Lựa chọn kỹ thuật giải quyết thích hợp. 2. Không gian trạng thái - Mở đầu Chương 3: Không gian trạng thái và Tìm kiếm mù 7 Khi biểu diễn một vấn đề như là một đồ thị không gian trạng thái, chúng ta có thể sử dụng lý thuyết đồ thị để phân tích cấu trúc và độ phức tạp của các vấn đề cũng như các thủ tục tìm kiếm. 5 6 Riverbank1 Riverbank 2 Island1 Island 2 1 2 3 4 7 Hệ thống cầu thành phố Konigsberg và biểu diễn đồ thị tương ứng [Leonhard Euler ] i1 i2 rb1 rb2 b2 b3 b1 b6 b5 b7 b4 2. Không gian trạng thái Chương 3: Không gian trạng thái và Tìm kiếm mù 8 Khái niệm về Không gian trạng thái Một KGTT [state space] là 1 bộ [N, A, S, GD] trong đó: N [node] là các nút hay các trạng thái của đồ thị. A [arc] là tập các cung [hay các liên kết] giữa các nút. S [start] là một tập chứa các trạng thái ban đầu của bài toán.[S N S ] GD [Goal Description] chứa các trạng thái đích của bài toán [S N S ]. Các trạng thái trong GD được mô tả theo một trong hai đặc tính: Đặc tính có thể đo lường được các trạng thái gặp trong quá trình tìm kiếm. VD: Tic-tac- toe, 8-puzzle, Đặc tính của đường đi được hình thành trong quá trình tìm kiếm. VD: TSP Đường đi của lời giải [solution path] là một con đường đi qua đồ thị này từ một nút thuộc S đến một nút thuộc GD. 2. Không gian trạng thái Chương 3: Không gian trạng thái và Tìm kiếm mù 9 Đồ thị có hướng không lặp lại [directed acyclic graph - DAG] Một phần KGTT triển khai trong Tic-tac-toe 2. Không gian trạng thái Chương 3: Không gian trạng thái và Tìm kiếm mù 10 Trò đố 8 ô hay 15 ô Trạng thái ban đầu Trạng thái đích Trò đố 15 ô Trò đố 8 ô Cần biểu diễn KGTT cho bài toán này như thế nào? 1 2 3 4 12 13 14 5 11 15 6 10 9 8 7 1 2 3 8 4 7 6 5 11 14 4 7 10 6 5 1 2 13 15 9 12 8 3 2 8 3 5 7 6 2 1 2. Không gian trạng thái Chương 3: Không gian trạng thái và Tìm kiếm mù 11 Có khả năng xảy ra vòng lặp không? Không gian trạng thái của bài toán 8 ô số sinh ra bằng phép “di chuyển ô trống” Cần biểu diễn KGTT cho bài toán này như thế nào? 2. Không gian trạng thái Chương 3: Không gian trạng thái và Tìm kiếm mù 12 Biểu diễn không gian trạng thái bài toán người đưa thư 2. Không gian trạng thái Chương 3: Không gian trạng thái và Tìm kiếm mù 13 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. 2. Không gian trạng thái Chương 3: Không gian trạng thái và Tìm kiếm mù 14 Các yếu tố xác định không gian trạng thái 1. Trạng thái. 2. Hành động. 3. Kiểm tra trạng thái thoả đích. 4. Chi phí cho mỗi bước chuyển trạng thái. 3. Phân loại vấn đề Chương 3: Không gian trạng thái và Tìm kiếm mù 15 Các đặc trưng của vấn đề 1. Tính khả tách. 2. Có thể huỷ bỏ hay lần ngược bước giải? 3. Không gian bài toán có đoán định được trước? [sau mỗi bước giải]. 4. Cần lời giải tốt hay tối ưu? 5. Lời giải là trạng thái hay dãy chuyển trạng thái? 6. Vai trò của tri thức? 7. Quá trình giải có cần tương tác người máy? 3. Phân loại vấn đề Chương 3: Không gian trạng thái và Tìm kiếm mù 16 Đơn định/nắm toán bộ không gian trạng thái Đơn định/nắm được bộ phận trong không gian trạng thái Không đơn định/nắm được một bộ phận của không gian trạng thái Không đơn định/không nắm được bộ phận của không gian trạng thái 4. Các chiến lược cho TK-KGTT Chương 3: Không gian trạng thái và Tìm kiếm mù 17 1. TK hướng từ dữ liệu [Data-driven Search] Suy diễn tiến [forward chaining] 2. TK hướng từ mục tiêu [Goal-driven Search] Suy diễn lùi [backward chaining] 1. TK hướng từ dữ liệu [Data-driven Search] 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. 4. Các chiến lược cho TK-KGTT Chương 3: Không gian trạng thái và Tìm kiếm mù 18 4. Các chiến lược cho TK-KGTT Chương 3: Không gian trạng thái và Tìm kiếm mù 19 2. TK hướng từ mục tiêu [Goal-driven Search] 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. 5. Chiến lược tìm kiếm trên đồ thị KGTT Chương 3: Không gian trạng thái và Tìm kiếm mù 20 Phương pháp đánh giá chiến lược tìm kiếm trên đồ thị KGTT: Chiến lược tìm kiếm là chiến lược lựa chọn thứ tự xét các nodes tạo ra. Các tiêu chuẩn để đáng giá chiến lược : đủ : Liệu có tìm được lời giải [nếu có]? độ phức tạp thời gian: số lượng node phải xét. độ phức tạp lưu trữ: Tổng dung lượng bộ nhớ phải lưu trữ [các nodes trong quá trình tìm kiếm. tối ưu: Có luôn cho lời giải tối ưu. Độ phực tạp thời gian và lưu trữ của bài toán có thể được đo bằng: b: Độ phân nhánh của cây d: Độ sâu của lời giải ngắn nhất m: Độ sâu tối đa của không gian trạng thái [có thể vô hạn]. 5. Chiến lược tìm kiếm trên đồ thị KGTT Chương 3: Không gian trạng thái và Tìm kiếm mù 21 Các chiến lược tìm kiếm mù [weak/uninformed/blind search] Những chiến thuật tìm kiếm chỉ sử dụng thông tin từ định nghĩa của bài toán: 1. Tìm kiếm theo chiều rộng 2. Tìm kiếm đều giá [uniform-cost search]. 3. Tìm kiếm theo chiều sâu. 4. Tìm kiếm theo chiều sâu có hạn 5. Tìm kiếm sâu dần. 5.1. Tìm kiếm theo chiều rộng Chương 3: Không gian trạng thái và Tìm kiếm mù 22 Tìm kiếm theo từng tầng. Phát triển các node gần nút nhất. Cài đặt: L [danh sách các node đã được sinh ra và chờ được duyệt] được cài đặt dưới dạng danh sách FIFO, i.e., Các node con được sinh ra [bởi EXPAND] sẽ được đặt ở dưới cùng của L. 5.1. Tìm kiếm theo chiều rộng Chương 3: Không gian trạng thái và Tìm kiếm mù 23 Tìm kiếm theo từng tầng. Phát triển các node gần nút nhất. Cài đặt: L [danh sách các node đã được sinh ra và chờ được duyệt] được cài đặt dưới dạng danh sách FIFO, i.e., Các node con được sinh ra [bởi EXPAND] sẽ được đặt ở dưới cùng của L. 5.1. Tìm kiếm theo chiều rộng Chương 3: Không gian trạng thái và Tìm kiếm mù 24 Tìm kiếm theo từng tầng. Phát triển các node gần nút nhất. Cài đặt: L [danh sách các node đã được sinh ra và chờ được duyệt] được cài đặt dưới dạng danh sách FIFO, i.e., Các node con được sinh ra [bởi EXPAND] sẽ được đặt ở dưới cùng của L. Tìm kiếm theo từng tầng. Phát triển các node gần nút nhất. Cài đặt: L [danh sách các node đã được sinh ra và chờ được duyệt] được cài đặt dưới dạng danh sách FIFO, i.e., Các node con được sinh ra [bởi EXPAND] sẽ được đặt ở dưới cùng của L. 5.1. Tìm kiếm theo chiều rộng Chương 3: Không gian trạng thái và Tìm kiếm mù 25 5.1. Tìm kiếm theo chiều rộng Chương 3: Không gian trạng thái và Tìm kiếm mù 26 Cài đặt thuật toán tìm kiếm theo chiều rộng Thuật toán tìm kiếm theo bề rộng được mô tả bởi thủ tục sau: procedure Breadth_First_Search; begin 1. Khởi tạo danh sách L chỉ chứa trạng thái ban đầu; 2. loop do 2.1 if L rỗng then {thông báo tìm kiếm thất bại; stop}; 2.2 Loại trạng thái u ở đầu danh sách L; 2.3 if u là trạng thái kết thúc then {thông báo tìm kiếm thành công; stop}; 2.4 for mỗi trạng thái v kề u do { Đặt v vào cuối danh sách L; father[v] ← u} end; Trong thuật toán, sử dụng hàm father[v] để lưu lại cha của mỗi đỉnh trên đường đi, father[v]=u nếu u là cha của đỉnh v. 5.1. Tìm kiếm theo chiều rộng Chương 3: Không gian trạng thái và Tìm kiếm mù 27 Nhận xét về thuật toán tìm kiếm theo chiều rộng. Trong thuật toán tìm kiếm theo chiều rộng, trạng thái nào được sinh ra trước sẽ được phát triển trước, do đó danh sách L được sử dụng là hàng đợi. Trong bước 2.3, ta cần kiểm tra xem u có là trạng thái kết thúc không. Nói chung, các trạng thái kết thúc được xác đinh bởi điều kiện nào đó. Nếu bài toán có nghiệm [tồn tại đường đi từ trạng thái đầu tới trạng thái kết thúc], thì thuật toán sẽ tìm được nghiệm. 5.1. Tìm kiếm theo chiều rộng Chương 3: Không gian trạng thái và Tìm kiếm mù 28 Đánh giá tìm kiếm BFS Tính đủ? có [nếu b là hữu hạn]. Thời gian? 1+b+b2+b3+ +bd + b[bd-1] = O[bd+1]. Không gian trạng thái? O[bd+1] [lưu mọi node của cây]. Tính tối ưu? có [giải thiết giá của mỗi bước chuyển là 1] Nhận xét chung: Không gian lưu trữ hết sức tốn kém là vấn đề lớn nhất đối với phương pháp tìm kiếm theo chiều rộng! 5.2. Tìm kiếm đều giá [uniform-cost search] Chương 3: Không gian trạng thái và Tìm kiếm mù 29 Ý tưởng: Xét node có giá tìm kiếm nhỏ nhất trước. Cài đặt: L = Hàng đợi có ưu tiên [bằng nghịch dấu giá thành] Nhận xét chung: Tương đương với BFS nếu các node có giá như nhau. Đánh giá phương pháp: Tính đủ? Có nếu cost ≥ ε Thời gian? Số lượng nodes với g ≤ giá của lời giải tối ưu, O[bceiling[C*/ ε]] trong đó C* là giá của lời giải tối ưu. Không gian trạng thái? Số lượng nodes với g ≤ giá của lời giải tối ưu, O[bceiling[C*/ ε]]. Tính tối ưu? Có – nodes được EXPAND theo thứ tự tăng dần của g[n]. 5.3. Tìm kiếm theo chiều sâu Chương 3: Không gian trạng thái và Tìm kiếm mù 30 Phát triển các node chưa xét ở sâu nhất. Cài đặt: L = danh sách kiểu LIFO, i.e., Đẩy các nodes con sinh bởi quá trình phát triển vào đầu L. 5.3. Tìm kiếm theo chiều sâu Chương 3: Không gian trạng thái và Tìm kiếm mù 31 Phát triển các node chưa xét ở sâu nhất. Cài đặt: L = danh sách kiểu LIFO, i.e., Đẩy các nodes con sinh bởi quá trình phát triển vào đầu L. 5.3. Tìm kiếm theo chiều sâu Chương 3: Không gian trạng thái và Tìm kiếm mù 32 Phát triển các node chưa xét ở sâu nhất. Cài đặt: L = danh sách kiểu LIFO, i.e., Đẩy các nodes con sinh bởi quá trình phát triển vào đầu L. 5.3. Tìm kiếm theo chiều sâu Chương 3: Không gian trạng thái và Tìm kiếm mù 33 Phát triển các node chưa xét ở sâu nhất. Cài đặt: L = danh sách kiểu LIFO, i.e., Đẩy các nodes con sinh bởi quá trình phát triển vào đầu L. 5.3. Tìm kiếm theo chiều sâu Chương 3: Không gian trạng thái và Tìm kiếm mù 34 Phát triển các node chưa xét ở sâu nhất. Cài đặt: L = danh sách kiểu LIFO, i.e., Đẩy các nodes con sinh bởi quá trình phát triển vào đầu L. 5.3. Tìm kiếm theo chiều sâu Chương 3: Không gian trạng thái và Tìm kiếm mù 35 Phát triển các node chưa xét ở sâu nhất. Cài đặt: L = danh sách kiểu LIFO, i.e., Đẩy các nodes con sinh bởi quá trình phát triển vào đầu L. 5.3. Tìm kiếm theo chiều sâu Chương 3: Không gian trạng thái và Tìm kiếm mù 36 Phát triển các node chưa xét ở sâu nhất. Cài đặt: L = danh sách kiểu LIFO, i.e., Đẩy các nodes con sinh bởi quá trình phát triển vào đầu L. 5.3. Tìm kiếm theo chiều sâu Chương 3: Không gian trạng thái và Tìm kiếm mù 37 Phát triển các node chưa xét ở sâu nhất. Cài đặt: L = danh sách kiểu LIFO, i.e., Đẩy các nodes con sinh bởi quá trình phát triển vào đầu L. 5.3. Tìm kiếm theo chiều sâu Chương 3: Không gian trạng thái và Tìm kiếm mù 38 Phát triển các node chưa xét ở sâu nhất. Cài đặt: L = danh sách kiểu LIFO, i.e., Đẩy các nodes con sinh bởi quá trình phát triển vào đầu L. 5.3. Tìm kiếm theo chiều sâu Chương 3: Không gian trạng thái và Tìm kiếm mù 39 Phát triển các node chưa xét ở sâu nhất. Cài đặt: L = danh sách kiểu LIFO, i.e., Đẩy các nodes con sinh bởi quá trình phát triển vào đầu L. 5.3. Tìm kiếm theo chiều sâu Chương 3: Không gian trạng thái và Tìm kiếm mù 40 Phát triển các node chưa xét ở sâu nhất. Cài đặt: L = danh sách kiểu LIFO, i.e., Đẩy các nodes con sinh bởi quá trình phát triển vào đầu L. 5.3. Tìm kiếm theo chiều sâu Chương 3: Không gian trạng thái và Tìm kiếm mù 41 Phát triển các node chưa xét ở sâu nhất. Cài đặt: L = danh sách kiểu LIFO, i.e., Đẩy các nodes con sinh bởi quá trình phát triển vào đầu L. 5.3. Tìm kiếm theo chiều sâu Chương 3: Không gian trạng thái và Tìm kiếm mù 42 Cài đặt thuật toán tìm kiếm theo chiều sâu Procedure Depth_First_Search; begin 1. Khởi tạo danh sách L chỉ chứa trạng thái ban đầu u0; 2. loop do 2.1. if L rỗng then {thông báo thất bại; stop}; 2.2. Loại trạng thái u ở đầu danh sách L; 2.3. if u là trạng thái kết thúc then {thông báo thành công; stop}; 2.4. for mỗi trạng thái v kề u do {Đặt v vào đầu danh sách L;}; end; 5.3. Tìm kiếm theo chiều sâu Chương 3: Không gian trạng thái và Tìm kiếm mù 43 Nhận xét thuật toán tìm kiếm theo chiều sâu Đối BFS: luôn tìm ra nghiệm nếu bài toán có nghiệm. Đối với DFS: không phải với bất kỳ bài toán có nghiệm nào thuật toán tìm kiếm theo chiều sâu cũng tìm ra nghiệm. [với bài toán có nghiệm và không gian tìm kiếm hữu hạn mới tìm được nghiệm]. Lý do? Trong trường hợp không gian trạng thái là vô hạn, thì có thể nó không tìm ra nghiệm vì ta luôn đi sâu xuống, nếu ta đi theo nhánh vô hạn mà nghiệm không nằm trên nhánh đó thì thuật toán sẽ không dừng. 5.3. Tìm kiếm theo chiều sâu Chương 3: Không gian trạng thái và Tìm kiếm mù 44 Đánh giá tìm kiếm DFS Tính đủ? Không đủ [không gian vô hạn hoặc loop] Nếu sửa để tránh trùng lặp → đủ trong không gian hữu hạn. Thời gian? O[bm] Rất xấu nếu m lớn hơn nhiều so với d. Nhưng nếu mật độ lời giải trong không gian lớn thì có thể nhanh hơn BFS. Không gian trạng thái? O[bm], i.e., Độ phức tạp tuyến tính Tính tối ưu? Không 5.4. Tìm kiếm với độ sâu giới hạn Chương 3: Không gian trạng thái và Tìm kiếm mù 45 Là thuật toán DFS với độ sâu giới hạn là d, i.e., nodes tại độ sâu d không có node con [hàm successor trả về rỗng]. Cài đặt: 5.4. Tìm kiếm với độ sâu giới hạn Chương 3: Không gian trạng thái và Tìm kiếm mù 46 Procedure Depth_Limited_Search[d]; begin 1. Khởi tạo danh sách L chỉ chứa trạng thái ban đầu u0; depth[u0] ← 0; 2. loop do 2.1. if L rỗng then {thông báo thất bại; stop}; 2.2. Loại trạng thái u ở đầu danh sách L; 2.3. if u là trạng thái kết thúc then {thông báo thành công; stop}; 2.4. if depth[u]