 |
|
| Computers Forum Index » Computer - Constraints » Path consistency algorithm... |
|
Page 1 of 1 |
|
| Author |
Message |
| ... |
Posted: Tue Jan 27, 2009 2:03 pm |
|
|
|
Guest
|
Hello,
I am trying to learn about constraints from Foundation of constraint
satisfication
book by tsang whose chapters are available online .
In chapter , the algorithm for PC-1 (path consistency) following
notion is used:
Y^n <--- C ;
Y^k (i,j) <-- Y^k-1 (i,j) AND Y^k-1 (i,k) * Y^k-1 (k,k) * Y^k-1
(k,j) ;
where n is number of total variables , C is a set of binary
constraints, and
k is the k-th variable .
Now lets say Z={A,B,C} ==> variables
C={Cab , Cbc , Cca} be binary constraints
My question is :
What does Y^1 or Y^A represent actually ?
Is it a set like this Y^A = { Caa , Cab , Cac}
I the book it say Y^k (i,j) represents a constraint Ci,j in the set
Y^k .
Thanks |
|
|
| Back to top |
|
|
|
| ... |
Posted: Sat Jan 31, 2009 11:30 am |
|
|
|
Guest
|
On Jan 27, 7:03 pm, vsvika... at (no spam) gmail.com wrote:
Quote: Hello,
I am trying to learn about constraints from Foundation of constraint
satisfication
book by tsang whose chapters are available online .
In chapter , the algorithm for PC-1 (path consistency) following
notion is used:
Y^n <--- C ;
Y^k (i,j) <-- Y^k-1 (i,j) AND Y^k-1 (i,k) * Y^k-1 (k,k) * Y^k-1
(k,j) ;
where n is number of total variables , C is a set of binary
constraints, and
k is the k-th variable .
Now lets say Z={A,B,C} ==> variables
C={Cab , Cbc , Cca} be binary constraints
My question is :
What does Y^1 or Y^A represent actually ?
Is it a set like this Y^A = { Caa , Cab , Cac}
I the book it say Y^k (i,j) represents a constraint Ci,j in the set
Y^k .
Thanks
All right i got it , here what i think it means :
Let S-0 be a set of all constraints i.e C initially
From S-0 we derive S-1 , S-2 , .. , and S-n. All of them sets of
constraints
on same variables as S-0 only the content of there matrix
representation
has changed. |
|
|
| Back to top |
|
|
|
|
|
All times are GMT
The time now is Thu Dec 10, 2009 6:38 pm
|
|