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

来源：计算机科学与探索杂志2018年第12期北京时间：

作者：翟治年，卢亚辉，余法红，高慧敏

单位：1. 浙江科技学院 信息与电子工程学院，杭州 3100232. 深圳大学 计算机与软件学院，广东 深圳 5180603. 嘉兴学院 数理与信息工程学院，浙江 嘉兴 3140014. 嘉兴学院 机电工程学院，浙江 嘉兴 314001

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

关键词：工作流,访问控制,资源分配,约束满足