algorithm - 给定一组规则生成决策树

Question

这几天一直在思考这个问题，没有找到最优解，所以提出这个问题。

假设我们有一组 N 个变量，用户可以组合这些变量来创建规则列表和以下操作，例如:

variables V_1,V_2,V_3
V_1 > 5 -> "Turn left"
V_2 < 6 -> "Turn right"
1 < V_1 < 4 -> "Continue straight"
V_1 = 0 AND V_2 > 6 AND V3 > 5 -> "Go backwards"
default -> "Stay"

变量不一定是整数，并且假设规则全部由一系列 AND 子句组成，后跟一个操作。

我想做的是构建一个决策树，使我能够快速处理像 (0,7,9) 这样的输入并返回正确的操作。截至目前，我唯一的想法是划分变量空间并查看输入状态适合的位置，但这似乎是一个缓慢的解决方案:有人知道可能更快的方法吗？

Answer 1

是什么让它变慢了？规矩多？长规则？变数多？规则处理缓慢？

如果您没有很多变量 规则，我显然会选择哈希表。

这是针对您所述问题的树示例(不一定是最优的)。

variables V_1,V_2,V_3
V_1 > 5 -> "Turn left"
V_2 < 6 -> "Turn right"
1 < V_1 < 4 -> "Continue straight"
V_1 = 0 AND V_2 > 6 AND V3 > 5 -> "Go backwards"
default -> "Stay"

   V1         V2      V3
   <0 ------- <6 --------------- Right
              >=6 -------------- Stay

   0 -------- <6 --------------- Right
               6 --------------- Stay
              >6 ---- <=5 ------ Stay
                      >5 ------- Backwards

   ]0-1] ---- <6 --------------- Right
              >=6 -------------- Stay

   ]1-4[ ----------------------- Straight

   [4-5] ---- <6 --------------- Right
              >=6 -------------- Stay

   >5 ------- <6 --------------- Right
              >=6 -------------- Stay