Thuật ngữ CS cho thuật toán khớp quy tắc trên bộ điều kiện bắt buộc và tùy chọn

Question

Tôi đang cố gắng nghiên cứu tài liệu cho các thuật toán để giải quyết một vấn đề cụ thể, nhưng tôi không nghĩ rằng tôi hoàn toàn biết cụm từ tìm kiếm phù hợp tìm kiếm.

Mục tiêu là có cơ sở dữ liệu quy tắc có thể truy vấn, trong đó mỗi quy tắc được chỉ định là điều kiện tuple — một số bắt buộc, một số tùy chọn. Truy vấn vào hệ thống bao gồm một bộ dữ kiện về thế giới và trả về danh sách tất cả các quy tắc có điều kiện bắt buộc khớp với các sự kiện trong truy vấn. Mỗi quy tắc được tính theo số lượng × của các điều kiện tùy chọn phù hợp và danh sách được sắp xếp theo đó.

Vì vậy, cho một ví dụ, nếu tôi đang sử dụng này để viết một dịch vụ bạn cùng phòng khớp, các quy tắc sẽ là một cái gì đó giống như

alice : { mandatory : { nightowl = no, smoker = no, pets < 2 }, 
      optional : { pets = 0 } } 
bob : { mandatory : { nightowl = yes, pets = 0 }, 
      optional : {smoker = no} } 
charlie : { mandatory : { musician = no }, 
      optional : {nightowl = yes, pets < 2 } } 

và truy vấn sẽ là

(nightowl = no, pets = 1, smoker = no, musician = no) 

trở

(charlie : 1/1 mandatory matched, 1/2 optional matched, 
    alice : 3/3 mandatory matched, 0/1 optional matched) 

Tôi biết đây là vấn đề phải được giải quyết nhiều lần trong khoa học máy tính , nhưng tôi không biết từ khóa nào cần tìm kiếm. Nó không phải là chức năng khoảng cách , bởi vì một số điều kiện là rời rạc đúng/sai riêng biệt trong khi các điều kiện khác là tùy chọn hoặc có điểm số tuyến tính. Nó không phải là đối sánh mẫu hoặc kết hợp mờ, bởi vì những thứ đó dường như chỉ chủ yếu là các chuỗi và biểu đồ. Đây không phải là hệ thống sản xuất hoặc quy tắc giống như Rete algorithm, bởi vì nó không rút ra suy luận IF-THEN từ quy tắc, cũng như không nhớ sự kiện từ một cuộc gọi đến lần tiếp theo.

Điều gì là được gọi là?

Tôi chỉ cần nghiên cứu hoặc mô tả thuật toán, không phải triển khai thực tế. Ứng dụng của chúng ta có những hạn chế về thời gian thực và bộ nhớ nghiêm trọng mà chúng ta sẽ cần phải xây dựng một bản cài đặt của chính mình, nhưng tôi muốn biết những gì khác đã được thực hiện trong không gian trước khi tôi bắt đầu phát minh ra mã. Một giấy ACM mà tôi có thể đuổi theo trích dẫn cũng sẽ rất tuyệt vời.

Answer 1

Thuật ngữ tôi muốn mô tả chính xác nhất loại vấn đề bạn đang nói đến là một sự cố constraint satisfaction.

Cụ thể hơn, bạn đang ở trong lĩnh vực có trọng số sự hài lòng về ràng buộc.

Lập trình hạn chế là thuật ngữ thông thường cho một bộ công cụ và ngôn ngữ được thiết kế đặc biệt để giải quyết các loại vấn đề này.

Answer 2

Phù hợp với điều kiện bắt buộc là range searching, cụ thể là tìm kiếm phạm vi trực giao. Các tài liệu liên quan thuộc về hình học tính toán. Xếp hạng theo điều kiện tùy chọn là hoạt động sắp xếp.