一系列复杂条件的部分验证

解决方案完全取决于您所说的有向无环图(DAG)实际表示的内容。是节点和或节点,还是条件分支?

如果它是一个AND/OR/NOT图,那么您需要从叶子开始计算节点的真值。这不是广度优先搜索,而是一种反向广度优先方法。计算叶的值,然后向后计算内部节点的值;最终,您将得到根节点的评估结果(真/假)。

听起来您正试图解决一个名为“[常数折叠][1]”的常见编译问题( http://en.wikipedia.org/wiki/Constant_folding

True AND X = X 或 True OR X = True 帮助修剪树木的大部分(据我所知,这个微不足道的实现是一个深度优先和回溯的问题,而不是广度优先,但不管怎样,它不是很多代码)。