| 概率最大受限路径相容算法 |
| |
| 引用本文： | 李宏博,梁艳春,李占山.概率最大受限路径相容算法[J].软件学报,2015,26(12):3140-3150. |
| |
| 作者姓名： | 李宏博 梁艳春 李占山 |
| |
| 作者单位： | 吉林大学计算机科学与技术学院, 吉林 长春 130012;符号计算与知识工程教育部重点实验室(吉林大学), 吉林 长春 130012,吉林大学计算机科学与技术学院, 吉林 长春 130012;符号计算与知识工程教育部重点实验室(吉林大学), 吉林 长春 130012,吉林大学计算机科学与技术学院, 吉林 长春 130012;符号计算与知识工程教育部重点实验室(吉林大学), 吉林 长春 130012 |
| |
| 基金项目： | 国家自然科学基金(61272207) |
| |
| 摘 要： | 研究了可用于求解约束满足问题的最大受限路径相容算法(maxRPC).maxRPC算法执行过程中有大量无效的寻找路径相容证明(PC-witness)的操作,有效地识别和避免这些无效的寻找PC-witness的操作,可以提高maxRPC算法的求解效率.首先,提出了在一条约束上任意两个相容的值在任意路径上存在PC-witness的概率;然后,基于这一概率提出了一种概率最大受限路径相容算法(PmaxRPC),并将新算法成功应用于求解约束满足问题的回溯搜索.实验结果显示:PmaxRPC可以避免一部分无效的寻找PC-witness的操作,在求解约束满足问题时,PmaxRPC效率高于maxRPC.在某些测试用例上,PmaxRPC比maxRPC和最流行的弧相容算法效率更高.
|
| 关 键 词： | 约束满足问题 局部相容 最大受限路径相容 概率最大受限路径相容 |
| 收稿时间： | 8/8/2014 12:00:00 AM |
| 修稿时间： | 2014/12/7 0:00:00 |
Probabilistic Max Restricted Path Consistency |
| |
| LI Hong-Bo,LIANG Yan-Chun and LI Zhan-Shan.Probabilistic Max Restricted Path Consistency[J].Journal of Software,2015,26(12):3140-3150. |
| |
| Authors: | LI Hong-Bo LIANG Yan-Chun and LI Zhan-Shan |
| |
| Affiliation: | College of Computer Science and Technology, Jilin University, Changchun 130012, China;Key Laboratory of Symbolic Computation and Knowledge Engineering for Ministry of Education(Jilin University), Changchun 130012, China,College of Computer Science and Technology, Jilin University, Changchun 130012, China;Key Laboratory of Symbolic Computation and Knowledge Engineering for Ministry of Education(Jilin University), Changchun 130012, China and College of Computer Science and Technology, Jilin University, Changchun 130012, China;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. |
| |
| Keywords: | constraint satisfaction problem local consistency max restricted path consistency probabilistic max restricted path consistency |
|
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
|
