3.2.2 变量动态排序决策机制
最佳优先搜索的分支限界法将活节点表组织成一个优先队列,按优先队列中规定的节点优先级选取优先级最高的下一个节点成为当前扩展节点。如上所述,用状态表示每个节点,其中变量区间状态有序集是根据决策机制确定的。本书提供了动态的决策机制确定变量的排序,这个排序就是变量赋值顺序的优先级。在很多搜索算法中,决定变量赋值顺序的原则都是它们的区间大小,因为这样可以令整个搜索树的节点数目最小。但是当不同的变量具有相同的区间大小时,利用区间大小排序的决策机制就失效了,需要有一种补充策略来解决这种无法打破的僵局。
图3-8 使用区间迭代优化策略的分支限界算法流程图
分支限界调用的区间运算部分从程序入口开始对待覆盖路径进行数据流分析,如果变量的取值在某个分支节点处导致不可达路径的产生,则赋值失败,不再向下进行数据流分析。距离程序入口越近的表达式对于赋值成功与否的影响越大。因此,需要结合表达式出现的顺序对程序中的变量进行分级。因为变量存在于控制流图的分支节点上,因此给出级别的定义。
定义3-10 对于一条路径上的k个分支(nqa,nqa+1)(a∈[1,k]),一个分支的级别rank(n qa,nqa+1)标志着它在整条路径中的顺序。(https://www.daowen.com)
第一个分支的级别是1,第二个分支的级别是2,依此类推。而出现在分支上的变量拥有与分支相同的级别。一个分支上可能有多个变量,即多个变量可能有相同的级别。而一个变量也可能出现在多个分支上,所以一个变量也可能拥有多个级别。对于没有出现在某个分支上的变量,我们认为它的级别是无穷大。
变量都出现在表达式中,所以需要提取表达式。由于路径p是由控制流图节点组成的,而表达式存储在控制流图节点中,因此提取含有表达式的控制流图节点就相当于提取了表达式。在提取表达式的时候是提取了含有表达式的节点,并将它们存储在线性链表中,因此为了提取表达式中的变量,需要依次遍历线性链表中的每一个节点。任一变量的级别和出现的次数都初始化为-1。在给不同变量进行赋值的过程中,只要当前的状态达到稳定,即当前变量赋值成功,就依照决策机制动态更新,重新进行变量排序,以确保当前变量是优先级最高的变量。获取变量级别的算法在3.1.5节中有详细介绍。
这是一个双关键字(区间大小+变量级别)排序。通过快速排序(quick sort)得到根据区间大小的排序结果,对于相同区间大小的变量会从入口开始沿着整个路径根据变量级别进行排序,一旦得出结果则随时退出,因为只要得到序列的第一个元素即可。这个双关键字排序正是BFS-BB中使用的排序方法,现在也考虑加入更多的元素进行多关键字排序,并通过实验验证其效果。
