| 摘要: |
| 研究了可用于求解约束满足问题的最大受限路径相容算法(maxRPC).maxRPC算法执行过程中有大量无效的寻找路径相容证明(PC-witness)的操作,有效地识别和避免这些无效的寻找PC-witness的操作,可以提高maxRPC算法的求解效率.首先,提出了在一条约束上任意两个相容的值在任意路径上存在PC-witness的概率;然后,基于这一概率提出了一种概率最大受限路径相容算法(PmaxRPC),并将新算法成功应用于求解约束满足问题的回溯搜索.实验结果显示:PmaxRPC可以避免一部分无效的寻找PC-witness的操作,在求解约束满足问题时,PmaxRPC效率高于maxRPC.在某些测试用例上,PmaxRPC比maxRPC和最流行的弧相容算法效率更高. |
| 关键词: 约束满足问题 局部相容 最大受限路径相容 概率最大受限路径相容 |
| DOI：10.13328/j.cnki.jos.004815 |
| 分类号: |
| 基金项目:国家自然科学基金(61272207) |
|
| Probabilistic Max Restricted Path Consistency |
|
LI Hong-Bo1,2, LIANG Yan-Chun1,2, LI Zhan-Shan1,2
|
|
1.College of Computer Science and Technology, Jilin University, Changchun 130012, China;2.Key Laboratory of Symbolic Computation and Knowledge Engineering for Ministry of Education(Jilin University), Changchun 130012, China
|
| Abstract: |
| Constraint satisfaction problem is widely applied in many areas of artificial intelligence. This study investigates the max restricted path consistency(maxRPC) which is used to solve constraint satisfaction problems. There are a number of useless operations to search for PC-witness in maxRPC. The efficiency of maxRPC can be improved by identifying and avoiding such operations. The paper first proposes the probability that on a constraint, a PC-witness exists for any two consistent values on a path. Based on the probability, it presents a probabilistic max restricted path consistency(PmaxRPC) and integrates it into backtracking search to solve constraint satisfaction problems. Experimental results show that PmaxRPC avoids some of these useless operations to search for PC-witness and it is more efficient than maxRPC when used in backtracking search. On some benchmark instances, PmaxRPC outperforms both maxRPC and Arc Consistency which is the most popular local consistency used in search. |
| Key words: constraint satisfaction problem local consistency max restricted path consistency probabilistic max restricted path consistency |
