Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

**Problem 5.3 (Finite CSPs in Prolog)**

Hello.

The description of arcconsOne() says:

arcconsOne(Ds,Ls,Cs,I,J) holds if x_I is arc−consistent relative to x_J

i.e., for every value for x_I from L_I there is a value for x_J from L_J

such that C_IJ (if present) is satisfied

If this predicate just checks arc-consistency of x_I relative to x_J using the values in Ls (assuming that Ls is given when calling this predicate), then passing Ds would be useless here. Or do i miss anything ?

Thanks in advance

EDIT: this has already been answered in the exercise session: yes it could be possible, that Ds is useless for the implementation

Hello

we had the same concern regarding the ‘Ds’. What we therefore implemented was to check if Ls is a subset of the corresponding Ds. This enables us to use the function in reverse and generate an arcconsistent Ls. However it was not necessary for the Implementation.

Hi matze,

thanks for your input. If i got it right, you used Ds in the first place to generate arccons Ls, but not anymore now. Is that correct ?

My implementation disclaims Ds completely now, assuming that Ls is given when calling arccons/arcconsAll… That is maybe also the reason why i can’t use these two for makeArccons, where i let Ls be initialized with Ds with all values possible in an extra predicate.

EDIT: Therefore one have to find a inital state that is consistent, meaning that any variable has to be assigned with a possible value, otherwise revise won’t delete any values as it finds always a legit constraint in the loop… Looking forward for your answers!

Indeed. I made the stubs such that the whole problem is passed around even if not every part of it is needed in every method.

Hi Bsanchez,

your interpretation of our code is partially correct. In the normal usage of the function, we assume that Ls (& Ds) is present. We then check if Ls is a subset of D (e.g. (1,3) e (1,2,3)). This does not add any functionality in this usage of the function. However, when using the function with a variable Ls, Prolog can try & error any possible subset combination of D if it is arcconsistent. The flow is therefore more dumb than the original AC-1/3 algorithm. But as florian already pointed out, it was not necessary.

Greetings!