给定输入（算法）匹配的规则

Question

假设我有以下类别（及其可能的值）：

animal: any, cat, dog
color: any, white, black, gray
gender: any, male, female
[...]

或者更一般地说...

category: <array of values>

(1) 假设我有一组可配置规则，例如：

when animal is any, color is gray, gender is male, call x
when animal is dog, color is gray, gender is male, call y
when animal is any, color is any, gender is any, call z
[...]

(2) 以及一些输入值。

问：是否有一种算法可以解决根据给定的输入查找匹配规则（优先级给予找到的最具体的规则）的问题？

例1：

input (animal:dog, color:gray, gender:male)

它会调用“y”

例2：

input (color:gray, gender:female)

它会调用“z”

更合适的方法是基于规则构建搜索树（树的每个级别都是一个类别）？

比如：

- any animal
  - any color
    - any gender => z
  - gray
     - male => x
- dog
  - gray
     - male => y

有更好的方法吗？

谢谢！

Answer 1

我会将规则散列到映射中，然后使用相同的散列进行查找。

map[hash(animal, color, gender)] = function to call

call map[hash(inputanimal, inputcolor, inputgender)]

这将确保更快地创建规则并解析正确的函数以根据输入调用。

如果规则必须完全匹配，否则属于通用的any,any,any，那么只需通过以下方式完成：

if map.contains(hash(inAnimal, inColour, inGender)) 
   x = map[hash(inAnimal, inColour, inGender)]
else
   x = map[hash(any, any, any)]

否则，如果它从输入开始并连续选择每个参数上的any规则，那么您可以这样做。

让哈希函数接受值数组。当您尝试匹配规则时，您从输入开始，然后连续将每个输入切换到任何一个，直到找到匹配项。

def key hash(array[])

....

解决过程...

input[] = {inAnimal, inColour, inGender}
function x
for(i = 0 to input.size) {
   if(map.contains(hash(input)) {
      x = map[hash(input)]
      break
   }
   input[i] = any
}
call x

Answer 2

经过以下修改的决策树可以工作：

1. 使用所有规则以正常方式创建决策树，以“any”作为边

2. 递归遍历时，遍历“value”和“any”并跟踪数字“any”在每个解决方案中，返回具有最少 'any' 的解决方案

   def 遍历（值、级别、树、任意计数）：
   如果树是一片叶子：
   返回（appr_func，anyCount）

   <前><代码>v1 = 无
   如果树中的值[级别]：
   v1 = 遍历（值，级别+1，树[值[级别]]]，anyCount）

   v2 = 无
   如果树中有“任何”：
   v2 = 遍历（值，级别+1，树['任意']，任意计数+1）

   如果 v1!=无：
   如果 v2!=无：
   如果 v1[1]

Answer 3

正确的答案取决于您想要获得多奇特的效果。有些东西像 Rete 算法。谷歌“专家系统”。我曾在拥有规则评估系统的大公司工作过，但他们并不是在内部编写这些系统，而是购买商业包。

如果您的需求很简单，那么每个级别都是一个类别的搜索树就可以了。如果应用程序只有特定的项目和一个通用的“任何”项目，那么这将工作得很好。如果存在多个级别的通用性（“哺乳动物”、“脊椎动物”、“动物”），那就会变得更加困难。

如果速度是问题，但内存使用不是问题，那么您也可以尝试哈希表的哈希表方法。哈希表中的每个条目都是一个键值对。在顶级哈希表中，键是顶级类别：“狗”、“猫”、“任何”。该值是另一个哈希表。在第二级哈希表中，键是颜色，值是另一个哈希表。等等。最深哈希表的值包含函数指针、闭包或编程语言提供的任何动态调用方法。

Answer 4

我首先会给所有变量一个唯一的值（数组位置）

动物：任意 = 0；猫=1；狗 = 2
性别：任意=0；男 = 1；女性 = 2
颜色：任意 = 0；白色=1；黑色=2；灰色=3；

然后我会给每个可能的组合赋予一个查找值。

             Animal-|        ANY        |       cat         |       dog         |       
                    ------------------------------------------------------------- 
             Gender-| any | male |female| any | male |female| any | male |female| 
                    ============================================================= 
      Color-any     |  0  |   1  |   2  |  3  |   4  |   5  |  6  |   7  |   8  |
                    ------------------------------------------------------------- 
            white   |  9  |  10  |  11  | 12  |  13  |  14  | 15  |  16  |  17  |
                    ------------------------------------------------------------- 
            black   | 18  |  19  |  20  | 21  |  22  |  23  | 24  |  25  |  26  |   
                    ------------------------------------------------------------- 
            gray    | 27  |  28  |  29  | 30  |  32  |  33  | 34  |  35  |  36  |
                    =============================================================

每个查找值可以通过以下方式计算：

(Animal * number of animals) + Gender + (Color * number of animals * number of sexes)

或在以下情况下：
动物是任意的，(0)
颜色为灰色，(3)
性别是男，(1)

(Animal * number of animals) + Sex + (Color * number of animals * number of sexes)
(   0   *        3         ) +  1  + (  3   *        3          *        3       )  

(0 * 3) + 1 + (3 * 3 * 3)  
   0    + 1 +      27       = 28 (the lookup value from the grid above)

28 表示呼叫 X。

所以在你的程序中：

计算你的值
将该值与已知情况进行比较

if Value in (1,2,8,13,14,15,21,28)    then X
if value in (3,4,5,23,24,26,34,35,36) then Y
if value in (0,9,12,16,17,22,25)      then Z

显然，这些值实际上可以存储在配置文件中，因此您可以更改逻辑而无需重新编译。

Answer 5

您几乎可以直接将其转换为 scala 代码。

通常，您会在 scala 中使用大写的 Animal、Cat、Dog，但为了匹配您的示例，我在这里保留了惯例：

abstract sealed class animal () {}
 object cat extends animal () {}
 object dog extends animal {}

abstract sealed class color () {}
 object white extends color {}
 object black extends color {}
 object gray  extends color {}

abstract sealed case class gender () {}
 object male   extends gender {}
 object female extends gender {}

def input (a: Option[animal], c: Option[color], g: Option[gender]) = (a, c, g) match {
  case (Some (dog), Some (gray), Some (male)) => println ("y called without freedom")
  case (_,          Some (gray), Some (male)) => println ("x called with animal" + a)
  case (_,          _,           _          ) => println ("z called with anmimal: " + a + "\tcolor: " + c + "\tgender: " + g)
}

input (Some (dog), Some (gray), Some (male))
input (None,       Some (gray), Some (female))

结果：

y called without freedom
x called with animal: None

您必须注意“输入”方法中的排序。具体方法必须先于非具体方法。

在某些情况下，根据您的描述，无法决定要做什么，但您必须决定先进行哪个测试：

(a, c, _)
(_, c, g)
(a, _, g) 

是否所有人都有 1 个开放案例。如果没有其他内容，(a, c, g) 可以匹配它们中的任何一个，但只会匹配第一个。

您必须提供一般情况（_、_、_），但如果没有意义，可能会引发错误。