概率最大受限路径相容算法

研究了可用于求解约束满足问题的最大受限路径相容算法(max RPC).max RPC算法执行过程中有大量无效的寻找路径相容证明(PC-witness)的操作,有效地识别和避免这些无效的寻找PC-witness的操作,可以提高max RPC算法的求解效率.首先,提出了在一条约束上任意两个相容的值在任意路径上存在PC-witness的概率;然后,基于这一概率提出了一种概率最大受限路径相容算法(Pmax RPC),并将新算法成功应用于求解约束满足问题的回溯搜索.实验结果显示:Pmax RPC可以避免一部分无效的寻找PC-witness的操作,在求解约束满足问题时,Pmax RPC效率高于max RPC.在某些测试用例上,Pmax RPC比max RPC和最流行的弧相容算法效率更高.

最大受限路径相容约束传播算法的研究进展

约束传播技术对于约束满足问题的求解性能至关重要。约束传播技术在一个预处理过程中能彻底地移除一些局部不相容值,或者在搜索期间高效地剪枝搜索树。最大受限路径相容算法(max Restricted Path Consistency,maxRPC)是最近提出的一种强相容性约束传播算法,它能够删除更多不相容值,在解决复杂问题中取得了很好的效果。文中对弧相容算法AC和最大受限路径相容算法maxRPC的相关算法AC3,AC3rm,maxRPC1,maxRPC2,maxRPCrm,maxRPC3等及其相关变体分别进行介绍和比较。在Mistral求解器上的实验测试结果验证了各种算法的性能。