So aren’t MCV and LCV the exact opposite?MCV tries to choose the variable with the most constraints on remaining variables but LCV is opposite: it tries to rule out as least values for other variables as possible

  • $\begingroup$ MCV also doesn't work in finding all solutions of CSP. Read Edward Tsang "Foundations of Constraint Satisfaction" $\endgroup$ – Cecelia Jan 8 '20 at 9:24

Yes, these two heuristics does sound like inconsistent. Most Constrained Variable (MCV) (also called MRV for Minimum Remaining Values) tries to reduce the size of the next branch to search while Least Constraining Values tries to enlarge the size of the next branch to branch.

However, if you take a close a look, they both serve the same goal, which is, given a Constraint Satisfaction Problem (CSP), to find a solution as fast as possible and, if there is no solution, declare that fact as fast as possible.

Firstly, these two heuristics are applied in different stages of the search. MCV is about choosing which variable to assign value to and then, given a variable, LCV is about choosing which value to assign.

Here is a quote from a lecture note on Constraint Satisfaction Problems by Max Welling, slighted edited.

In all stages of the searching for one solution, we want to enter the most promising branch, but we also want to detect inevitable failure sooner.

MCV: the variable that is most likely to cause failure in a branch is assigned first. The variable must be assigned at some point, so if it is doomed to fail, we’d better found out soon.
LCV: tries to avoid failure by assigning values that leave maximal flexibility for the remaining variables. We want our search to succeed as soon as possible, so given some ordering, we want to find the branch that is more likely to succeed.

In term of the search tree, MCV help pruning bigger branches more often and earlier, thus makes the searching end faster, whether it ends with a solution or no solution possible. LCV help make backtracking less often in case there is a solution, but it does not help when there is no solution since every value has to be searched. In other words, if the goal is to find all solutions instead of one solution, then MCV still help effectively while LCV does not help at all.

I would like to use planning a party as an example. The variables are who should attend, when to hold it, where to hold it and how much to spend (why and what is another question). The object is to see if there is a party plan that is viable.

Suppose you are almost running out of money. Then the first thing to check is to set a tight limit on spending. You do not want to plan all the other parts in great beautiful detail only to find there is not enough money to support them later. Then within your budget you want to set a limit as high as possible so that there is more room to make the party plan attractive enough to be held. Note that you are applying the principle of MCV and LCV.

Consider another situation. You are planning a birthday party for one of your friends and you are not so constrained much by the money. Then you probably do not want to consider your budget first. The first thing you want to decide is probably when to hold the party since there are usually not many choices. It is expected usually to be held just before that birthday. Then in order to have most of remaining choices you want to pick a time such as the night on the birthday instead of in the afternoon when many people are still working or having classes. Only in case the night on the birthday does not work, for example because some people cannot attend, will you backtrack to the less likely choice of the afternoon on the birthday. Note again that you are using the approach of MCV and LCV.

We can see that MCV and LCV are working together to enable you to find a viable party plan faster. You can also imagine what might happen if you use the opposite approaches, the approach of least constrained variable first and maximum constraining values first

Although far from rigorous, this example of party planning might aid your conceptual understanding of MCV and LCV working together. (You can also view the example as an application of principles of artificial intelligence to guide our decision making process in real life.)

For more related material, you can check chapter 6, "Constraint Satisfaction Problems" in the leading AI book Artificial Intelligence: A Modern Approach (3rd Edition) by by Stuart Russell and Peter Norvig.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy