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

摘要：

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

关键词：约束满足问题、局部相容、最大受限路径相容、概率最大受限路径相容

所属期刊栏目：26

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金61272207 National Natural Science Foundation of China 61272207

在线出版日期：2016-08-19（万方平台首次上网日期，不代表论文的发表时间）

页数：共11页

页码：3140-3150