CSP Ordering
Ordering heuristics improve CSP search efficiency by deciding which variable to assign next and which value to try first. Instead of blindly picking, good ordering strategies reduce the chances of dead-ends and cut down on backtracking using two broad principles:
- Minimum Remaining Values (MRV) chooses the most constrained variable to assign next.
⠀- Least Constraining Value (LCV) selects the value for the chosen variable that rules out the fewest possibilities in the domains of its neighboring variables, preserving the most flexibility for future assignments.
A CSP’s structure can be further exploited to reduce complexity by identifying special graph properties:
- Tree-structured CSPs can be solved in polynomial time as follows:
1.