sasgwb@mozart.unx.sas.com (Gary Black) (07/03/90)
I've seen most of the good algorithms for arc consistency (AC1, AC2, AC3, AC4, etc.) and they all are presented in examples using ONLY BINARY CONSTRAINTS. On n-ary constraints, these algorithms seem to rapidly get prohibitively expensive. My question is: Is anyone aware of AC algorithms which can handle hyperarcs? For example, given a constraint net with 3 nodes, A, B, and C, and a constraint A + B = C, how do we perform AC on this net without looking at the power set of the domains of A, B and C? Is it even possible? Thanks in advance for any helpful comments. Gary
miron@fornax.UUCP (Miron Cuperman) (07/06/90)
I have implemented k-ary arc consistency. I think there are several references out there. The expense is proportional to the cross product of the sets and not to the power set of course. Real intervals also work with k-ary arc consistency, and may be quite a bit faster for domains which require precision (which when expressed in discrete sets make the sets very large). -- By me: Miron Cuperman <miron@cs.sfu.ca> [if you use 'reply' check that the address the mailer uses is correct.] The long habit of living indisposeth us for dying. - Sir Thomas Browne