1 \documentclass[a4paper, 10pt, pagesize, smallheadings]{article}
3 %\usepackage[latin1]{inputenc}
4 \usepackage{amsmath, amsthm, amssymb}
7 \usepackage{algorithmic}
12 \usepackage{tikz-qtree}
13 \usetikzlibrary{decorations.pathmorphing} % noisy shapes
14 \usetikzlibrary{fit} % fitting shapes to coordinates
15 \usetikzlibrary{backgrounds} % drawin
16 \usetikzlibrary{shapes,snakes}
17 \addtolength{\voffset}{-20pt}
18 \title{CSP Exercise 05 Solution}
20 \renewcommand{\familydefault}{\sfdefault}
21 \newcommand{\R}{\mathcal{R}}
22 \newcommand{\N}{\mathbb{N}}
23 \newcommand{\C}{\mathcal{C}}
24 \newcommand{\bo}{\mathcal{O}}
26 %\include{pythonlisting}
32 \section*{Exercise 5.1}
33 (a) The following table shows the states during the AC3 iterations.\\\\
34 \begin{tabular}{r l l l}
35 Iteration & Queue & Revise & Domains\\\hline\\
36 $0$ & $\{(v_1,v_2),(v_2,v_1),
38 (v_1,v_3),(v_3,v_1)\}$
43 $1$ & $\{(v_1,v_2),(v_2,v_1),
50 $2$ & $\{(v_1,v_2),(v_2,v_1),
57 $3$ & $\{(v_1,v_2),(v_2,v_1),
58 (v_2,v_3)\}\cup\{(v_1,v_3)\}$
63 $4$ & $\{(v_1,v_2),(v_2,v_1),
69 $5$ & $\{(v_1,v_2),(v_2,v_1)\}$
85 (b) The following table shows the states during the PC2 iterations.\\\\
86 \begin{tabular}{r l l l l l}
87 Iteration & Queue & Revise-3 & $R_{v_1,v_2}$ & $R_{v_2,v_3}$ & $R_{v_1,v_3}$\\
89 $0$ & $\{(1,3,2),(1,2,3),(2,1,3)\}$
92 & $\{(1,1),(1,2),(2,1)\}$
93 & $\{(1,1),(1,2),(1,3),$\\
94 &&&&& $(1,4),(1,5),(2,2),$\\
95 &&&&& $(2,3),(2,4),(2,5),$\\
96 &&&&& $(3,3),(3,4),(3,5),$\\
97 &&&&& $(4,4),(4,5),(5,5)\}$\\
98 $1$ & $\{(1,3,2),(1,2,3)\}$
101 & $\{(1,1),(1,2),(2,1)\}$
102 & $\{(1,1),(1,2),(1,3),$\\
103 &&&&& $(1,4),(1,5),(2,2),$\\
104 &&&&& $(2,3),(2,4),(2,5),$\\
105 &&&&& $(3,3),(3,4),(3,5),$\\
106 &&&&& $(4,4),(4,5),(5,5)\}$\\
108 & $(\{v_1,v_2\},v_3)$
110 & $\{(1,1),(1,2),(2,1)\}$
111 & $\{(1,1),(1,2),(1,3),$\\
112 &&&&& $(1,4),(1,5),(2,2),$\\
113 &&&&& $(2,3),(2,4),(2,5),$\\
114 &&&&& $(3,3),(3,4),(3,5),$\\
115 &&&&& $(4,4),(4,5),(5,5)\}$\\
116 $3$ & $\{\}\cup\{(2,1,3),(2,3,1)\}$
117 & $(\{v_1,v_3\},v_2)$
119 & $\{(1,1),(1,2),(2,1)\}$
120 & $\{(1,1),(2,2)\}$\\
121 $4$ & $\{(2,1,3)\}\cup\{(1,2,3),(1,3,2)\}$
122 & $(\{v_2,v_3\},v_1)$
125 & $\{(1,1),(2,2)\}$\\
126 $5$ & $\{(2,1,3),(1,2,3)\}$
127 & $(\{v_1,v_3\},v_2)$
130 & $\{(1,1),(2,2)\}$\\
132 & $(\{v_1,v_2\},v_3)$
135 & $\{(1,1),(2,2)\}$\\
137 & $(\{v_2,v_1\},v_3)$
143 \section*{Exercise 5.3}
144 (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}$.
146 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\\\\
147 (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$.
149 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\\\\
150 (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$.
152 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