Bài giảng Trí tuệ nhân tạo (Artificial Intelligence): Chương 2 – GV. Nguyễn Văn Hòa

Bài giảng Trí tuệ nhân tạo (Artificial Intelligence) - Chương 2 cung cấp kiến thức về chiến lược tìm kiếm mù. Những nội dung chính trong chương gồm có: Bài toán, biểu diễn bài toán, tìm kiếm, các chiến lược điều khiển, các đặc trưng của bài toán, vấn đề trong thiết kế CT tìm kiếm. Mời các bạn tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Trí tuệ nhân tạo (Artificial Intelligence): Chương 2 – GV. Nguyễn Văn HòaChương 2: Chiến lược tìm kiếm mù Giảng viên: Nguyễn Văn Hòa Khoa CNTT - ĐH An Giang 1Nội dung◼ Bài toán tìm kiếm ❑ Biểu diễn bài toán ❑ Tìm kiếm◼ Các chiến lược điều khiển tìm kiếm◼ Các đặc trưng của bài toán◼ Vấn đề trong thiết kế chương trình tìm kiếm Ref: http://www.cs.cmu.edu/~awm/tutorials 2Mô hình ứng dụng của TTNT TTNT = Presentation & Search Tri Thức Tìm kiếm Knowledge Search Engineering Suy luận Heurictic 3Bài toán tìm kiếmLàm sao có thể đi từ S đến G? Và số lần chuyển đổi cóthể ít nhất? 4Bài toán tìm kiếm (tt)◼ Giải bài toán bằng cách tìm kiếm, gồm: ❑ Cấu trúc bài toán: VD. tìm đường đi trên đồ thị ❑ Biểu diễn bài toán bằng không gian trạng thái ❑ Giải bài toán = Tìm ra một trạng thái/con đường trong không gian trạng thái (trạng thái đầu  trạng thái đích) 5Bài toán tìm kiếm (tt)◼ Không gian trạng thái của bài toán tìm kiếm có 5 thành phần: Q, S, G, sucss, cost ❑ Q: tập hữu hạn các trạng thái (nút của Graph) ❑ SQ: tập hữu hạn khác rỗng các trạng thái bắt đầu ❑ G Q : tập hữu hạn khác rỗng các trạng thái đích ❑ succs: Q→P(Q) hàm nhận một trạng thái làm đầu vào và trả về kết quả các trạng thái. ❑ cost: Q, Q→ Số dương là hàm nhận 2 tham số đầu vào là TT s và s’ ◼ Trả về chi phí từ s đến s’. ◼ Hàm chỉ được định nghĩa khi s’ là con của s. 6Bài toán tìm kiếm (tt)◼ Q={START, a , b , c , d , e , f , h , p , q , r, GOAL}◼ S={START}◼ G={GOAL}◼ succs(b)={a}, succs(e)={h,r},…◼ cost(s,s’)=1, cho tất cả chuyển trạng thái 7Các loại bài toán tìm kiếm 8Các loại bài toán tìm kiếm (tt)◼ Fully observable, deterministic ❑ single-belief-state problem◼ Non-observable ❑ sensorless (conformant) problem◼ Partially observable/non-deterministic ❑ contingency problem ❑ interleave search and execution◼ Unknown state space ❑ exploration problem ❑ execution first 9 State space vs database search State Space Database◼ Không gian tìm kiếm thường là ◼ Không gian tìm kiếm là một đồ thị (graph) một danh sách hay cây◼ Mục tiêu tìm kiếm là một path ◼ Tìm kiếm một record/nút◼ Phải lưu trữ toàn bộ không gian ◼ Phần tử đã duyệt qua là trong quá trình tìm kiếm không còn dùng tới◼ Không gian tìm kiếm biến động ◼ Không gian tìm kiếm là cố liên tục trong quá trình tìm kiếm định trong quá trình tìm◼ Đặc tính của trạng thái / nút chứa kiếm nhiều thuộc tính bị thay đổi giá trị ◼ Thuộc tính của một trong quá trình tìm kiếm record/nút là cố định 10Bài toán Romania ◼ State space: ❑ Cities ◼ Successor function: ❑ Go to adj city with cost = dist ◼ Start state: ❑ Arad ◼ Goal test: ❑ Is state == Bucharest? ◼ Solution?Bài toán: Tic tac toeĐồ thị có hướng không lặplại (directed acyclic graph) 12Bài toán: 8 puzzle Có khả năng xảy ra vòng lặp không? 13Chiến lược tìm kiếm?◼ Khi tìm kiếm lời giải, từ một trạng thái nào đó chưa phải là trạng thái đích, ta dựa theo hàm succs sinh ra tập các trạng thái mới (mở rộng)◼ Để được lời giải, ta phải liên tục chọn trạng thái mới, mở rộng, kiểm tra cho đến khi tìm được trạng thái đích hoặc không mở rộng được KGTT◼ Tập các trạng thái được mở rộng sẽ có nhiều phần tử, việc chọn trạng thái nào để tiếp tục mở rộng được gọi là chiến lược tìm kiếm 14Đánh giá một chiến lược?◼ Tính đầy đủ: chiến lược phải đảm bảo tìm được lời giải (nếu có lời giải)?◼ Tính tối ưu: lời giải có tốt hơn so với một số chiến lược khác hay không?◼ Độ phức tạp không gian: cần bao nhiêu đơn vị bộ nhớ để tìm được lời giải?◼ Độ phức tạp thời gian: cần bao nhiêu thời gian để tìm được lời giải? 15Thông tin mỗi nút ?◼ Nội dung trạng thái mà nút hiện hành đang biểu diễn◼ Nút cha đã sinh ra nó◼ succs đã được sử dụng để sinh ra nút hiện hành◼ Độ sâu của nút (tính từ nút gốc)◼ Giá trị đường đi từ nút gốc đến nút hiện hành 16Tìm kiếm mù◼ Trạng thái được chọn để phát triển dựa theo cấu trúc của KGTT mà dùng thông tin hỗ trợ◼ Là chiến lược tìm kiếm mù không hiệu quả◼ Đây là cơ sở để chúng ta cải tiến và thu được những chiến lược hiệu quả hơn◼ Hai giải thuật tìm kiếm mù ❑ Tìm kiếm theo chiều rộng (Breadth-First-Search) ❑ Tìm kiếm theo chiều sâu (Depth First Search) 17 Tìm kiếm theo chiều rộng Strategy: expand a G shallowest node first ...