工作流可满足决策(≠)的完备独立树分解回溯法

• 作者: 余法红 卢亚辉 翟治年 高慧敏
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 工作流 访问控制 资源分配 约束满足
• 年，卷（期）: 2018,（12）
• 所属期刊栏目: 理论与算法
• 页码范围: 2021-2032
• 页数: 12页
• 分类号: TP309
• 字数: 11334字
• 语种: 中文
• DOI: 10.3778/j.issn.1673-9418.1710074

摘要

互斥约束工作流可满足决策是关系到安全业务可行性的重要问题,而其现有算法的理论和实测性能,或时间和空间代价严重失衡.根据其低约束密度特征,利用Jegou的树分解回溯方法来解决上述问题.因该方法仅根据约束不相关性得出子问题独立性,不能保证部分解之间的兼容性,从变量不相交和约束不相关两个角度建立了完备的子问题独立性及其部分解缓存原理,设计了相应的算法,并通过交错归纳的方法证明其正确性.分析表明,该算法时间复杂度为O*(|S|3×dW+1),一定条件下低于目前最优的O*(2|S|(|X|+|U|2))时间,其中S、d、W分别为步骤集、步骤授权列表的最大规模、树分解宽度.实验表明,该算法在低密度约束下,时间性能显著超过现有理论或实际性能最优的算法,且未付出很大空间代价.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	高慧敏	嘉兴学院机电工程学院	28	31	3.0	4.0
2	卢亚辉	深圳大学计算机与软件学院	12	24	3.0	3.0
3	翟治年	浙江科技学院信息与电子工程学院	10	19	2.0	3.0
4	余法红	嘉兴学院数理与信息工程学院	9	17	2.0	3.0