Constraint Satisfaction problems
Constraint Satisfaction problems (CSPs) are problems where:
For example: consider the case of finding all permutations of a string.
CSPs are solved by backtracking -
Two things need to be kept in mind here.
MCV: Most constrained variable
When assigning values to variables, always choose that variable which has minimum number of values left in its set.
LCV: Least constrained value
When assigning values to a variable, always choose a value which will cause minimum constraint to the system.
The reason for MCV is that all variables must be assigned a value sooner or later.
So its best to assign a value to a variable which is most constrained so that chances of it falling into no-values-left trap are minimized.
The reason for LCV is exactly opposite that of MCV i.e. all values in a variable's set need not be analyzed to find a solution.
So its best to choose those values from the set which will allow others maximum chances of survival.
|Email:||(Your email is not shared with anybody)|