CÁC CẤU TRÚC VÀ CHIẾN LƯỢC DÙNG CHO VIỆC TÌM KIẾM TRONG KHÔNG GIAN TRẠNG THÁI

Trong chương này, chúng ta giới thiệu về lý thuyết của việc tìm kiếmtrong không gian trạng thái. Để thiết kế và thực hiện thành công các thuật toán tìm kiếm, người lập trình phải có khả năng phân tích và dự đoán hành vi của chúng. Lý thuyết tìm kiếm trong không gian trạng thái (state space search) là công cụ cơ bản để giải quyết vấn đề này.
Nội dung trích xuất từ tài liệu:
CÁC CẤU TRÚC VÀ CHIẾN LƯỢC DÙNG CHO VIỆC TÌM KIẾM TRONG KHÔNG GIAN TRẠNG THÁI Chương 3: Tìm kiếm Trong Không Gian Trạng Thái Chương III CÁC CẤU TRÚC VÀ CHIẾN LƯỢC DÙNG CHO VIỆC TÌM KIẾM TRONG KHÔNG GIAN TRẠNG THÁINội dung chính : Trong chương này, chúng ta giới thiệu về lý thuyết của việc tìm kiếmtrong không gian trạng thái. Để thiết kế và thực hiện thành công các thuật toán tìm kiếm,người lập trình phải có khả năng phân tích và dự đoán hành vi của chúng. Lý thuyết tìmkiếm trong không gian trạng thái (state space search) là công cụ cơ bản để giải quyết vấn đềnày. Nội dung chương III sẽ trình bày định nghĩa về không gian trạng thái, giới thiệu một sốcác ví dụ minh họa việc mô tả vấn đề dùng lý thuyết đồ thị, nêu ra hai hướng tìm kiếm trongkhông gian trạng thái (hướng dữ liệu và hướng mục tiêu) và tập trung phân tích các chiếnlược chủ yếu dùng cho việc tìm kiếm trên không gian trạng thái đồ thị như: tìm kiếm rộng,tìm kiếm sâu, tìm kiếm sâu đào sâu nhiều lần, … Phần cuối chương cũng đề cập đến việcdùng không gian trạng thái để biểu diễn quá trình suy luận bằng phép tính vị từ trên đồ thịAND/OR.Mục tiêu cần đạt : Sau chương này, sinh viên có thể : Vận dụng lý thuyết đồ thị để xây dựng mô hình toán cho một bài toán cụ thể. Vận dụng các chiến lược tìm kiếm Vận dụng đồ thị AND/OR để biểu diễn quá trình suy luận trên không gian trạng thái của một hệ logic.Kiến thức tiên quyết: Lý thuyết đồ thị, Các thuật toán tìm kiếm trên đồ thị, Logic hìnhthức, …Tài liệu tham khảo : [1] George F. Luger, William A. Stubblefield – Albuquerque – Artificial Intelligence – Wesley Publishing Company, Inc – 1997 (Chapter3) [2] Bùi Xuân Toại – Trương Gia Việt (Biên dịch) – Trí tuệ nhân tạo – Các cấu trúc và chiến lược giải quyết vấn đề - NXB Thống kê, 2000 (Phần II) [3] Wikipedia – Bách khoa toàn thư mở - Lý thuyết đồ thị http://en.wikipedia.org/wiki/Graph_theory [4] Lecture note for February 15, 1996-ICS 161: Design and Analysis of Algorithm – BFS và DFS http://www.ics.uci.edu/~eppstein/161/960215.htmlVõ Huỳnh Trâm – Trần Ngân Bình 43Giáo Trình Trí Tuệ Nhân TạoI MỞ ĐẦUBằng cách biểu diễn bài toán dưới dạng đồ thị không gian trạng thái (state space graph),chúng ta có thể dùng lý thuyết đồ thị (graph theory) để phân tích cấu trúc và độ phức tạp củabài toán này lẫn các thủ tục dùng để giải quyết nó.Một đồ thị sẽ bao gồm một số nút (node) và một số cung (arc), hay còn gọi là liên kết (link),nối giữa các cặp nút. Trong mô hình không gian trạng thái của bài toán, các nút của đồ thịđược dùng để biểu diễn các trạng thái rời rạc trong quá trình đó, như các kết quả của nhữngsuy diễn logic hay các cấu hình của một bảng trò chơi chẳng hạn. Còn các cung thì biểu diễnsự chuyển tiếp giữa các trạng thái đó. Những chuyển tiếp này tương ứng với các bước suydiễn logic hoặc các di chuyển hợp luật của một trò chơi.Lý thuyết đồ thị là một công cụ tốt nhất của chúng ta trong việc suy luận về cấu trúc của cácđối tượng và các mối quan hệ. Thật vậy, đây cũng chính là một trong những nguyên nhândẫn đến sự sáng tạo ra nó vào thời kỳ đầu thế kỷ XVIII.Nhà toán học người Áo Leonhard Euler đã phát minh ra lý thuyết đồ thị để giải quyết “bàitoán các cây cầu của Konigsberg”. Thành phố Konigsberg nằm trên cả hai bờ và hai hòn đảocủa một con sông. Người ta nối các đảo và hai bờ sông với nhau bằng bảy chiếc cầu nhưhình 3.1 Bờ sông 1 4 2 3 1 Đảo 2 Đảo 1 6 7 5 Bờ sông 2 Hình 3.1 - Biểu diễn không gian trạng thái hệ thống cầu thành phố KonigsbergBài toán Konigsberg đặt câu hỏi là liệu có thể đi khắp thành phố mà chỉ ngang qua mỗi câycầu một lần hay không? Mặc dù những người dân ở đây không ai tìm được lối đi nào nhưvậy, nhưng họ vẫn nghi ngờ là có thể, đồng thời cũng không ai chứng minh được là không cókhả năng. Nhờ phát minh dạng lý thuyết đồ thị, Euler đã tạo ra cách biểu diễn phương án lựachọn cho bản đồ thành phố như trên hình 3.244 Võ Huỳnh Trâm – Trần Ngân Bình Chương 3: Tìm kiếm Trong Không Gian Trạng Thái bs1 c2 c4 c3 c1 ...