Probabilistic Max Restricted Path Consistency
Author:
Affiliation:

Clc Number:

Fund Project:

National Natural Science Foundation of China (61272207)

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    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.

    Reference
    Related
    Cited by
Get Citation

李宏博,梁艳春,李占山.概率最大受限路径相容算法.软件学报,2015,26(12):3140-3150

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:August 08,2014
  • Revised:December 07,2014
  • Adopted:
  • Online: December 04,2015
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063