3.3.2　变量的动态排序对比实验

1.实验设计

变量的动态排序是指:①选取小区间变量优先赋值;②区间相同的情况下依据变量的级别确定优先级,变量级别越高则优先级越高。

保持其他策略为最优的设置,在实验时对使用动态变量排序和只使用小区间优先赋值的方法进行对比(每种情况做20组实验)。

2.实验环境

①CPU为Intel(R)Pentium(R)CPU U5600@1.33 GHz。

②主板为联想3249A69(英特尔QM57)。

③内存为4 GB(2.92 GB可用)。

④显卡为Intel(R)HD Graphics(Pentium)。

⑤硬盘为希捷ST9250315AS。(https://www.daowen.com)

⑥操作系统为Windows 7家庭普通版。

3.实验数据

表3-9为变量的动态排序对比实验结果。其中,A代表变量的动态排序(区间大小+变量级别),B代表不使用变量的动态排序(只按区间大小排序,小区间优先赋值)。

表3-9　变量的动态排序对比实验结果

4.实验总结

可以看出变量的动态排序对于分支限界的影响是两方面的。

①能够减少测试用例生成的时间。当最大分支数分别为201和601时,对时间的减少可以分别达到86%和23%(具体能够减少多少时间与被测程序有关)。

②能够影响是否求解成功。两个实验中都出现了由于变量同区间后的随机排序导致求解失败的情况。变量的排序作为分支限界算法的一部分,对于其整体的求解能力是有很明显的影响的(在本实验中,求解成功率提高了30%~40%)。