Interchangeability algorithm
 | This article, Interchangeability algorithm, has recently been created via the Articles for creation process. Please check to see if the reviewer has accidentally left this template after accepting the draft and take appropriate action as necessary.
Reviewer tools: Inform author |
The concept of interchangeability and interchangeability algorithm Constraint satisfaction problems(CSP's) was first introduced by Eugene Freuder, in the year 1991. [1] The interchangeability algorithm reduces the search space of backtrack search algorithms, thereby improving the efficiency of NP-Complete CSP problems. [2]
Definitions
- Fully Interchangeable
- A value a for variable v is fully interchangeable with value b if and only if every solution in which v = a remains a solution when b is substituted for a and vice-versa.[3]
- Neighbourhood Interchangeable
- A value a for variable v is neighbourhood interchangeable with value b if and only if for every constraint on v, the values compatible with v = a are exactly those compatible with v = b.[3]
- Fully Substitutable
- A value a for variable v is fully substitutable with value b if and only if every solution in which v = a remains a solution when b is substituted for a (but not necessarily vice-versa).[3]
- Dynamically Interchangeable
- A value a for variable v is dynamically interchangeable for b with respect to a set A of variable assignments if and only if they are fully interchangeable in the subproblem induced by A.[3]
Algorithm
- Neighborhood Interchangeability Algorithm
Finds neighborhood interchangeable values in a CSP. Repeat for each variable:
- Build a discrimination tree by:
- Repeat for each value, v:
- Repeat for each neighboring variable W:
- Repeat for each value w consistent with v:
- Move to if present, construct if not, a node of the discrimination tree corresponding to w|W[3]
- Repeat for each value w consistent with v:
- Repeat for each neighboring variable W:
- K-Interchangeability Algorithm
The algorithm can be used to explicitly find solutions to a constraint satisfaction problem. The algorithm can also be run for k steps as a preprocessor to simplify the subsequent backtrack search.
Finds k-interchangeable values in a CSP. Repeat for each variable:
- Build a discrimination tree by:
- Repeat for each value, v:
- Repeat for each (k-1)-tuple of variables
- Repeat for each (k-1)-tuple of values w, which together with v constitute a solution to the subproblem induced by W:
- Move to if present, construct if not, a node of the discrimination tree corresponding to w|W[3]
- Repeat for each (k-1)-tuple of values w, which together with v constitute a solution to the subproblem induced by W:
- Repeat for each (k-1)-tuple of variables
Complexity Analysis
Applications
In Computer Science, the interchangeability algorithm has been extensively used in the fields of Artificial Intelligence, graph coloring problems, abstraction frame-works and solution adaptation. [3] [4] [5] [6] [7] [8]
Full Dynamic Substitutability by SAT Encoding Steven Prestwich Cork Constraint Computation Centre Department of Computer Science University College, Cork, Ireland http://cse-wiki.unl.edu/wiki/images/3/31/Prestwich-CP2004.pdf
References
- ^ Belaid Benhamou and Mohamed Reda Saidi "Reasoning by dominance in Not-Equals binary constraint networks",Laboratoire des Sciences de l'Information et des Systmes (LSIS),Centre de Mathmatiques et d'Informatique, France.
- ^ Assef Chmeiss and Lakhdar Sais "About Neighborhood Substitutability in CSP's",University of Artrois, France.
- ^ a b c d e f g Freuder, E.C.: Eliminating Interchangeable Values in Constraint Satisfaction Problems. In: In Proc. of AAAI-91, Anaheim, CA (1991) 227–233
- ^ Haselbock, A.: Exploiting Interchangeabilities in Constraint Satisfaction Problems. In Proc. of the 13 th IJCAI (1993) 282–287
- ^ Weigel, R., Faltings, B.: Compiling constraint satisfaction problems. Artificial Intelligence 115 (1999) 257–289
- ^ Choueiry, B.Y.: Abstraction Methods for Resource Allocation. PhD thesis, EPFL PhD Thesis no 1292 (1994)
- ^ Weigel, R., Faltings, B.: Interchangeability for Case Adaptation in Configura- tion Problems. In Proceedings of the AAAI98 Spring Symposium on Multimodal Reasoning, Stanford, CA, TR SS-98-04. (1998)
- ^ Neagu, N., Faltings, B.: Exploiting Interchangeabilities for Case Adaptation. In Proc. of the 4th ICCBR01 (2001)