What exactly is the difference between MRV and forward checking. They seem to be almost the same thing. It seems that forward checking is redundant since MRV will find the variably with the empty domain as soon as it arises and thus fail and begin back tracking.
To me, MRV talks about how to pick the next variable to assign value and forward checking tells when to terminate a search. The first one works every step you picks a variable while the latter is affective only when there is a variable without legal move. Forward checking provides early detection of failure while MRV doesn't.
ReplyDeleteConsider example V1={1}, V2={1} while V1 != V2, according to MRV, it says "pick either of them" while FC says "stop, there is no point keep searching".
FC is just a criteria, you can imagine it being used to look many steps ahead and terminate some branch of search tree before it is actually expanded.
I like to think of FC as an accelerator for MRV. As FC eliminates values from future assignments, future variables domains shrink and they become more restricted, moving them up in the eyes of MRV.
ReplyDeleteIf you had a = {1}, b = {2}, c = {3}, d = {1,2}, alldiff(a,b,c,d), it would take longer using MRV alone (a = 1, b = 2, c = 3, d = Fail), versus FC & MRV (a = 1, b = 2, d = Fail) to determine it's unsatisfiable.
That's a very simplistic illustative example. With bigger problems the improvement can be orders of magnitude.
Thanks you, that really cleared it up
ReplyDelete