tag:blogger.com,1999:blog-1872817975428307009.post2258183054414227216..comments2009-05-07T20:40:27.801-07:00Comments on cse471/598 Intro to AI Spring 2009 Blog: MRV and forward checkingSubbarao Kambhampatihttp://www.blogger.com/profile/08449853328445416609noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-1872817975428307009.post-8467250745056180772009-03-17T00:19:00.000-07:002009-03-17T00:19:00.000-07:00Thanks you, that really cleared it upThanks you, that really cleared it upAngelhttps://www.blogger.com/profile/09505827670450123283noreply@blogger.comtag:blogger.com,1999:blog-1872817975428307009.post-75684724380356608642009-03-16T23:34:00.000-07:002009-03-16T23:34:00.000-07:00I like to think of FC as an accelerator for MRV. A...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.<BR/>If 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.<BR/>That's a very simplistic illustative example. With bigger problems the improvement can be orders of magnitude.jmajorshttps://www.blogger.com/profile/02469675915989613659noreply@blogger.comtag:blogger.com,1999:blog-1872817975428307009.post-54094788691379095792009-03-16T22:35:00.000-07:002009-03-16T22:35:00.000-07:00To me, MRV talks about how to pick the next variab...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.<BR/> Consider 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". <BR/> 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.yunsong menghttps://www.blogger.com/profile/16680982537542842676noreply@blogger.com