> > > I had somehow gotten a different idea of consistency: > for all w in Dy for all v in Dx the relationship v compare w is true >
Ah, ok, that's a little bit too strong (it might remove values that can participate in a solution). I should have said: for all w in Dy, there exists v in Dx such that v compare w is true. But I imagine that that is the point of calling it "arc consistency" > -- each arc is consistent to itself, but need not be consistent with > other arcs? > Yes, the algorithm only propagates information across pairs of variables (a single arc). However, this can trigger other arcs to be reexamined. > So... > > An consistent arc seems to be implemented as a pair of set bits in D > which corresponds to a set bit in A and a set bit in C. (So we > consider all the possible cases and if any of them are true we are > satisfied.) > > Except you have C implemented a s a pair -- a matrix and its > transpose. [That's an optimization for performance, though, and I > feel that that should take back seat to simplicity except where it has > a significant measurable benefit which exceeds its cost (complexity > always has a cost).] > Yes, my goal was to create a simd algorithm for arc consistency. Apart from revDom=: getx *. +./ @ (gety # [) newD=. ax *.//. revLookup"1 arcs everything else is fluff to actually get something semi-useful. The beauty with having the explicit transpose is that we can use a single "or" assembly instruction to merge 32 (or 64) values at once. It would be interesting to see what the minimal algorithm in J would be. > > A matches along the leading D dimension, C matches along the trailing > D dimension. The bit pair in D thus corresponds to a row/column pair > against A as well as against C. > I'm a little lost with this line of thinking. > A tricky part seems to be that the upper triangle of A corresponds to > the forward direction in C (the bit in D that selects a row in A is > also selecting a row in C) while the lower triangle of A corresponds > to the reverse direction in C. But I'm not seeing anything like this > in the text of the wikipedia entry. And, if the diagram on the right > hand side is meant to be an illustration where the constraint is x < y > then it looks like we do not care about the order of the two > variables. In other words, if we specify the constraint x < y it > looks like either x1 < x2 or x2 < x1 is sufficient to satisfy arc > consistency. In other words, i think we should always use the > symmetric closure of the constraint. > Does this sound valid to you? > Unfortunately not. There are no values that can satisfy x1<x2 and x2<x1. If this was the case all csps would have no solutions Cheers, Mike ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
