不过,在通常情况下,数学表达式树不一定是二叉树,内部节点可能只有1个子节点。如此,就要考虑根节点和下一内部节点参数数量的二维概率分布,记作 L(e,n)。
接下来,就是对随机树进行采样,从可能的运算符和整数、变量、常量列表中随机选择内部节点及叶子节点来对树进行“装饰”。
最后,计算表达式的数量。
经由前面的步骤,可以看出,表达式实际上是由一组有限的变量、常量、整数和一系列运算符组成的。
于是,问题可以概括成:
- 最多包含n个内部节点的树
- 一组p1个一元运算符(如cos,sin,exp,log)
- 一组p2个二进制运算符(如 ,-,×,pow)
- 一组L个叶子值,其中包含变量(如x,y,z),常量(如e,π),整数(如 {-10,…,10})
如果p1 = 0,则表达式用二叉树表示。
这样,具有n个内部节点的二叉树恰好具有n 1个叶子节点。每个节点和叶子可以分别取p1和L个不同的值。
具有n个二进制运算符的表达式数量就可以表示为:
如果p1 > 0,表达式数量则为:
可以观察到,叶子节点和二元运算符的数量会明显影响问题空间的大小。