Constraint Satisfaction problemsConstraint 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. |
Got a thought to share or found a
bug in the code?
We'd love to hear from you:
Name: | |
Email: | (Your email is not shared with anybody) |
Comment: |
Facebook comments: