Added some solutions.
1.1 --- a/exercises/solutions/sol05.tex Sat Jun 09 23:45:57 2012 +0200
1.2 +++ b/exercises/solutions/sol05.tex Sun Jun 10 05:35:08 2012 +0200
1.3 @@ -30,9 +30,9 @@
1.4 \maketitle
1.5 %
1.6 \section*{Exercise 5.1}
1.7 -(a) The following table shows the states during the iterations.\\\\
1.8 +(a) The following table shows the states during the AC3 iterations.\\\\
1.9 \begin{tabular}{r l l l}
1.10 -Iteration & Queue & Revise & Domains\\\hline
1.11 +Iteration & Queue & Revise & Domains\\\hline\\
1.12 $0$ & $\{(v_1,v_2),(v_2,v_1),
1.13 (v_2,v_3),(v_3,v_2),
1.14 (v_1,v_3),(v_3,v_1)\}$
1.15 @@ -81,5 +81,73 @@
1.16 & $(\{1,2\},
1.17 \{1,2\},
1.18 \{1,2\})$\\
1.19 +\end{tabular}\\\\\\
1.20 +(b) The following table shows the states during the PC2 iterations.\\\\
1.21 +\begin{tabular}{r l l l l l}
1.22 + Iteration & Queue & Revise-3 & $R_{v_1,v_2}$ & $R_{v_2,v_3}$ & $R_{v_1,v_3}$\\
1.23 + \hline\\
1.24 + $0$ & $\{(1,3,2),(1,2,3),(2,1,3)\}$
1.25 + & $ $
1.26 + & $\{(1,2),(2,1)\}$
1.27 + & $\{(1,1),(1,2),(2,1)\}$
1.28 + & $\{(1,1),(1,2),(1,3),$\\
1.29 + &&&&& $(1,4),(1,5),(2,2),$\\
1.30 + &&&&& $(2,3),(2,4),(2,5),$\\
1.31 + &&&&& $(3,3),(3,4),(3,5),$\\
1.32 + &&&&& $(4,4),(4,5),(5,5)\}$\\
1.33 + $1$ & $\{(1,3,2),(1,2,3)\}$
1.34 + & $(\{v_2,v_1\},v_3)$
1.35 + & $\{(1,2),(2,1)\}$
1.36 + & $\{(1,1),(1,2),(2,1)\}$
1.37 + & $\{(1,1),(1,2),(1,3),$\\
1.38 + &&&&& $(1,4),(1,5),(2,2),$\\
1.39 + &&&&& $(2,3),(2,4),(2,5),$\\
1.40 + &&&&& $(3,3),(3,4),(3,5),$\\
1.41 + &&&&& $(4,4),(4,5),(5,5)\}$\\
1.42 + $2$ & $\{(1,3,2)\}$
1.43 + & $(\{v_1,v_2\},v_3)$
1.44 + & $\{(1,2),(2,1)\}$
1.45 + & $\{(1,1),(1,2),(2,1)\}$
1.46 + & $\{(1,1),(1,2),(1,3),$\\
1.47 + &&&&& $(1,4),(1,5),(2,2),$\\
1.48 + &&&&& $(2,3),(2,4),(2,5),$\\
1.49 + &&&&& $(3,3),(3,4),(3,5),$\\
1.50 + &&&&& $(4,4),(4,5),(5,5)\}$\\
1.51 + $3$ & $\{\}\cup\{(2,1,3),(2,3,1)\}$
1.52 + & $(\{v_1,v_3\},v_2)$
1.53 + & $\{(1,2),(2,1)\}$
1.54 + & $\{(1,1),(1,2),(2,1)\}$
1.55 + & $\{(1,1),(2,2)\}$\\
1.56 + $4$ & $\{(2,1,3)\}\cup\{(1,2,3),(1,3,2)\}$
1.57 + & $(\{v_2,v_3\},v_1)$
1.58 + & $\{(1,2),(2,1)\}$
1.59 + & $\{(1,2),(2,1)\}$
1.60 + & $\{(1,1),(2,2)\}$\\
1.61 + $5$ & $\{(2,1,3),(1,2,3)\}$
1.62 + & $(\{v_1,v_3\},v_2)$
1.63 + & $\{(1,2),(2,1)\}$
1.64 + & $\{(1,2),(2,1)\}$
1.65 + & $\{(1,1),(2,2)\}$\\
1.66 + $6$ & $\{(2,1,3)\}$
1.67 + & $(\{v_1,v_2\},v_3)$
1.68 + & $\{(1,2),(2,1)\}$
1.69 + & $\{(1,2),(2,1)\}$
1.70 + & $\{(1,1),(2,2)\}$\\
1.71 + $7$ & $\{\}$
1.72 + & $(\{v_2,v_1\},v_3)$
1.73 + & $\{(1,2),(2,1)\}$
1.74 + & $\{(1,2),(2,1)\}$
1.75 + & $\{(1,1),(2,2)\}$
1.76 \end{tabular}
1.77 +
1.78 +\section*{Exercise 5.3}
1.79 +(a) In a path-consistent network for every pair $(a_i,a_j)\in R_{ij}$, there exists an $a_k\in D_k$, such that $(a_i,a_k)\in R_{ik}$ and $(a_k,a_j)\in R_{kj}$.
1.80 +
1.81 +Since all the $R_{ij}$ are non-empty and all our variables $v_i$ share the same domain values, it follows that all $v_i$ are arc-consistent relative to $v_k$ and all $v_k$ are arc-consistent relative to $v_j$, which induces that all $R_{ij}$ are arc-consistent, since otherwise they would be no $a_i\in D_i$, such that $(a_k,a_i)\in R_{ki}$ and $(a_i,a_j)\in R_{ij}$. \qed\\\\
1.82 +(b) We know that all sets $A_m\subseteq\{0,1\}$ are non-empty, i.e., $1\leq|A_m|\leq2$ for all $1\leq m\leq l$. Therefore it holds that the intersection of two sets $A_q=A_o\cap A_p$ has cardinality $0\leq|A_q|\leq \min\{|A_o|,|A_p|\}\leq 2$.
1.83 +
1.84 +WLOG, we know that $A_q$ becomes the empty set, iff $A_o=\{0\}$ and $A_p=\{1\}$ and any combination of $A_o=\{0,1\}$ and $A_p\subset A_o$ yields the set $A_q=A_p$. Therefore it holds that for $\bigcap_{1\leq m\leq l}{A_m}=\emptyset$ to hold, there must be two sets holding the distinct elements $0$ and $1$ respectively, as has been shown. \qed\\\\
1.85 +(c) We prove by contradiction. Assume that the partial assignment on $v_1,...,v_{k-1}$ can not be extended to $v_k$, i.e., $\bigcap_{2\leq i\leq k-1}{\{a_k\mid (a_i,a_k)\in R_{ik}\}}=\emptyset$. By (b) follows that there must be $2\leq i\neq j\leq k-1$, such that $\{a_k\mid(a_i,a_k)\in R_{ik}\}\cap\{a_k\mid(a_j,a_k)\in R_{jk}\}=\emptyset$.
1.86 +
1.87 +WLOG let $\{a_k\mid(a_i,a_k)\in R_{ik}\}=\{0\}$ and $\{a_k\mid(a_j,a_k)\in R_{jk}\}=\{1\}$. We know that we have non-empty constraints on all variable pairs $R_{ij}$ and there is a consistent assignment $(a_i,a_j)\in R_{ij}$. By our assumption there is an assignement $(a_i,0)\in R_{ik}$ but no $(a_j,0)\in R_{jk}$. This contradicts to the definition of path-consistency, where for every pair $(a_i,a_j)\in R_{ij}$, there exists an $a_k\in D_k$, such that $(a_i,a_k)\in R_{ik}$ and $(a_k,a_j)\in R_{kj}$. Therefore there can not be such an assumption in a path-consistent network with given properties and we can extend the assignment to $v_k$. \qed
1.88 \end{document}