- ĐIỀU KHIỂN VÀ CÀI ĐẶT TÌM KIẾM TRONG KHÔNG GIAN TRẠNG THÁI. - Nội dung chính : Trong chương này, các kỹ thuật sâu hơn cho việc cài đặt các thuật toán tìm kiếm sẽ được trình bày một cách chi tiết. - Trước hết là tìm kiếm đệ quy (recursive search. - một phương pháp thực hiện tìm kiếm sâu kèm theo lần ngược với cách thức tự nhiên và ngắn gọn. - Tìm kiếm đệ quy được tăng cường nhờ sử dụng sự hợp nhất (unification) để tìm kiếm các không gian trạng thái do các biểu thức của phép tính vị từ sinh ra. - Sự kết hợp này cho ta thuật toán tìm kiếm hướng mẫu (pattern – directed search). - ¾ Vận dụng thuật toán tìm kiếm đệ quy kết hợp lần ngược trên không gian trạng thái.. - ¾ Hiểu thuật toán hướng mẫu khi thực hiện việc tìm kiếm trong không gian trạng thái.. - ¾ Vận dụng hệ sinh cho một bài toán.. - ¾ Hiểu các ưu điểm của hệ sinh. - 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ị, Lý thuyết trò chơi,. - I TÌM KIẾM DỰA TRÊN CƠ SỞ ĐỆ QUI. - I.1 Tìm kiếm đệ quy. - Một chuyển đổi trực tiếp của thuật toán tìm kiếm sâu thành dạng đệ quy sẽ minh họa cho sự tương đương của đệ quy và lặp lại đơn giản. - Thuật toán này sử dụng các biến toàn cục closed và open để duy trì danh sách các trạng thái:. - Trạng thái hiện hành. - If trạng thái hiện hành là trạng thái đích then trả lời (thành công) Else. - closed + trạng thái hiện hành;. - For mỗi trạng thái con của trạng thái hiện hành do If chưa có trong closed hay open % xây dựng ngăn xếp then bổ sung con đó vào đầu danh sách open. - Tìm kiếm sâu. - Tìm kiếm sâu như vừa được trình bày sẽ không sử dụng hết sức mạnh của phép đệ quy. - Nó vẫn còn khả năng đơn giản hóa thủ tục bằng cách sử dụng chính phép đệ quy (thay gì một danh sách open) để sắp xếp các trạng thái trong không gian trạng thái. - Trong phiên bản này của thuật toán, một danh sách closed toàn cục sẽ được dùng để phát hiện các trạng thái lặp lại, còn danh sách open thì tiềm ẩn trong các mẩu tin hoạt động của môi trường đệ quy.. - Function Depthsearch (trạng thái hiện hành. - If trạng thái hiện hành là trạng thái đích then trả lời (thành công);. - For mỗi trạng thái hiện hành có con chưa được kiểm tra do. - tìm kiếm đã đến cùng. - Thay vì phát sinh tất cả các con của một trạng thái và đưa chúng vào danh sách open, thuật toán này phát sinh mỗi lần một con và tìm kiếm theo phép đệ quy các nút cháu của từng con đó trước khi phát sinh các anh em của nó. - phát sinh trạng thái. - Trong tìm kiếm theo đệ quy đối với một trạng thái con, nếu có một con nào đó của trạng thái này là đích, thuật toán đệ quy sẽ trả lời thành công và bỏ qua tất cả các trạng thái anh em. - Ngược lại, các trạng thái anh em kế tiếp được phát sinh. - Cứ như vậy thuật toán sẽ tìm kiếm toàn bộ đồ thị lần lượt theo từng độ sâu một.. - Quá trình lần ngược sẽ tác động khi tất cả các con cháu của một trạng thái không phải là đích, làm cho bước đệ quy đó thất bại. - Việc thực hiện đệ quy cho phép lập trình viên thu hẹp tầm nhìn của họ vào một trạng thái duy nhất cùng với các con của nó thay vì phải duy trì một danh sách open gồm nhiều trạng thái.. - Tìm kiếm trong không gian trạng thái là một quá trình đệ quy. - Để tìm đường đi từ trạng thái hiện hành đến đích, bạn chuyển đến một trạng thái con và thực hiện phép đệ quy. - Nếu trạng thái con đó không dẫn đến đích, bạn thử lần lượt các trạng thái anh em của nó. - I.2 Tìm kiếm hướng mẫu (Pattern – directed search). - Trong phần này chúng ta sẽ áp dụng tìm kiếm đệ quy vào không gian các suy diễn logic, kết quả sẽ là một thủ tục tìm kiếm tổng quát dùng cho phép tính vị từ.. - Thuật toán sẽ đề nghị một tìm kiếm hướng mục tiêu với câu hỏi ban đầu tạo nên đích và các modus ponens xác định các chuyển tiếp giữa các trạng thái. - Nếu đích phụ phù hợp với một sự kiện trong cơ sở tri thức, cuộc tìm kiếm kết thúc. - Phiên bản hoàn chỉnh của thuật toán tìm kiếm hướng mẫu có thể trả lời một tập các đồng nhất thỏa mãn từng đích phụ là:. - II HỆ THỐNG LUẬT SINH (HỆ SINH – PRODUCTION SYSTEM). - II.1 Định nghĩa hệ sinh. - Hệ sinh là một mô hình tính toán quan trọng trong trí tuệ nhân tạo về cả hai mặt: thực hiện các thuật toán tìm kiếm và mô hình hóa việc giải các bài toán của con người.. - Một hệ sinh được định nghĩa bởi:. - Bộ nhớ làm việc (Working memory): Chứa một mô tả về trạng thái hiện thời của bài toán trong quá trình suy luận. - Là cấu trúc điều khiển của hệ sinh.. - Trạng thái hiện hành của việc giải bài toán được duy trì dưới dạng một tập các mẫu trong bộ nhớ làm việc. - Đây là một khâu quan trọng để các hệ sinh có thể đưa khả năng điều khiển heuristic vào một thuật toán tìm kiếm.. - Hình 5.1 – Cấu trúc hệ sinh. - Không gian tìm kiếm do trò đố 8 ô sinh ra vừa đủ phức tạp để khảo sát và cũng vừa đủ nhỏ để có thể theo dõi, cho nên ta thường hay sử dụng nó để minh họa cho các chiến lược tìm kiếm khác nhau như tìm kiếm sâu, tìm kiếm rộng, cũng như các chiến lược tìm kiếm heuristic. - Trong trường hợp trạng thái bắt đầu và trạng thái đích của trò chơi được xác định, chúng ta có khả năng áp dụng một hệ sinh cho không gian tìm kiếm của bài toán.. - Trạng thái bắt đầu:. - Trạng thái kết thúc:. - Điều kiện Hành động Trạng thái kết thúc trong bộ nhớ làm việc → Dừng. - Ô trống không ở cạnh đỉnh → Chuyển ô trống lên Ô trống không ở cạnh phải → Chuyển ô trống sang phải Ô trống không ở cạnh đái → Chuyển ô trống xuống Bộ nhớ làm việc chứa trạnh thái bắt đầu và trạng thái kết thúc Cơ chế kiểm soát. - Dừng khi tìm thấy trạng thái kết thúc. - Khởi đầu, bộ nhớ làm việc chứa trạng thái bàn cờ hiện tại và trạng thái đích. - Vòng lặp điều khiển sẽ áp dụng các luật cho đến khi trạng thái hiện tại giống trạng thái đích rồi dừng lại. - Vì quá trình tìm kiếm có thể dẫn đến những kết thúc chết nên chu trình điều khiển cho phép lần ngược.. - II.3 Điều khiển tìm kiếm trong các hệ sinh. - Mô hình hệ sinh cho chúng ta có nhiều cơ hội để bổ sung điều khiển heuristic cho một thuật toán tìm kiếm. - Những cơ hội đó có thể áp dụng khi chọn chiến lược tìm kiếm hướng dữ liệu hay tìm kiếm hướng mục tiêu, trong cấu trúc các luật hoặc khi chọn chiến lược giải quyết tranh chấp.. - II.3.1 Điều khiển chọn chiến lược tìm kiếm hướng dữ liệu (suy diễn tiến) hay tìm kiếm hướng mục tiêu (suy diễn lùi). - Tìm kiếm hướng dữ liệu bắt đầu với một mô tả bài toán (như một tập các tiền đề logic, các triệu chứng của người bệnh, hay một khối dữ liệu cần suy diễn. - Quá trình này được thực hiện bằng cách áp dụng các luật suy diễn, các nước đi hợp lệ trong một trò chơi hoặc các thao tác sinh ra trạng thái khác vào mô tả hiện hành của bài toán, đồng thời đưa thêm các kết quả vào mô tả bài toán. - Hình 5.5 – Tìm kiếm hướng dữ liệu trong một hệ sinh. - Trạng thái hiện tại của bài toán được đưa vào bộ nhớ làm việc. - Chu trình nhận dạng – hành động sẽ đối sánh trạng thái hiện tại với tập luật sinh (theo thứ tự). - Khi các dữ liệu này phù hợp với phần điều kiện của một trong các luật sinh đó, phần hành động của luật sinh sẽ bổ sung thêm (bằng cách thay đổi bộ nhớ làm việc) một thông tin mới vào trạng thái hiện tại của bài toán.. - Hình trên trình bày quá trình tìm kiếm hướng dữ liệu đơn giản dựa vào một tập các luật sinh được biểu diễn dưới dạng phép kéo theo của phép tính mệnh đề. - Hình này cũng giới thiệu trình tự các luật kích hoạt và trạng thái bộ nhớ làm việc trong quá trình thực hiện cùng với đồ thị của không gian tìm kiếm.. - Ta cũng có thể áp dụng tìm kiếm hướng mục tiêu trong các hệ sinh. - Để thực hiện điều này, mục tiêu được đưa vào bộ nhớ làm việc và được đối sánh với phần ACTION của các luật sinh (bằng phép hợp nhất chẳng hạn) và phần CODITION cuả luật sẽ được bổ sung vào bộ nhớ làm việc và trở thành các mục tiêu mới của quá trình tìm kiếm. - Quá trình tìm kiếm sẽ dừng lại khi các CODITION của tất cả các luật sinh được kích hoạt đều là đúng. - Tìm kiếm hướng mục tiêu sẽ kích hoạt loạt luật sinh khác và tiến hành quá trình tìm kiếm trên không gian khác so với kiểu hướng dữ liệu.. - Tìm kiếm hướng mục tiêu trong một hệ sinh. - II.3.2 Điều khiển tìm kiếm thông qua cấu trúc luật. - Cấu trúc của các luật trong một hệ sinh bao gồm sự phân biệt giữa phần điều kiện (CONDITION) với phần hành động (ACTION) và thứ tự mà các điều kiện được thử, sẽ quyết định cách tìm kiếm trong không gian.. - Hệ sinh thử các luật theo một thứ tự xác định nên người lập trình có thể điều khiển quá trình tìm kiếm thông qua cấu trúc và thứ tự của các luật trong tập luật sinh. - Mặc dù tương đương về mặt logic nhưng hai cách thực hiện không như nhau trong một quá trình tìm kiếm.. - Chiến lược này giúp tập trung việc tìm kiếm vào một dòng suy luận duy nhất.. - Theo các minh họa trên, hệ sinh cho chúng ta một quy tắc chung để thực hiện tìm kiếm. - Đưa một sắp xếp tự nhiên vào tìm kiếm trong không gian trạng thái: Các phần tử của một hệ sinh sẽ được sắp xếp một cách tự nhiên vào cấu trúc tìm kiếm không gian trạng thái. - Các trạng thái kế tiếp của bộ nhớ làm việc sẽ tạo nên các nút của đồ thị.. - Các luật sinh là các bước chuyển đổi có thể xảy ra giữa các trạng thái cùng với các chiến lược giải quyết tranh chấp sẽ cài đặt việc chọn một nhánh trong không gian trạng thái đó.. - Trong một bài toán, các mô tả tạo nên trạng thái hiện hành sẽ xác định tập luật tranh chấp và do đó cũng sẽ xác định con đường tìm kiếm và lời giải riêng.. - Có cơ hội cho điều khiển heuristic của quá trình tìm kiếm.. - Vì mỗi luật ứng với một đoạn của quá trình giải toán nên nội dung luật sẽ giải thích đầy đủ ý nghĩa về trạng thái và hành động hiện hành của hệ thống đó.. - TỔNG KẾT CHƯƠNG V: Chương V đã trình bày một số các thuật toán cũng như các mô hình, kiến trúc phổ biến dùng điều khiển và cài đặt quá trình tìm kiếm trong không gian trạng thái như: tìm kiếm đệ quy, mô hình hệ sinh, kiến trúc bảng đen. - b) Nếu biết lượng chất béo có trong thịt bò (contains_fat) là nhỏ hơn 20%, biểu diễn các bước suy diễn theo hệ sinh – tìm kiếm hướng dữ liệu để chứng tỏ “thịt bò là thực phẩm an toàn”.. - ĐIỀU KHIỂN VÀ CÀI ĐẶT TÌM KIẾM TRONG KHÔNG GIAN TRẠNG THÁI...79. - TÌM KIẾM DỰA TRÊN CƠ SỞ ĐỆ QUI...80. - Tìm kiếm đệ quy ...80. - Tìm kiếm hướng mẫu (Pattern – directed search)...81. - HỆ THỐNG LUẬT SINH (HỆ SINH – PRODUCTION SYSTEM) ...83. - Định nghĩa hệ sinh ...83. - Một số ví dụ về hệ sinh ...85. - Điều khiển tìm kiếm trong các hệ sinh...87
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt