Forward Checking and ARC Consistency.. Now for Rao's version

Looks like the confusions are begetting more confusions in the FC/AC discussion. Let me stop the buck...

Terminology: If you have n variables x1...xn; and if you have assigned x1,x2...xi-1; and are about to assign xi,
then current variable: xi  ; past variables: x1...xi-1  ; future variables xi+1....xn

Forward checking:

The idea: For each *future* variable, remove from its domain any values that are conflicting with the assignments you have done  until now (i.e., past variables and current variable).

In the special case of binary CSPs, notice that the only way a value can be deleted from the domain of the future variable is if it conflicts with the assignments made to the current variable.

In the case of n-ary CSPs, it is possible that the current variable's assignment along with some of the past variable assignments will rule out a value from the future variable's domain.
(e.g. suppose we have a constraint  x1=a& x4=b => x9 !=c ; so if x1 is a past variable and was assigned a; and x4 is the current variable and got assigned b, we can remove c from the domain of x9)


ARC Consistnency:


 The idea: Make sure that for every variable, xi; and every other variable xj (different from xi), for every value that
  xi can take, there is a value that xj can take without conflicting with xi.
 
So, if you find that when xi takes a, xj cannot take *any value*, then you *remove* a from the domain of xi. In this sense of  "pruning values from domains" ARC Consistency is similar to Forward checking.

 However, unlike FC, which is with respect to a given search branch--with past, current and future variables, Arc Consistency is a *preproessing technique* and does not differentiate between past/current/future variables)


It is easy to see that if you have a binary CSP and you already ensured ARC consistency on it, then doing Forward checking will not remove any more values--no matter in what order you wind up assigning variables.


hope this helps
Rao


ps: So is sudoku a binary CSP or not?

-----------------

  "My student came to me with a desire to know the time, and
    I taught her how to make a watch"
 
                                -Chris in the morning (Northern Exposure)

Regarding Forward Checking and Arc Consistency

Since so many students asked questions about Forward Checking and Arc Consistency today,
I think it is necessary to make sure everyone are on the same boat. Let me try to clarify, correct me if
I am wrong:

Forward Checking:
Keep a list of all possible values for each unassigned variables, every time before assigning a value to a variable,
check whether that value is the only possible value for neighbor variables (Don't permanently delete that
value from neighbor's possible value), if none of them is the case, make the assignment, and update the possible
values for other variables (Now you can delete the value just assigned). And keep going.

Arc Consistency:
Keep all possible values for unassigned variables, and propagate constraints to each of the variable.
Remove any possible value that has no support from neighbors, and check all variables each round.
End if no value was removed in one round. (For one round, I mean update all variables) 


--
Meng,Yunsong
Teaching Assistant

regarding second project deadline

Dear all:

 Apparently CSE 471 student-body is turning into a veritable California electorate with voter-sponsored initiatives aimed at the evil deadlines.. I wish people divert part of this enthusiasm to blog-participation on thinking cap questions..

Anyways, while the blog makes it sound as if there is uniform and vocal support for deadline change, I have also received direct mails asking that the deadline *not be shifted* since the students in question have worked their schedules around to get done with the project.

To be fair to people who have completed their work as well as allow a little more time to those who want to complete the project, I will take the project until Tuesday with a 20% late penalty. (Please resist the temptation to ask us questions such as "Can reduce my penalty to 5pi% if I turn in the project only pi days late")

regards
Rao

MRV and forward checking

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.

Re: Statistics of homework 2 and project 1

Homework 2 

  total: 100

               min            max         average      
Grad:       41              96            75.9           
Under:      41              91            69.5


Project 1 without extra points

  total: 50

               min            max         average
Grad:       40              50            45.9
Under:     15               50            40.8


Project 1 with extra points

  total: 63
               min            max         average
Grad:       42              60             51
Under:     15               61            42.4


--
Meng,Yunsong
Teaching Assistant
Department of Computer Science and Engineering
School of Computing & Informatics
Arizona State University

Statistics of homework 2 and project 1

Homework 2 

  total: 100

               min            max         average      
Grad:       41              96            75.9           
Under:      41              91            69.5


Project 1 without extra points

  total: 50

               min            max         average
Grad:       40              50            45.9
Under:     15               50            40.8


Project 1 extra points

  total: 63
               min            max         average
Grad:       42              60            51
Under:     15               61            42.4


--
Meng,Yunsong
Teaching Assistant
Department of Computer Science and Engineering
School of Computing & Informatics
Arizona State University

CSE471/598 TA office hours update

A reminder, I will have office hour on Wednesday for project 2, 2:00PM-3:00PM.

--
Meng,Yunsong
Teaching Assistant
Department of Computer Science and Engineering
School of Computing & Informatics
Arizona State University