Calcul de la fermeture avec filtrage à la volée

Dans leur étude du problème de conformation moléculaire, Crippen et Havel [4], utilisent une méthode nommée bound-smoothing qui réalise cette opération de fermeture. Pour chaque arète du graphe, l'algorithme parcours tous les triangles du graphe contenant cette arète, en mettant à jour les bornes du domaine de sa longueur. C'est une modification de l'algorithme du plus court chemin pour tout couple de sommets de Floyd qui a une complexité en temps de $\Theta(n^3)$. Une preuve et une analyse de cet algorithme se trouve dans le livre de Cormen, Leiserson et Rivest [18].

Notre idée est d'incorporer au traitement d'une arète, le filtrage des coordonnées de ses extrémités, en projetant simplement chacun des domaines sur la contrainte liée à cette arête. L'algorithme ci-dessous réalise cette opération de fermeture en filtrant à la volée les domaines des variables. L'opération de projection se faisant en temps linéaire de la dimension de l'espace de travail, $\Theta(p)$), l'algorithme de fermeture-filtrage a une complexité en temps de $\Theta(pn^3)$.

Algorithme abstrait :
procedure CLOSE-FILTER( $\mathcal{I}=(\mathcal{P},\:\mathcal{D},\:\Delta)$ )
pour k $\rightarrow$ 1 à $n$ faire
pour j $\rightarrow$ 1 à $n$ faire
pour i $\rightarrow$ 1 à $n$ faire
si $u_{ij} > u_{ik} + u_{jk}$ alors $u_{ij} = u_{ik} + u_{jk}$
si $l_{ij} < l_{ik} - u_{jk}$ alors $l_{ij} = l_{ik} - u_{jk}$
sinon si $l_{ij} < l_{jk} - u_{ik}$ alors $l_{ij} = l_{jk} - u_{ik}$
si $l_{ij} > u_{ij}$ alors Erreur
FILTER-DOMAINS($C_{ij}$)
finpour
finpour
finpour
retourner $\mathcal{I}$

La fonction FILTER-DOMAINS($C_{ij}$) utilise la contrainte $C_{ij}$ de la forme :
$\sum_{l=1}^{l=p}{({x_i}^l-{x_j}^l)^2} = \delta_{ij}$ pour les filtrer les domaines des coordonnées des points $P_i$ et $P_j$ en faisant une projection des domaines :

$$\forall l \in \llbracket 1, p \rrbracket, \: {D'}_{x_i^l} = D_{x_... ...j^l} \pm \sqrt{ \sum_{k=1,k \neq l}^{k=p}{(D_{x_i^k}-D_{x_j^k})^2}} \: \right)$$

La dimension de l'espace de travail étant en général très petit pour de nombreuses applications, on peut considérer que le filtrage des domaines est en temps constant.