2
$\begingroup$

I am currently studying constraint satisfaction problems and have come across two heuristics for variable selection. The minimum remaining values(MRV) heuristic and the degree heuristic.

The MRV heuristic tells you to choose a variable that has the least legal assignments, while the degree heuristic tells you to choose a variable that has the biggest effect on the remaining unassigned variables.

Can these 2 heuristics for variable selection be used in conjunction with each other? Some books say that degree heuristic can be used as first selection of variables. Which heuristic is better followed after that? The MRV or degree heuristic?

enter image description here

The picture shows the case where degree heuristic is used. If MRV were to be used, then at the 3rd step, the leftmost side of the map would be coloured blue.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.