Adaptive Neighborhood Inverse Consistency as Lookahead for Non-Binary CSPs
Woodward, Robert J. (University of Nebraska-Lincoln) | Karakashian, Shant (University of Nebraska-Lincoln) | Choueiry, Berthe Y. (University of Nebraska-Lincoln) | Bessiere, Christian (University of Montpellier)
Freuder and Elfe (1996) introduced Neighborhood Inverse Consistency (NIC) for binary CSPs. In this paper, we introduce RNIC, the extension of NIC to non-binary CSPs, and describe a practical algorithm for enforcing it. We propose an adaptive strategy to weaken or strengthen this property based on the connectivity of the network. We demonstrate the effectiveness of RNIC as a full lookahead strategy during search for solving difficult benchmark problems.
Aug-4-2011