CS 术语，表示强制和可选条件元组上的规则匹配算法
我正在尝试研究解决特定问题的算法的文献，但我认为我不太知道描述我正在寻找的内容的正确搜索词。
目标是拥有一个可查询的规则数据库，其中每个规则都被指定为元组条件 - 有些是强制性的，有些是可选的。对系统的查询由有关世界的事实元组组成，并返回强制条件与查询中的事实相匹配的所有规则的列表。每个规则按照匹配的可选条件的数量×权重进行评分，并由此对列表进行排序。
举个例子，如果我用它来编写室友匹配服务，规则将类似于
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 } }
并且查询将
( nightowl = no, pets = 1, smoker = no, musician = no )
返回
( charlie : 1/1 mandatory matched, 1/2 optional matched,
alice : 3/3 mandatory matched, 0/1 optional matched )
我知道这是一个在计算机科学中必须已经解决过很多次的问题，但我不知道该搜索什么关键词。它不是一个距离函数，因为某些条件是离散的真/假拒绝器，而其他条件是可选的或具有线性分数。它不是模式匹配或模糊匹配，因为这些似乎主要指字符串和图形。它不是像Rete那样的生产系统或规则引擎算法，因为它不会从规则中得出 IF-THEN 推论，也不会记住一次调用到下一次调用的事实。
它叫什么？
我只需要算法的研究或描述，而不是实际的实现。我们的应用程序具有如此严格的实时和内存限制，无论如何我们都需要构建自己的实现，但在开始发明代码之前，我想知道该领域还做了什么。一篇我可以引用的 ACM 论文也很棒。
I'm trying to research literature for algorithms to solve a particular problem, but I don't think I quite know the right search term to describe what I'm looking for.
The goal is to have a queryable rules database, where each rule is specified as tuple conditions — some mandatory, some optional. A query into the system consists of a tuple of facts about the world, and returns a list of all the rules whose mandatory conditions matched the facts in the query. Each rule is scored by the number×weight of optional conditions matched and the list is sorted thereby.
So for an example, if I were using this to write a roommate-matching service, the rules would be something like
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 } }
and the query would be
( nightowl = no, pets = 1, smoker = no, musician = no )
returning
( charlie : 1/1 mandatory matched, 1/2 optional matched,
alice : 3/3 mandatory matched, 0/1 optional matched )
I know this is a problem that must have been solved many times in computer science already, but I don't know what keywords to search for. It's not a distance function, because some conditions are discrete true/false rejectors whereas others are optional or have linear scores. It's not pattern matching or fuzzy matching, because those seem to refer mostly to strings and graphs. It's not a production system or rules engine like the Rete algorithm, because it doesn't draw IF-THEN inferences from rules, nor does it remember facts from one call to the next.
What is it called?
I only need research or descriptions of algorithms, not actual implementations. Our application has such severe realtime and memory constraints that we'll need to build an implementation of our own anyway, but I'd like to know what else has been done in the space before I start inventing code. An ACM paper that I could chase citations from would be great, too.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我想说最准确地描述您正在谈论的问题类型的术语是约束满足问题。
更具体地说，您处于加权约束满足的领域。
约束编程是专门为解决此类问题而设计的一组工具和语言的常用术语。
The term I'd say most accurately describes the type of problem you're talking about is a constraint satisfaction problem.
More specifically, you're in the realm of weighted constraint satisfaction.
Constraint programming is the usual term for a set of tools and languages that are designed specifically for solving these types of problems.
匹配强制条件是范围搜索，具体是正交范围搜索。相关文献属于计算几何。按可选条件排序是一种排序操作。
Matching the mandatory conditions is range searching, specifically orthogonal range searching. The relevant literature belongs to computational geometry. Ranking by optional conditions is a sorting operation.