启发式算法的最优决策树

Question

我有以下格式的启发式：

if a == 1 and b == 1 and c == 1:
    do something
if a == 1 and b == 1 and c == 2:
    do something
if a == 3 and b == 2 and c == 1:
    do something
if a == 2 and b == 2 and c == 1:
    do something
if a == 3 and b == 1 and c == 3:
    do something
etc.

当然，这会产生许多不必要的比较，如果语句嵌套如下，这些比较是可以避免的：

if a == 1:
    if b == 1:
        if c == 1:
            do something
        if c == 2:
            do something
etc.

假设我有一个情况的元组集合(a, b, c)是有限的，并且每个元组都有相同的被算法接收的可能性，我如何生成一个最优的决策树，即它对一般情况进行的比较次数最少，或者当所有输入都通过它时，它使比较总数最小化？

我想是这样的：

In: optimal_tree([(1, 1, 1), (1, 1, 2)])
Out: "if a == 1:
          if b == 1:
              if c == 1:
                  do something
              if c == 2:
                  do something"
In: optimal_tree([(1, 1), (2, 1), (2, 2)])
Out: "if a == 2:
          if b == 1:
              do something
          if b == 2:
              do something
      if a == 1:
          do something"
     OR
     "if b == 1:
          if a == 1:
              do something
          if a == 2:
              do something
      if b == 2:
          do something"

Answer 1

规则引擎和数据库查询也经常处理这个问题。您可能需要研究这些背后的实现。

他们有几种方法来处理这个问题（尽管没有一种是完美的）：

• 按照规则/查询中定义的顺序进行比较
• 根据统计信息重新排序比较。例如，数据库将首先处理具有最大值差异的索引列

如果你想让你的算法更快，你可能想研究散列&如果你还没有做索引的话。这带来了更大的规模优势。