关于强制和可选条件元组的规则匹配算法的CS术语

Question

我正在尝试研究文献中的算法来解决一个特定的问题,但我不认为我完全知道正确的搜索术语来描述我正在寻找的东西.

目标是建立一个可查询的规则数据库,其中每个规则都被指定为元组条件 - 一些是强制的,一些是可选的.对系统的查询由关于世界的事实元组组成,并返回其强制条件与查询中的事实匹配的所有规则的列表.每个规则由匹配的可选条件的数量×权重评分,并且列表由此排序.

举个例子,如果我用它来写一个室友匹配服务,那么规则就是这样的

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论文也很棒.

Answer 1

我想说最准确地描述您所讨论的问题类型的术语是约束满足问题。

更具体地说，您处于加权约束满足的领域。

约束编程是专门为解决此类问题而设计的一组工具和语言的常用术语。