基于模式回溯的#WS(≠)快速定界算法

2020-12-09 09:46翟治年卢亚辉潘志刚周武杰

小型微型计算机系统 2020年12期

翟治年，卢亚辉，俞坚,潘志刚，周武杰，3

1(浙江科技学院信息与电子工程学院，杭州 310023)2(深圳大学计算机与软件学院，广东深圳 518060)3(浙江大学信息与电子工程学院，杭州 310027)

1 引言

工作流可满足性(Workflow Satisfiability,WS)关系到业务安全策略与执行资源分配的协调与否，是安全规划的一项关键验证[1,2]，并具有执行场景发现问题(Scenarios Finding Problem,SFP)[3]等重要的应用变体.为定量考查WS实例的可满足性，并扩展可满足判定的途径，文献[4,5]提出了相应的计数问题(Counting Workflow Satisfiability,#WS).它是#CSP(Counting Constraint Satisfaction Problem)[6,7]的特殊形式，具有特定于业务安全的约束配置、可能的流程相关性[2]，步骤数量受限[8]、约束稀疏[9]等特征.在应用上，#WS与安全工作流的资源弹性[10,11](部分资源失效时的WS)问题有密切关系，为其提供了参考指标和验证手段[4,12].近年来，云制造[13]、众包[14]等依赖于第3方资源的新型工作流环境得到了蓬勃发展.此类资源具有虚拟、分散、多变等特性，失效和违约风险较高[15]，使业务安全规划的资源弹性要求变得日益突出，亟待加强#WS等相关问题的研究.

在基本的互斥约束下，#WS已进入#P完全问题类[16]，较NP完全问题更为困难[17].而其全局计数要求又很难适用局部和智能搜索方法.特别地，在第3方资源环境下，候选资源数量大大超过工作流步骤[10,18,19]，给#WS算法造成了新的性能压力.

现有#WS研究集中在常见的互斥和绑定约束下.其核心问题是仅含互斥约束的#WS(≠)(绑定约束可以多项式时间消去[5])，在求解性能上已取得了一定进展.2015年，文献[5]将#WS(≠)归约为逻辑可满足计数问题(Counting SATisfi ability,#SAT)[20]，借助其高效求解器sharpSAT，取得了一定的实测时间性能.由于归约所得逻辑变量规模巨大，整体时间复杂度高达O*(2|R||S|)，其中S和R分别为步骤集和资源集.且其所用组件缓存技术极耗内存，空间复杂度也达到同一量级，综合性能很受局限.2016年，文献[4]利用基于赋权集容斥原理和快速zeta变换的集合划分方法，建立了一种#WS(≠)的动态规划算法，具有O*(2|S||R|)时间复杂度，但其空间复杂度仍为指数级，实际占用增长很快.2016年，文献[9]通过树分解技术来利用约束图的结构信息，应用树分解回溯计数的方法(Counting Backtracking Tree Decomposition,#BTD)求解#WS(≠)，并对约束验证范围进行了简化，较前述工作更好地控制了空间开销.而其时间复杂度为O*(|R|W+1)，其中W为约束图树分解宽度.在工作流应用常见的低约束密度条件下，W的值通常受限，因而该算法有比较明显的时间性能优势.但其对大量资源带来的性能压力，缺乏有效的约简机制.

最近，在WS研究中提出了一种模式回溯法[21,18,22].在互斥等资源独立性约束条件下，可以有效克服资源集规模造成的解空间膨胀问题，并利用回溯法的优化技术积累.本文将根据模式回溯法的的两层求解机制，通过精确的模式可行解计数，结合模式资源指派图的匹配数量定界，提出一种# WS(≠)定界算法.实验表明，该算法在高资源配比、低约束密度条件下，能够快速计算#WS(≠)解的上、下界，且其上界比较接近于精确解.

2 预备知识

WS以一组工作流步骤S为变量集、每个s∈S有一个值域Rs⊆R，其中R是所有资源的集合.对步骤变量的取值，有一组约束C.WS(≠)是C中仅含互斥约束的WS.任何互斥约束c都作用于两个变量，要求它们取值不同.WS(≠)的目标是求任意一个可行解，即从S到R的一个赋值映射，使其满足所有约束和(各变量的)值域要求，或指出可行解不存在.而#WS(≠)的目标是统计WS(≠)可行解的数量.通常有解空间搜索或动态规划两种求解途径.

任何部分赋值，即从T⊆S到R的映射，都有其划分模式：当且仅当两个变量赋值相同时，将其归入同一个块，相应块的集合形成赋值变量集T的一个划分，称为模式.每个模式都是一组部分赋值的抽象.由此可以得到问题解空间的一个压缩映像，即模式空间.它是一棵以模式为结点的根树，描述了对空划分逐个加入新变量，最终扩展至完全模式的可能路径.其叶结点对应于所有完全模式.

部分赋值满足互斥约束c(即其给c的两个变量分配不同的值)，当且仅当其模式满足c(即其将c的两个变量分入不同的块).若对模式空间进行搜索，发现一个模式违反约束，即可排除以其为模式的所有部分赋值，非常高效.然而，问题解空间是根据值域构造的，搜索时只需要验证约束.而压缩为模式空间后，相应于模式结点的部分赋值不一定符合值域要求，从而需要验证.文献[18]解决了模式真实性验证(根据一个模式判定相应的部分赋值有无可能满足值域要求)的问题，使得可以对模式空间进行回溯搜索，通过可行模式得到WS(≠)的可行解.验证模式真实性的主要思路是给定任意模式P，为每个块b∈P计算恰当的资源指派邻域Nb⊆Rb=∩s∈bRs，这里Rb称为块b的值域.根据P中所有块的邻域，可得(资源)指派图G(P).存在符合WS(≠)值域要求且以P为模式的部分赋值，当且仅当二分图G(P)存在左(块侧)到右(资源侧)完备匹配.按此匹配为完全可行模式各块中的步骤分配资源，即得WS的一个可行解.特别地，文献[18]利用子模式相对父模式只有一个差异块的特点，实现了增量式的真实性判定.只须计算差异块的邻域，并计算从差异块出发的增广路，即可将父模式指派图扩展为子模式指派图，并由前者的匹配修改得到后者的匹配.

3 #WS(≠)的模式回溯定界

现有模式回溯法仅适用于WS(≠).若需统计所有可行解的数量，不仅要相应改变算法结构，而且所得算法将面临着更严重的性能压力.模式空间不仅实现了整个问题解空间的压缩，而且将部分赋值归类为一个个的模式.相对于平面化的搜索空间，这种层次性有利于从宏观上确定可行解数量的界，在保证一定结果质量的前提下降低计算负担.本文在文献[18]刚刚提出的增量模式回溯法基础上，为#WS(≠)建立了一种模式回溯定界算法(Bounding Algorithm Based on Pattern Backtracking).其问题求解思路可概括为以下几点：

1.对每个模式P，均使用完全指派图(对块b∈P，Nb=Rb)，以防统计时遗漏可行解.WS(≠)求任意一个可行解，在可行解存在性等价的前提下，可以使用更为精简的指派图来提高效率.而#WS(≠)不能遗漏任何可行解，只能使用完全指派图(每个块的指派邻域都等于该块的值域).

2.每个(左到右完备)匹配都可将完全可行模式转化为一个真实可行解，不同匹配的转化结果不同.故找到完全可行模式后，对其资源指派图中的匹配数量计算上、下界，即为此模式所含可行解数量的界.而在验证模式真实性时，只关心匹配的存在性，求一个匹配即可.

3.用回溯法遍历模式空间，对每个完全可行模式，计算其所含可行解数量的界，并相加汇总.

4.适当利用约束图和指派图的结构信息.通过连通片分解，由前者/后者得到独立的# WS(≠)/二分图匹配计数子问题，分别求解，并相乘汇总.

下面给出具体算法.先由上述思路第4点得主控函数.

算法1.#MAIN//计数主控函数

输入：S、R、 {Rs|s∈S}和C作为全局变量可用，其中C只含互斥约束.

输出：WS(≠)可行解数量下界LB和上界UB.

1.LB←1;

2.UB←1;

3.分解S和C构成的约束图，得一连通片集Comps;

4.for(compi∈Comps){

5.Si←V(compi);//V(compi)是compi的顶点集

6.Ci←E(compi);//E(compi)是compi的边集，每边对应一条互斥约束

7. 〈LBi,UBi〉←#IPB≠(∅,∅,∅,Si,Ci);

8.LB←LB·LBi;

9.UB←UB·UBi;

10.}

11.return〈LB,UB〉;

其中调用了如下模式回溯计数算法.它体现了前述思路的第1、3两点.

算法2.#IPB≠(P,&G,M,Si,Ci) //递归过程

输入：已满足约束和值域要求的模式P；其完全指派图G=G(P)，&表示传址；M是G的左到右完备匹配，其大小为|P|；Si和Ci表示一个连通片内的变量集和约束集.

输出：在Si和Ci导出的WS子问题中，其模式扩展于P的可行解数量下界LBi和上界UBi.

1.LBi←0;

2.UBi←0;

3.if(|∪P|=|Si|){//子问题的完全可行模式

4. 〈LBi,UBi〉←#MATCH(G);//P为满足C的完全模式，对其指派图中符合值域的匹配数进行界定

5.}else{

6. 按一定排序规则选择扩展变量s;//参见文献[18]

7. 计算用s扩展P形成的满足C的模式集X(P);

8. for(Pj∈X(P)){//有未搜索的子模式

9. 基于G计算Pj的完全指派图Gj=G(Pj);//指派图增量计算，参见文献[18]

10. 基于M计算Gj的左到右最大匹配Mj;//匹配增量计算，参见文献[18]

11. if(|Mj|=|Pj|){//Mj完备

12. 〈LBij,UBij〉←#IPB≠(Pj,Gj,Mj,Si,Ci)//递归调用;

13.LBi←LBi+LBij;

14.LBi←LBi+LBij;

15. }

16. 恢复G;//利用增量计算时备份的差异信息

17. }//for

18.}//if-else

19.return〈LBi,UBi〉;

相对于用模式回溯求解WS(而不是#WS)，需要注意第16行恢复指派图是无条件的，并非模式验证失败或发生回溯时才进行.算法2可以对完全可行模式进行精确计数.但为了进一步得到真实可行解的数量界，须调用如下的匹配计数定界算法(其中函数LV()和RV()分别取二分图的左侧和右侧顶点集).它体现了前述思路的第2、4两点.

算法3.#MATCH(G)

输入：从模式(划分块的集合)到资源集的二分图G

输出：其左到右完备匹配数量的下界lb和上界ub.

1.lb←1;

2.ub←1;

3.对二分图G进行分解，得到连通片集GComps;

4.for(gcompk∈GComps){

5. if(gcompk是完全二分图) {

6.p←0;//p表示已考查的左侧顶点数

7. for(b∈LV(gcompk)){//对每个左侧顶b

8.lb←lb·(|RV(gcompk)|-p);

9.p←p+1;

10. }

11.ub←lb;//可精确计数，上下界重合

12. }else{//非完全

13.lb←1;

14.p←0;//p表示已考查的左侧顶点数

15. for(b∈LV(gcompk)){//对每个左侧顶b

16.ub←ub·min{|Rb|,|RV(gcompk)|-p};

17.p←p+1;

18. }

19. }//if-else

20.}

在算法3中，对二分图进行连通片分解后，逐连通片计算匹配数上、下界.若连通二分图是完全的，不难精确计算其匹配数，由第6-第11行代码完成.否则，由第13-第18行代码进行定界.因为可行模式的指派图必然存在匹配，第13行将下界取1.而上界由第15-第18行代码计算，其基本思路是将每个左侧顶点的值域大小相乘.但是左侧顶可匹配的邻域还会受到一定限制.设b是连通二分图中第p+1个被检查的左侧顶点.事实上之前每检查一个左侧顶，都是从其可匹配的邻域中隐含地选择一个右侧顶，形成一条拟匹配边，得到一个更小规模的匹配子问题.删除这一对顶点及其所有关联边，不影响子问题的计数.因此检查到第p+1个左侧顶时，在相应的子问题中，至多有RV(gcompk)-p个右侧顶可匹配.应取其与|Rb|的较小者作为b可匹配的邻点数上界.

整体上，算法1和现有的模式回溯WS算法一样，至多对O*(B|S|)(B|S|表示第|S|个贝尔数)个模式结点进行检查，每个结点处的验证开销为多项式级.算法1要对每个完全可行模式进行匹配计数，但由算法3易知，此过程可在多项式时间完成.因此，算法的整体时间复杂度仍为O*(B|S|).算法1没有特殊的空间需求，和模式回溯WS算法一样，具有多项式级空间代价.

4 实验研究

现在对算法1进行实验研究，并与文献[5]的sharpSAT归约(R2sharpSAT)，文献[4]的#DP和文献[9]的#BTD简化(#BTD-S)算法对比.测试环境为主频3.6GHz/睿频4.2GHz的Intel Core i3 CPU、8G RAM、CentOS 8系统、GNU C++编译器(-O3优化)、GMP6.2大整数库，单个实例执行时限为半小时.

实验1.4种#WS(≠)算法的性能对比

本实验将4种算法在不同步骤数量和资源配比下进行综合性能比较.由于互斥约束通常作用于职责分离的关键步骤，故取较低的约束密度.测试实例生成规则是：在[10,20]之间随机生成20个值，得到相应大小的S；对每个S，随机取25≤μ≤75，得到μ%|S|大小的R(μ%称为资源配比)；再从代表分散(D)、低(L)、中(M)、高(D)的4个区间{[1,100],[1,33],[34,66],[67,100]}中随机选择授权比例区间AP，对每个s∈S，随机选取α∈AP，再随机取α%|R|个不同资源作为Rs；随机取5≤ω≤15，以概率ω%(称为约束密度)决定每对步骤之间是否存在互斥约束，得到C，并保持其它参数不变，重复生成5次C，相应得到一组5个同参数实例，测试时对每组的解出实例取平均结果.4种算法测得的解出率(用SP表示)、执行时间、峰值空间如表1所示.

首先将算法1与#BTD-S比较.可以看到随着实例规模的变化，两者的空间占用均保持较小的值，且彼此差距不大.因为#BTD-S具有全局动态规划与局部回溯相结合的算法结构，所以带有子问题解的缓存，更耗空间一些.算法1在12/20组实例上，平均空间占用不大于对方，略有优势.在各组实例上，算法1的解出率均不低于对方.这主要源于算法1的执行时间优势.算法1在与对方解出率相同的15/20组实例(不含第20组实例，两者均解出2/5，但具体实例不全相同，也不含#BTD-S无数据的第19组实例)上，所需的执行时间也较少，其性能是对方的1.18-368倍不等，平均为54.9倍.在剩余3组两者均完全解出的实例上，#BTD-S的性能是算法1的10.6-18.2倍，平均14.7倍.整体上，算法1有很明显的时间性能优势.

表1 4种#WS(≠)算法的时间(s)和空间(MB)代价Table 1 Cost of time(s)and space(MB)for the 4 #WS(≠)algorithms

将算法1与#DP比较.由于多项式和指数空间复杂度的差异，算法1有明显的空间性能优势.由表1可以看到，#DP的空间占用始终高于算法1，且随着|S|的增大，差距不断扩大，从1.07倍增长到207倍，平均为22.1倍.#DP的时间复杂度低至2的指数级，较算法1更有优势.测试表明，在8G内存和半小时限制下，#DP解出了第17组的全部5个实例，而算法1有2个未解出.除此以外，算法1的解出率均不低于对方.在两者均完全解出的17组实例上，算法1的时间性能均优于对方，比率为1.53-464548倍不等，平均为62019倍.这主要是由于#DP通过系统、规整的计算来控制时间复杂度，且初始开销很高，对小规模的实例并无优势.而对于稍大规模的实例，#DP会很快遭遇空间性能的瓶颈.因而其仅在|S|=18(第17组实例)这样的过渡区域，表现出了一定的优势.在时间特别是内存资源受限条件下，算法1的整体优势更为明显.

将算法1与R2sharpSAT比较.R2sharpSAT始终具有很高的空间占用，达到算法1的258-278倍，平均258倍.R2sharpSAT的空间代价主要由组件缓存导致，由于使用了缓存清理技术，并未随问题规模明显增长.在解出率上，R2sharpSAT也在第17组实例上超过了算法1，多解出了1个实例.但其在第19和20组实例上解出率均为0.算法1在与对方解出率相同的17/20组实例上，有15组优势，时间性能达到对方的18.8-116157倍不等，平均8151倍，有2组劣势，对方性能是算法1的6.10和44.1倍.算法1仍然有整体上的优势.

总体上，算法1的综合性能比较突出.其空间性能仅在个别实例上弱于#BTD-S，时间性能在多数实例上有明显优势，但在极少数实例上弱于其它算法.这种优势首先来源于模式空间对原始解空间的压缩，其搜索范围只取决于步骤数量，是与资源数量无关的.同时，在低约束密度下，约束图结构较为松散，容易形成多个连通片，降低子问题的步骤数量.进而，在叶结点处计算匹配数时，没有采用指数时间的动态规划精确计数，而是尽可能分解二分图，然后通过快速方法定界，使前述两点优化的效果得以保持.相形之下，#BTD-S虽然也较好控制了内存占用，但其侧重于对约束图的结构进行深入的分解，对于大量资源造成的解空间膨胀问题，缺乏有效的解决机制.而其它两种算法整体上较#BTD-S更弱，很大程度上是受空间性能制约.当然，其它算法均给出精确的可行解数量，而算法1只能给出其上、下界.表1进一步给出了算法1的界相对其它算法所得精确值的比率(组内各比率求平均，第20组只计算了与#BTD-S共同解出的1个实例).可以看到，其上界质量较好，为精确解的1.06-2.79倍，平均1.41倍.

实验2.算法1时间性能随资源配比的变化

如前述，每组实例主要有|S|、资源配比和约束密度3个参数.由实验1可以看到，算法1的解出率和时间性能随着|S|的增大，大体上呈现下降的趋势.工作流应用中，约束密度通常较低，变动不大.而在当前常见的第三方资源环境下，资源配比|R|/|S|向上波动的空间很大.根据实验1的测试情况，我们选择|S|=15，取ω=10，在20%、50%、80%三种授权比例下，让资源配比从4到20，以步长4变化，进一步了解算法1解出率、执行时间和所得界的变化.为消除约束分布偶然性影响，每组参数生成50个实例，结果如表2所示.

表2 算法1执行时间(s)随资源配比的变化Table 2 Variation of the run-time(s)of algorithm 1corresponding to the ratio of resource

首先，资源配比的增大，使得80%授权的第5组出现了2个未解出实例.进一步观察可知，随着资源配比的增加，平均执行时间大体呈增加趋势.对于偏离趋势的20%授权第3组实例和50%授权第2组实例，相应的最大执行时间也偏高.异常与这些个别值拉高平均值有关.另外，50%授权的第4组和第5组实例平均值接近，但第5组实例的最大值偏低，其平均值主要源于集体贡献.对原始数据进行统计，可知第5组较大的值更多，其中位数是第4组的6.2倍，且有37个值不小于第4组的中位数.对于同样的|S|，模式空间的大小是固定的.上述执行时间随资源配比增长的趋势，主要是因为在搜索结点处，为计算模式块的值域，需要在更大的资源范围中搜索.当其它条件一定时，更多资源会导致更多满足约束和值域要求的赋值，故表2中无论LB还是UB都呈现随资源配比而增长的趋势.

5 结论与下一步工作