Définitions et notations

Un problème de satisfaction de contraintes est la donnée d'un ensemble de variables, un ensemble de domaines associés à chacune de ces variables et d'un ensemble de contraintes, qui expriment des relations entre elles. La résolution d'un CSP(Constraint Solving Problem) consiste à filtrer au mieux les domaines des variables afin d'en extraire les valeurs qui ne peuvent valider tout ou partie de l'ensemble du système de contraintes.

Définition 1.1 (Constraint Solving Problem(CSP)[1])   Un $\mathcal{CSP}$ est un triplet $(\mathcal{X,D,C})$ tel que :

• $\mathcal{X}=\{x_1,\ldots,x_n\}$ est un ensemble de variables.
• $\mathcal{D}=\{D_{x_1},\ldots,D_{x_n}\}$ est un ensemble de domaines. ($D_{x_i}$ est le domaine contenantr toutes les valeurs potentielles de la variable $x_i$).
• $\mathcal{C}=\{c_1,\ldots,c_m\}$ est un ensemble de contraintes.

On note $Var(c)$ le sous-ensemble de $\mathcal{X}$ des variables de $c$.

Plus formellement, on peut définir une instance d'un problème de satisfaction de contraintes de distances de la manière suivante :

Définition 1.2 ( $\mathcal{DCSP}$)   Une instance $\mathcal{I}=(\mathcal{P},\:\mathcal{D},\:\Delta)$ d'un problème de satisfaction de contraintes de distances est la donnée de :

• $\mathcal{P}=\{P_i(\:x_{1}^{i},\:x_{2}^{i},\:\ldots\:,\:x_{p}^{i}\:)\}_{1 \leq i \leq n}$ un ensemble de $n$ points de $\mathbb{R}^p$, de dimension finie $p$.
• $\mathcal{D}=\{\:D_{1}^{i},\:D_{2}^{i},\:\ldots\:,\:D_{p}^{i}\:\}_{1 \leq i \leq n}$ un ensemble de $n \times p$ domaines associés aux composantes des points et tels que :
  $D_{j}^{i} = [\:\underline{x_{j}^{i}},\:\overline{x_{j}^{i}}]$ $\forall\:(i,j) :\:1 \leq i \leq n,\:1 \leq j \leq p$
• $\Delta = {\{\Delta_{k}\}}_{1 \leq k \leq m}$ un ensemble de $m$ domaines associés aux distances euclidiennes $\delta_{i_kj_k}$ entre les points $P_{i_k}$ et $P_{j_k}$ et tels que :
  $\Delta_k = [\:{l_{i_kj_k},\:u_{i_kj_k}}\:]$ $\forall\:k:\:1 \leq k \leq m$
  $\sum_{l=1}^{p}{ {(x_{l}^{i_k} - x_{l}^{j_k})}^2 } = {\delta_{i_kj_k}}^2$ $\forall\:k:\:1 \leq k \leq m$

On dira que $\mathcal{I}=(\mathcal{P},\:\mathcal{D},\:\Delta)$ est complète si $m=\frac{n(n-1)}{2}$.

Pour simplifier l'écriture on notera :

• En dimension 2 :
  • $\mathcal{P}=\{P_i(\:x_i,\:y_i\:)\}_{1 \leq i \leq n}$
  • $\mathcal{D}= {\{\:D_{x_i},\:D_{y_i}\}}_{1 \leq i \leq n}$ où $D_{x_i}= [\:\underline{x_{i}},\:\overline{x_{i}}]$ et $D_{y_i}= [\:\underline{y_i},\:\overline{y_i}]$.
• En dimension 3 :
  • $\mathcal{P}=\{P_i(\:x_i,\:y_i\:,\:z_i)\}_{1 \leq i \leq n}$
  • $\mathcal{D}= {\{\:D_{x_i},\:D_{y_i},\:D_{z_i}\}}_{1 \leq i \leq n}$ où $D_{x_i}= [\:\underline{x_{i}},\:\overline{x_{i}}]$, $D_{y_i}= [\:\underline{y_i},\:\overline{y_i}]$ et $D_{z_i}= [\:\underline{z_i},\:\overline{z_i}]$.

On définit également la notion de graphe de distance associé à une instance, dont nous discuterons l'intérêt dans la section 3 :

Définition 1.3 ( $\mathcal{DG}$)   Le graphe de distance $\mathcal{DG}(\mathcal{I})=(V,\:E,\:p)$ associé à un $\mathcal{DCSP} :\mathcal{I}=(\mathcal{P},\:\mathcal{D},\:\Delta)$ est défini par :

• Un ensemble de sommets $V={\{v_i\}}_{1 \leq i \leq n}$, tel que chaque sommet $v_i$ est associé au point $P_i \in \mathcal{P}$
• Un ensemble d'arètes $A$, reliant les couples de points pour lesquels une approximation finie de leur distance respective est connue :
  $A=\{(v_i,\:v_j) \vert \exists k : 1 \leq k \leq m$ et $\Delta_k = [\:l_{ij},\:u_{ij}\:] \in \Delta\}$
• Une fonction de valuation des arètes $p\::\:A \rightarrow \Delta$, retournant l'intervalle de variation de la distance entre les 2 sommets de l'arête. Plus formellement :
  $a=(v_i,v_j) \rightarrow p(a) = [\:l_{ij},\:u_{ij}\:] \in \Delta$