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

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