| *WS-RI增量模式回溯的边界收缩加速 |
| |
| 引用本文： | 翟治年,卢亚辉,周武杰,彭艳斌,郑志军,俞坚,丰明坤.*WS-RI增量模式回溯的边界收缩加速[J].计算机工程与应用,2020,56(24):236-241. |
| |
| 作者姓名： | 翟治年 卢亚辉 周武杰 彭艳斌 郑志军 俞坚 丰明坤 |
| |
| 作者单位： | 1.浙江科技学院 信息与电子工程学院，杭州 310023
2.深圳大学 计算机与软件学院，广东 深圳 518060
3.浙江大学 信息与电子工程学院，杭州 310027 |
| |
| 基金项目： | 浙江省自然科学基金;浙江省公益计划;国家自然科学基金;浙江省教育厅科研项目;浙江省重点研发计划 |
| |
| 摘 要： | 资源独立约束工作流可满足决策*WS-RI是业务安全规划的典型问题，在云制造等第三方资源环境中有重要意义。增量模式回溯法（Incremental Pattern Backtracking，IPB）是一种能够打破对称，高效求解*WS-RI的新型算法。它的一个主要优势是在模式验证时，通过渐进方式计算其中各块到资源集的指派图。但其在整个资源集中搜索指派邻点，实际性能存在缺陷，并在模式空间上放大。利用块中各步骤授权资源的分布间隙，设计了一种边界收缩的加速方法。它在搜索过程中增量计算邻域的初始边界，循环对齐和滑动当前边界，过滤无用资源，快速求出各个邻点。随机实例集上的实验表明，该算法显著优于目前最快的非增量模式回溯法。而较现有IPB，对低授权或高资源比例的相对困难实例，时间性能有明显提高。
|
| 关 键 词： | 资源独立约束 打破对称 模式 匹配 |
Acceleration of Boundary Shrinking in Incremental Pattern Backtracking for *WS-RI |
| |
| ZHAI Zhinian,LU Yahui,ZHOU Wujie,PENG Yanbin,ZHENG Zhijun,YU Jian,FENG Mingkun.Acceleration of Boundary Shrinking in Incremental Pattern Backtracking for *WS-RI[J].Computer Engineering and Applications,2020,56(24):236-241. |
| |
| Authors: | ZHAI Zhinian LU Yahui ZHOU Wujie PENG Yanbin ZHENG Zhijun YU Jian FENG Mingkun |
| |
| Affiliation: | 1.School of Information and Electronic Engineering, Zhejiang University of Science and Technology, Hangzhou 310023, China
2.School of Computer and Software, Shenzhen University, Shenzhen, Guangdong 518060, China
3.School of Information and Electronic Engineering, Zhejiang University, Hangzhou 310027, China |
| |
| Abstract: | Workflow Satisfiability decision with Resource Independent constraints（*WS-RI） is an essential issue for the planning of business security, which has important meaning in the environments of the third-party resources, such as cloud manufacturing. Incremental Pattern Backtracking（IPB） is a new type of algorithm which can efficiently solve *WS-RI with symmetries broken. As one of its main advantages, when validating a pattern, it incrementally computes the bipartite graph which assigns resources to the pattern’s blocks. But its practical performance is defective in that any assigning neighbor is searched from the whole resource set, as will be amplified on the pattern space. In this paper, by exploiting the gaps among the authorized resources of each step in a block, an accelerating method of boundary shrinking is designed. It incrementally computes the initial boundary of a neighborhood in the searching process, in turn aligns and moves the current boundary. Thus, it can filter out useless resources and quickly find the neighbors. Experiments on the randomly generated instances show that the proposed algorithm is significantly better than the present fastest non-incremental PB. Compared to the present IPB, on the harder instances under conditions of low authorizing proportion or high resource proportion, the proposed algorithm has achieved obvious improvement subject to time performance. |
| |
| Keywords: | resource independent constraints symmetry breaking pattern matching |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
|
