DÙ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Ừ

Mô tả không gian trạng thái của một hệ logic:

Đồ thị không gian trạng thái của logic vị từ bao gồm các nút, mỗi nút biểu diễn cho một trạng thái của quá trình giải bài toán và các luật suy diễn có thể được dùng để hình thành và mô tả các cung giữa các trạng thái này. Theo cách này, các bài toán trong phép tính vị từ, như việc xác định một biểu thức nào đó có phải là hệ quả logic của một tập các khẳng định cho trước hay không, có thể giải quyết bằng phương pháp tìm kiếm.

Thí dụ 3.4: Giả sử p, q, r, … là các mệnh đề, ta có thể giả thuyết có các khẳng định sau :

Từ tập các khẳng định này và các modus ponen của các luật suy diễn, một số các mệnh đề nhất định (p, r và u) có thể được suy diễn ra; còn các mệnh đề khác (như v và q) không thể suy diễn được và thực tế chúng không đi theo một cách logic từ các khẳng định này. Quan hệ giữa các khẳng định ban đầu và các suy diễn được biểu diễn trong đồ thị có hướng như hình 3.12.

Với cách biểu diễn này, việc xác định một mệnh đề cho trước có phải là một hệ quả logic của một tập các mệnh đề hay không sẽ trở thành bài toán tìm đường đi từ một nút xuất phát đến nút đích. Nó cũng được quy về bài toán tìm kiếm trên đồ thị. Chiến lược tìm kiếm được dùng ở đây sẽ là tìm kiếm hướng dữ liệu, vì nó đi từ những gì đã biết (các mệnh đề đúng) đến đích. Theo cách khác, chiến lược hướng mục tiêu cũng có thể được áp dụng vào cùng không gian đó bằng cách xuất phát từ mệnh đề cần chứng minh (đích) và đi ngược theo các cung để tìm sự hỗ trợ đối với đích đó trong các mệnh đề đúng. Ngoài ra, chúng ta còn có thể tìm kiếm trên không gian suy diễn này theo chiều sâu hay chiều rộng.

Hình 3.12 – Đồ thị không gian trạng thái cho thí dụ 3.4

Đồ thị Và / Hoặc (And / Or Graph)

Đồ thị Và / Hoặc là một công cụ quan trọng để mô tả các không gian tìm kiếm trong nhiều bài toán của Trí tuệ nhân tạo, bao gồm cả các bài toán giải quyết bằng cách chứng minh theo định lý logic và các hệ chuyên gia.

Đồ thị Và / Hoặc có sự phân biệt các nút Và (And) với các nút Hoặc (Or):

• Nếu các tiền đề của một mệnh đề được nối với nhau bằng toán tử ∧, chúng được gọi là các nút Và, đồng thời các cung nối với nút này được liên kết với nhau bằng một dấu liên kết cong.
• Nếu các tiền đề của một mệnh đề được nối với nhau bằng toán tử ∨, chúng được xem là các nút Hoặc. Các cung nối từ các nút Hoặc đến nút bố mẹ của chúng sẽ không được liên kết như vậy.

Thí dụ 3.5: Giả sử các mệnh đề sau đây là đúng:

Tập các khẳng định này sẽ sinh ra đồ thị Và / Hoặc như trong hình vẽ sau:

Hình 3.13 – Đồ thị AND/OR cho bài toán

Các câu hỏi có thể được đặt ra là:

• h là đúng?
• h có còn đúng nếu b sai?

Trong ví dụ trên, chiến lược tìm kiếm hướng mục tiêu để xác định h là đúng trước hết phải chứng minh cả a lẫn e đúng. Nút a đúng là tất nhiên, nhưng muốn e đúng thì cả c lẫn a đều phải đúng, hai nút này đã được cho trước là đúng. Khi chương trình giải bài toán đã xác định tất cả các cung này là các mệnh đề đúng, thì các giá trị đúng sẽ được tổng hợp lại ở các nút Và để kiểm chứng giá trị đúng của h.

Ngược lại, chiến lược tìm kiếm hướng dữ liệu để xác định h đúng phải xuất phát từ các sự kiện đã biết (c, a và b) và bắt đầu bằng việc bổ sung các mệnh đề mới vào tập mệnh đề đã biết này phù hợp theo các qui định của đồ thị Và / Hoặc, e hoặc d sẽ là mệnh đề đầu tiên được bổ sung vào tập sự kiện đó. Những bổ sung này sẽ tạo khả năng suy diễn ra các sự kiện mới. Quá trình này cứ tiếp tục cho đến khi đích được chứng minh.

TỔNG KẾT CHƯƠNG III:

Chương III đã giới thiệu các cơ sở lý thuyết trong tìm kiếm không gian trạng thái, sử dụng lý thuyết đồ thị để phân tích cấu trúc và mức độ phức tạp của các chiến lược giải quyết vấn đề bài toán. Các cách thức có thể sử dụng để mô hình hóa việc giải quyết vấn đề dưới dạng một tìm kiếm trên đồ thị trạng thái của bài toán đó cũng đã được nêu ra. Đồng thời cũng so sánh giữa hai cách suy luận hướng dữ liậu và hướng mục tiêu, giữa tìm kiếm sâu và tìm kiếm rộng. Phần cuối chương, đồ thị And/Or cho phép chúng ta áp dụng tìm kiếm không gian trạng thái vào việc thực hiện các suy diễn logic. Tuy nhiên, hầu hết các chiến lược này đều mang tính hình thức, chương tiếp theo sẽ đi sâu hơn vào những “mẹo giải” trong các chiến lược tìm kiếm không hình thức áp dụng cho những không gian bài toán đặc trưng nhằm thu hẹp quá trình tìm kiếm trên các không gian này.

Bài tập chương III

Xét đồ thị trạng thái sau đây, với mỗi chiến lược tìm kiếm bên dưới hãy liệt kê với danh sách thứ tự các nút được duyệt qua.

• Tìm kiếm rộng (BFS).
• Tìm kiếm sâu (DFS).
• Tìm kiếm sâu với độ sâu giới hạn là 3.
• Tìm kiếm sâu đào sâu nhiều lần.

Giả sử P là nút mục tiêu của đồ thị bên dưới, nếu dùng giải thuật tìm kiếm sâu đào sâu nhiều lần để duyệt đồ thị không gian trạng thái này, hãy cho biết danh sách thứ tự các nút mà giải thuật đã duyệt qua.