Problem 5.3 (Finite CSPs in Prolog)

Master / Vertiefung Künstliche Intelligenz
1

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.

2

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

3

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.

4

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!

5

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.

6

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!