National Natural Science Foundation of China (61272207)
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.