User:Vineet.karkera/Draft of Interchangeability Algorithm

The concept of interchangeability and interchangeability algorithm Constraint satisfaction problems(CSP's) was first introduced by Eugene Freuder, in the year 1991. The interchangeability algorithm reduces the search space of backtrack search algorithms, thereby improving the efficiency of NP-Complete CSP problems.

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.

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.

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).

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.

Pseudocode

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

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

Complexity Analysis

In the case of neighborhood interchangeable algorithm, if we assign the worst case bound to each loop. Then for n variables, which have at most d values for a variable, then we have a bound of : O(n * d * (n-l) * d) = O(n^2 d^2) .

Similarly, the the complexity analysis of the k-interchangeability algorithm for a worst case O(n^(k-1)), with (k-1)-tuples of variables and d^(k-1), for (k-1)-tuples of values, then the bound is : O(n * d * n^(k-l) * d^(k-1)) = O(n^k d^k).

Example

Example for Interchangeability Algorithm.

The figure shows a simple graph coloring example with colors as vertices, such that no two vertices which are joined by an edge have the same color. The available colors at each vertex are shown. The colors yellow, green, brown, red, blue, pink represent vertex Y and are fully interchangeable by definition. For example, substituting maroon for green in the solution orange|X (orange for X), green|Y will yield another solution.

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.