4.2.4 算法描述和实现
基于上述对区间运算的分析,我们提出引入一个迭代区间算子(Iterative Interval Arithmetic,IIA)来对其进行改进。图4-13所示是进行了若干轮迭代的迭代算子的工作过程。由于变量区间在每轮都得到了削减,那么当迭代结束时,所得到的区间集一定是在相同输入条件下所有变量的最精简区间集。另外,如果将区间运算看作一个函数,那么这个区间集也是该函数的不动点。而图4-14所示的是迭代算子所产生的另外一种情况,即经过若干轮的迭代之后检查出了不一致,也就是产生了一个空区间(这同样也是一个最精简的区间),这说明路径基于当前的变量区间集是不可达的。
图4-13 迭代算子运算到不动点的过程
图4-14 迭代算子检查到不一致的过程
为了更好地描述IIA的功能,我们使用下述伪代码来进行描述。
(https://www.daowen.com)
正如4.2.1节所述,弧一致性检查方法经常与搜索算法结合起来使用。因此,我们把算法4-2和BFS-BB结合起来,在本书中叫作BFS-BB-IIA。
BFS-BB-IIA有两个阶段。第一个阶段是预处理操作。待覆盖路径p是BFS-BBIIA的输入,其中包含着变量的集合X={x 1,x 2,…,x n}、变量的区间集D={D 1,D 2,…,D n},以及要满足的约束集合。首先,IIA检查弧一致性。如果检查出不一致,那么由于检测出了不可达路径退出BFS-BB-IIA。如果未检查出p不可达,但是D当中有无限大的区间,那么IIA对这些无限大的区间进行削减并判断弧一致性。这个步骤可能一直持续到不再检查出不一致。第二个阶段进行BB搜索。对FV中的所有变量进行排序,返回第一个待赋值变量(如x 1)。不失一般性,下面的介绍都假设当前变量为x i。从x i的区间Di中为其选择一个赋值V i。对于当前所有变量的区间集,IIA检查弧一致性。如果结果一致,那么将x 1放入PV,对D进行更新。对其他变量的排序和赋值重复进行,直到所有变量都有一个合适的赋值{V 1,V 2,…,V n}使得p可达。{x 1↦V 1,x 2↦V 2,…,x n↦V n}(Vi∈Di)是该CSP的一个解。如果结果不一致,那么需要首先通过F(V i)(式(3-6))为x i从D i中计算出另一个值,然后IIA继续判断弧一致性。如果D i中已经没有值了,那么需要从PV中选择一个变量并对它重新赋值,这就是回溯。
可以看出迭代算子在BFS-BB-IIA的3个步骤中都发挥作用,同时它也以之前所描述的两种方式参与了约束求解,即搜索开始前的预处理以及搜索过程中的前向检查。我们使用不同的标记来标识它所起作用的不同阶段:第1行的不可达路径检测(Infeasible Path Detection,IPD)、第7行的初始区间削减(Initial Domain Reduction,IDR)、第15行的变量赋值判断(Variable Assignment Determination,VAD)。IPD和IDR用于预处理,VAD用于前向检查。除了不同的使用阶段,还有两点可以对这几个方法进行区分。第一点是输入:IPD的输入是所有变量的区间集,这个区间集有可能令p不可达;IDR的输入是所有变量的区间集,这个区间集中可能包含无穷大的区间;VAD的输入是所有变量的区间集,这个区间集中的每个区间都有有限的上、下界,而且PV中的变量和当前变量的区间都是[V,V]的形式,事实上是一个确切值。第二点是处理矛盾的区间信息的方式:由于区间运算的保守性,如果IPD时检查出不一致,那么该路径肯定是不可达的,没有任何必要进行后续的搜索操作;而当IDR检查出不一致时,可以认定初始区间削减策略有问题,因而需要对其进行调整;对于VAD来说,检查出不一致只能说明当前变量的当前赋值不是最终解的一部分,而后续应该如何调整已在上一章进行了介绍。
迭代的区间运算(IIA)与类似AC-3这样的弧一致性检查方法都是前向检查方法,其作用是检查所有变量的区间集是否能够满足它们之间的约束,并通过去除部分搜索空间来提高搜索效率。相比之下,IIA主要关注分支条件,这其中所涉及的可能不止两个变量,而当不一致被检查出来时,被缩减的区间可能涉及所有相关的变量。
上述分析说明,一方面,在某些情况下,如对于测试变量区间比较大的实际工程项目,IIA由于其粗粒度的检查方式可能效率更高。另外,IIA也适用于浮点型变量。而另一方面,这种粗粒度的检查方式会导致精度的损失,其原因可以追溯到区间运算的保守性。而迭代算子的提出就是为了某种程度上能够提高区间运算的精度,所以可以看出IIA是在精度和效率之间的一种折中。
