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

Quick Bounding Algorithm for#WS(≠)Based on Pattern Backtracking

作　　者：翟治年[1] 卢亚辉[2] 俞坚[1] 潘志刚[1] 周武杰[1,3] ZHAI Zhi-nian;LU Ya-hui;YU Jian;PAN Zhi-gang;ZHOU Wu-jie(School of Information and Electronics Engineering,Zhejiang University of Science and Technology,Hangzhou 310023,China;School of Computer and Software,Shenzhen University,Shenzhen 518060,China;School of Information and Electronics Engineering,Zhejiang University,Hangzhou 310027,China)

机构地区：[1]浙江科技学院信息与电子工程学院,杭州310023 [2]深圳大学计算机与软件学院,广东深圳518060 [3]浙江大学信息与电子工程学院,杭州310027

出　　处：《小型微型计算机系统》2020年第12期2494-2499,共6页Journal of Chinese Computer Systems

基　　金：国家自然科学基金面上项目(61972357)资助;浙江省重点研发计划项目(2019C03135)资助;浙江省教育厅科研项目(Y201737476)资助。

摘　　要：WS(≠)是互斥约束工作流可满足性的量化问题,与第三方环境中有重要意义的资源弹性密切相关.为克服其求解性能瓶颈,本文利用模式回溯法的解空间压缩特性和两层求解机制,提出了一种真实可行解的数量定界方法.它对模式回溯法的结构进行扩展,实现完全可行模式的遍历和统计.对其中每个模式,计算其资源指派二分图上匹配数量的界.再汇总二者,给出#WS(≠)的上、下界.随机生成数据集上的实验表明,在高资源配比和低约束密度条件下,本文算法相对现有算法有比较突出的时间和空间性能,且其给出的上界相当接近于准确值.WS(≠)is the quantified problem of exclusion constrained Workflow Satisfiability.It is closely related to the issue of resource resiliency w hich is important in third-party environments.In this paper,to address its issue of performance bottleneck,a bounding algorithm for the amount of real feasible solutions is proposed using the property of solution space compression and tw o-layered solving mechanism of Pattern Backtracking(PB).First,all the full feasible patterns are found and counted via extending the structure of PB.Further,for each pattern of them,the amount of matchings in its resource assigning bipartite is bounded.All of them are summarized to give upper and lower boundaries for#WS(≠).Experiments on randomly generated dataset show that,under the conditions of high resource ratio and low constraint density,the proposed algorithm has excellent time and space performance compared to the existing algorithms.M eanw hile,its upper boundaries are quite closed to the exact values.

关 键 词：工作流 授权 互斥约束 资源分配 可满足性 模型计数 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]