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

• 作者: 李占山 李宏博 梁艳春
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 约束满足问题 局部相容 最大受限路径相容 概率最大受限路径相容
• 年，卷（期）: 2015,（12）
• 所属期刊栏目: 模式识别与人工智能
• 页码范围: 3140-3150
• 页数: 11页
• 分类号: TP18
• 字数: 8755字
• 语种: 中文
• DOI: 10.13328/j.cnki.jos.004815

摘要

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