4.1.2　问题的提出

约束满足问题通过寻优或搜索方法来解决,但是这类算法涉及回溯操作,而回溯操作在很多时候效率很低,如下面的例子。图4-2所示为作者所在项目组使用BFS-BB测试一个benchmark的实验结果,被测程序包含多种实际工程中常见的数据类型和控制结构,语句覆盖下有65条待覆盖路径。为这65条路径生成测试用例时,21条路径发生了回溯,占路径总数的32%,而这21条路径的测试用例生成时间却占据了总时间的81%。可见,必须提高回溯操作的效率才可能有效减少搜索的时间,也就是说分析利用搜索过程中的信息进而减少对搜索树的访问次数并提高搜索效率,是影响求解速度的关键。

图4-2　回溯路径数量比与时间比

有以下3个具体问题影响回溯算法的效率。

①大量时序回溯导致的盲目搜索。其表现可以通过图4-3(灰色部分代表死端)看出,即到达死端后不对矛盾的性质进行分析,而直接回溯到上一层变量,如果上一层变量仍无法解决矛盾,则继续回溯到上一层变量,直到抵达矛盾变量所在的层次。这种逐层回溯的方式由于没有分析出导致矛盾产生的变量而大量增加了对搜索树的访问。(https://www.daowen.com)

图4-3　时序回溯示意图

②在搜索过程中由不可达区间导致的无谓穷搜。如果不去除这部分不可达区间,将会导致不可达路径的产生,并进而导致很多运算变成无用的,据统计,这部分计算量占比为30%~75%[8]。研究人员已经逐渐意识到边搜索边检测的重要性,并将其应用于项目实践中。

③忽略变量间的相互关系。根据作者所在项目组前期的实验结果,当变量之间相互独立时,搜索时间与变量个数呈线性关系;当变量之间紧密线性相关时,搜索时间与变量个数呈多项式关系[4]。可见变量之间的相关性对搜索时间的影响很大,而通过寻求变量的相关性缩小矛盾的传播范围将有助于提高回溯的效率。