Algorithms for CSP

Constraint Satisfaction Problem (约束满足问题) is known as an NP-complete problem. We can’t find a polynomial time algorithm until we can prove P=NP, but we’ve developed some algorithm to accelerate the process to find the solution of CSP.

Algorithm 1: BackTracking

BackTracking is the basic algorithm to solve CSP. In every step, find a valid value to assign to current variable. If a valid value is found, assign it to current variable and go to next step. If there’s no any valid value, back-track to the last variable to assign another value, expect another value of the last variable can lead to success of finding valid value for current variable. A valid value for current variable is a value that is not conflict with any assigned variable.

For example, in the Chart 1, Variable C can’t find valid value, then we back-track to Variable B to change the value, then check Variable C again.

BackTracking is a Depth-First Search algorithm in search-space. Time complexity: O(b^d), when b is the average tightness of constraints, which is the branching factor of the searching tree, and d is the number of variables, the depth of the searching tree.

Algorithm 2: Forward Check

Forward Check sign an invalid value in the search space for future variables when current variable is assigned a valid value. If there’s no any valid value for current variable, back-track to the last variable to assign another value. A valid value for the current variable is a value that is not signed invalid from the assigned variables.

For example, in the Chart 1, Values of Variable C is signed invalid and Values of variable D is signed invalid too because of the assignment of A and B, then we back-track to Variable B to change the value, change the related value of C and D again, then check Variable C again.

Forward Check has the same time complexity as BackTracking, and it’s slower than Backtracking. Because Forward Check exam the same nodes as BackTracking, but waste time to assign future nodes that may never been used. For example, because all the value of Variable C is invalid, it doesn’t matter if values of Variable D are valid or not, but the values are already checked and signed when assign values for Variable A and B.

Algorithm 3: Back Jump

Forward Check is slower than BackTracking, but the idea is good. Actually, if we find all the values of Variable C are invalid because they are conflict with the value of Variable A, then we don’t need to change the value of B to check C again. We can directly jump to another value of Variable A, skip other values of B (under A1 value). After we assigned another valid value for A, we check B1 again. This is the Back Jump algorithm.

Back Jump skipped some nodes, so theoretically it’s faster than BackTracking and Forward Check.

Algorithm 4: Dynamic Backtracking

Dynamic Backtracking’s idea is: When we back jump from C to A, if variable B is not conflict with A, then it’s unnecessary to change B’s value after A is re-assigned. In color-mapping problem, assume we assigned color of E1, E2 cities in east, then assigned color of W1, W2, W3 cities in west and return to assign color for E3, E4, E5 cities in east. When working in east cities E3, E4, E5, we found we have to change color of E2, using Back Jump we will have to change the color of the western cities too; But deploying Dynamic Backtracking algorithm, we can leave W1, W2, W3 alone, since they’re not conflict with any of the east city.

This algorithm is faster than above algorithms, especially for CSPs have many variables.

Continue Reading...