I have been struggling with understanding this program, and I have an
issue that I need clarified:
D
1 0 0 1
0 1 0 1
1 0 1 0
1 1 0 0
c1
1 0 1 0
1 1 1 0
1 1 1 0
1 0 0 0
X
0 0 0 0
0 0 0 1
0 0 0 0
0 2 0 0
Here, I am thinking that an arc consistent result can only have 1
values in half of the rows of D. But ac gives me 1 values in all of
the rows of D.
Also, consider this case:
D
0 1 1 0
1 0 1 0
0 0 1 1
0 1 0 1
c1
1 0 1 1
1 0 1 1
1 0 0 1
0 1 1 0
X
0 0 1 1
0 0 1 0
2 2 0 0
2 0 0 0
Here, ac gives me:
0 1 1 0
0 0 1 0
0 0 0 1
0 1 0 1
But I think the result should be
0 1 1 0
1 0 1 0
0 0 1 1
0 1 0 1
The difference is in the "0" value in the second row and the "2" value
in the third row.
If I understand the algorithm properly: according to X, relationships
are considered between the third row and either the first or second
row. And, according to c1, 0 comp 2 is valid.
In other words, I think this might be a valid implementation of arc consistency:
arcn=:3 :0
'D c1 X'=: y
X1=. 1=X
([:+./"1[: +./((|:c1) *"1 2~ (|:X1) *"1 2 ]) +. c1 *"1 2~ X1 *"1 2 ])^:_ D
)
for reference, here's my "workalike" cover for ac (except, of course,
the results are not the same):
arccon=:3 :0
'D c1 X'=: y
'n d'=: $D
adj =: ((<@#)&(i.n)) @ (0&<)
A =: adj X
ac =: > @ (1&{) @ (revise^:_) @ ((i.n)&;)
ac D
)
I do not want to concern myself with efficiency issues until after I
am sure I understand the algorithm properly. (But making c1 and X
sparse might be appropriate, in some contexts.)
If I have made a mistake here, I'd greatly appreciate an explanation
of where I went wrong.
Thanks,
--
Raul
On Fri, Nov 2, 2012 at 1:01 AM, Michal D. <[email protected]> wrote:
> Hi All,
>
> I've managed to write my first not-completely-trivial program in J. It
> implements an arc consistency algorithm (
> http://en.wikipedia.org/wiki/Local_consistency#Arc_consistency). I would
> appreciate any comments regarding style, what I'm doing wrong in J or how
> to improve the code. I also have a couple of questions of my own:
>
> 1) how do I avoid @ especially once we remove explicit arguments?
> 2) how do I avoid constant boxing/unboxing due to fill (see arcsX)?
> 3) Is a boxed value always a pointer? One could imagine implementing
> 'ragged' arrays without pointers.
> 4) Is there a good way to have named variables (ie. avoid getx, gety)?
> 5) Why is a hook the default and not composition?
>
> Code at: http://pastebin.com/k4XuKfFi
>
> Cheers!
>
> Mike
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
