Main Page | Report this Page
Computers Forum Index  »  Computer - Constraints  »  Path consistency algorithm...
Page 1 of 1    

Path consistency algorithm...

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
 
...
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.
 
 
Page 1 of 1    
All times are GMT
The time now is Thu Dec 03, 2009 12:20 pm