互斥约束工作流可满足性决策的匹配剪枝模式回溯法

摘要

针对用于工作流可满足决策的模式回溯技术如何平衡性能与代价的问题,提出了一种对部分模式解及时进行授权匹配验证的优化方法,牺牲一定验证效率以增强剪枝能力.就仅受互斥约束的问题情形,利用实例难易程度的两极分化现象对总体时间性能进行了分析.随机生成数据集上的实验表明,这一优化极大地降低了模式回溯在难实例上的时间代价,而对易实例执行时间的影响很小,且相对于其他基于动态规划的代表性算法,优化后的算法在时间和空间性能上均有显著优势.