Domain Reduction Algorithm
Vocabulary
- Variable v: something that can have an assignment
- Value x: something that can be assigned
- Domain d: set of all different values
- Constraint c: limit on variable values
With a depth-first search, the domain reduction algorithm goes back up one node when it is unable to comply with a constraint. It reduces the domain of available variables at node n-1 to make sure it will have an unused variable in the next node n.
By considering more variables (propagating to neighboring states in the US map coloring example), the domain can be reduced to a single value at a certain node.
Solving the problem faster
By working on the most constraints nodes first, the algorithm doesn’t have to work back up as much as if it starts with least constraints first.
Obviously, the main constraint of using only a small number of values (colors in the example) is the most limiting one. Being able to increase the number of values can drastically simplify the problem.
In case of uncertainty on the exact number of values, find a range of values that solve the problem (such as in the airplane assignment example).
Resources allocations
- Used most constraints first
- Propagate through domain reduced to single algorithm
- In the absence of definite result, find a narrow range of max values where it doesn’t work, and min values where it does