FranconiSpace

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Solutions to the CSP lab ======

===== 4.2 =====

==== (a) ====
 Yes it is arc consistent, as there are vowels in the 1st, 3rd and 5th positions in the words.
==== (b) ====
 //fever// can be removed from W as there is no vowel in the 1st, 3rd or 5th position of the word //fever//.

===== 4.3 =====

==== (a) ====
See [[https://www.cs.ubc.ca/~poole/aibook/figures/ch04/cross2cn.xml|https://www.cs.ubc.ca/~poole/aibook/figures/ch04/cross2cn.xml]] for a representation in the applet.
See [[https://www.cs.ubc.ca/~poole/aibook/figures/ch04/cross2ac.xml|https://www.cs.ubc.ca/~poole/aibook/figures/ch04/cross2ac.xml]] for a representation in the applet of the arc consistent network.

==== (b) ====
Number the squares on the intersections of words s1-s9 (s1 is the square with a 1 in it, s2 has a 2 in it and s8 has a 6 in it). The arc consistent form has:
<code>s1: h,s,t 
s2: e,h,o 
s3: a,h,o 
s4: e,n,t 
s5: i,s,u 
s6: a,e,r 
s7: g,l,s 
s8: d,e,k 
s9: n,s,v</code>

==== (c) ====

Let's ﬁrst eliminate 1a: We get the constraint on //<1d, 2d>// with the elements {//<haste, eta>, <sound, one>, <think, her>//}. 

Eliminate 3a, gives the relation on //<1d, 2d>// with elements: {//<haste, eta>, <sound, one>, <think, her>//}. These combine to the same relation on //<1d, 2d>//.

We can now eliminate 2d, which creates a relation on //<1d, 4a>// with domain {//<haste, usage>, <sound, fuels>, <think, ﬁrst>//}. Again this provides no more constraints than the previous relation on //<1d, 4a>//.

We can now eliminate 1d and create a relation on //<6a, 4a>// with domain: {//<easy, usage>, <else, usage>, <desk, fuels>//}. 

If we eliminate 5d, we create a relation on //<6a, 4a>// with domain: {//<desk, fuels>, <easy, fuels>, <else, fuels>, <kind, first>//}. 

These last two can be combined giving their intersection: {//<desk, fuels>, <kind, ﬁrst>//}. 

This is then only relation left and there are two solutions on //<6a, 4a>//. Each of these gives rise to a unique solution.

==== (d) ====
If you eliminate 1d (or 4a) ﬁrst, you create a relation on 3 variables which is much more complicated and less efﬁcient. So that elimination ordering does affect efﬁciency.

===== 4.5 =====

==== (a) ====
There is a solution tree based on the variable ordering //C, D, A, B, E// at [[https://www.cs.ubc.ca/~poole/aibook/figures/ch04/schedSearchTree.txt|https://www.cs.ubc.ca/~poole/aibook/figures/ch04/schedSearchTree.txt]]

==== (b) ====

  * Initial constraint graph: {{:teaching:is:csp-lab-solution-graph-before.png?400|initial constraint graph}}
  * Arc consistent graph: {{:teaching:is:csp-lab-solution-graph-after.png?400|arc consistent graph}}

==== (c) ====

You can try to split the domain of D. There are two cases, D = 2 and D = 3.
FranconiSpace

User Tools

Site Tools

Page Tools
