<![CDATA[
Cas bidirectionnel
On a n capteurs, numérotés de 0 à n-1, dont on connaît la position.
On notera D(i,j) la distance (euclidienne) du capteur i au capteur j.
On notera v(i,r) le capteur de rang r dans la liste des capteurs rangés par éloignement croissant du capteur i,
en notant v(i,0)=i.
On notera d(i,j) = #{k| k≠i, D(i,k)≤D(i,j)} le nombre de capteurs atteints par i
quand il émet assez fort pour atteindre juste le capteur j. C'est le numéro d'un rayon d'émission possible de i.
Cela représente aussi la distance de i à j.
On notera C(i,j) le coût d'émission de i jusqu'à j.
On notera c(i,r) le coût d'émission de i jusqu'aux r plus proches capteurs.
On a c(i,r)=C(i,v(i,r)) et
C(i,j)=c(i,d(i,j)).
De plus si r=d(i,j) alors c(i,r)=C(i,j)=D²(i,j) C₂+ r C₁.
Tout arbre A reliant les n capteurs, a un coût associé : coût(A)=∑_i max{C(i,j)| ∃j i←→j ∈ A}
On cherche l'arbre reliant les n capteurs de coût minimal, par une méthode de séparation et évaluation.
La séparation se fera en imposant que le rayon d'émission d'un capteur donné est supérieur à un certain rayon ou non.
Les sous-problèmes à considérer s'obtiennent donc en donnant pour chaque capteur i,
un intervalle possible [rm(i),rM(i)] pour le rayon d'émission autour de ce capteur.
Pour tout sous-problème, on va redéfinir les fonctions C et coût et définir un graphe G,
où l'arc i→j est présent si d(i,j)≤rM(i) et d(j,i)≤rM(j), son coût étant C(i,j)=c(i,max(d(i,j),rm(i)))
Ainsi i→j est présent ssi j→i l'est, mais ces deux arcs peuvent avoir des coûts différents.
Comme le graphe est représenté par la matrice des coûts C, on donnera un coût infini aux arcs inexistants.
De plus deux arcs de même origine et de même extrémité avec des coûts différents seront remplacés par le moins cher des deux.
Ainsi ajouter un arc i→j de coût a, pourra toujours se coder C(i,j):=min(C(i,j),a)
Le graphe G est connexe ssi il est fortement connexe.
S'il n'est pas connexe, alors le sous-problème n'a pas de solution réalisable. On peut lui attribuer un coût infini.
S'il est connexe, on peut trouver en O(n²) un minorant du coût valable pour tous les sous-graphes fortement connexes reliant
tous les capteurs et donc en particulier tous les arbres reliant les n capteurs. Pour tout sous-graphe H de G,
i.e. un graphe ayant les mêmes n sommets, mais seulement une partie des arcs de G (en gardant leur coût),
on notera origine(H)={i|∃j i→j ∈ H} l'ensemble des origines de tous les arcs de H,
et coût(H,i)= max{C(i,j) | ∃j i→j∈ H} le coût maximal d'un arc de H partant du capteur i,
et coût(H)=∑_{i∈ origine(H)} coût(H,i).
Cette définition remplace en la généralisant la définition du coût d'un arbre donnée précédemment. En effet elle donne la
même valeur dans le cas où le sous-problème considéré est le problème complet (i.e. rm(i)=1 et rM(i)=n-1 pour tout i) et
si on assimile l'arête i←→j aux deux arcs i→j et j→i.
Idem pour C.
Première méthode :
On choisit un sommet quelconque r, que l'on prend comme racine de l'arbre A. On oriente
alors toutes les arêtes en arcs qui vont vers la racine. L'arbre A donne donc une arborescence A_r de racine r. Alors
coût(A) ≥ coût(A_r)+min_j C(r,j)
Le coût minimal d'une arborescence de racine r couvrant le graphe peut se calculer en O(n²) par la méthode d'Edmonds.
On peut prendre r au hasard, ou chercher le plus grand majorant obtenu en prenant tous les r possibles.
Le temps de calcul semble être n³, mais on peut le ramener facilement à n².
On ne s'attardera pas sur cette méthode car on peut la simplifier en améliorant nettement le minorant.
Méthode d'Edmonds :
Pour chaque sommet i (sauf la racine r) on prend un arc de coût minimal sortant de i, i→ppv(i).
Si l'ensemble de ces n-1 arcs ne forme aucun cycle, on a alors une arborescence convergeant vers r, qui est évidemment
de coût minimal.
S'il y a un cycle, on modifie le graphe en fusionnant tous les sommets du cycle en un seul nouveau sommet s.
Un arc i→j est conservé avec le même coût si i et j ne sont pas dans le cycle.
Il est supprimé si i et j sont dans le cycle.
Si j est dans le cycle mais non i, alors il devient un arc i→s de même poids (C(i,s):=min(C(i,s),C(i,j))
Si i est dans le cycle mais non j, alors il devient un arc s→j de poids C(i,j)-C(i,ppv(i)), qui correspond
à l'augmentation de coût quand on remplace i→ppv(i) par i→j. (C(s,j):=min(C(s,j),C(i,j)-C(i,ppv(i))).
Il n'y a plus qu'à chercher une arborescence de coût minimal dans le nouveau graphe.
Deuxième méthode :
On peut appliquer la méthode d'Edmonds, sans choisir de racine.
Pour chaque sommet parmi les n, on prend un arc de coût minimal sortant de i, i→ppv(i).
Il y a donc forcément un cycle, que l'on réduit.
La méthode s'arrête quand il n'y plus qu'un seul sommet et donc zéro arc.
Cela peut s'interpréter autrement :
On commence par ajouter un sommet supplémentaire fictif u inacessible qui sera la racine pour la vraie méthode d'Edmonds.
Comme ce sommet est inaccesible, il ne sera jamais le plus proche voisin d'un autre sommet,
et la méthode d'Edmonds s'arrêtera seulement quand tous les autres sommets auront été fusionnés en un seul.
On obtient ainsi un graphe connexe avec un seul cycle, au lieu d'une arborescence.
Supposons par exemple que le dernier cycle fusionné soit de longueur 2, s→t→s.
Une arborescence de coût minimal ayant sa racine dans (un des sommets de) s fait intervenir le coût C(t,s) mais non C(s,t).
De même une arborescence de coût minimal ayant sa racine dans t fait intervenir le coût C(s,t) mais non C(t,s).
Par contre un graphe fortement connexe fera intervenir les deux,
car il a au moins un arc sortant de s pour aller dans t et un arc sortant de t pour aller dans s.
On obtient ainsi un minorant meilleur que par la première méthode. Démontrons le.
Le dernier cycle fusionné était s→t→s.
Ce cycle correspond dans le graphe initial à un sous-graphe G₀
qui possède exactement un arc sortant de chaque sommet. Soit i→f(i) l'arc sortant de i.
Soit S l'ensemble des sommets fusionnés en s.
Soit T l'ensemble des sommets fusionnés en t.
Dans G₀ un seul arc va de S dans T, soit a→f(a) cet arc.
De même un seul arc va de T dans S, soit b→f(b) cet arc.
G₀-{a→f(a)} est une arborescence couvrante, convergeant vers a de coût minimal (produite
par la méthode d'Edmonds quand on ajoute un arc a→u très cher). De même
G₀-{b→f(b)} est une arborescence couvrante, convergeant vers b de coût minimal.
Ainsi G₀ est formé d'une arborescence couvrant S convergeant vers b, de l'arc b→f(b),
d'une arborescence couvrant T convergeant vers a et de l'arc a→f(a).
Ce graphe contient donc un seul cycle. Et ce cycle passe par a et b.
Pour un sous-graphe H de G, on notera H|S son sous-graphe obtenu en ne gardant que
les arcs partant de sommets contenus dans S (mais arrivant peut-être hors de S).
Soit H un sous-graphe fortement connexe.
On peut en extraire une arborescence couvrante convergeant vers b, H_b.
Alors H_b|S ∪ G₀|(T-{b}) est une arborescence couvrante convergeant vers b. Comme
G₀-{b→f(b)} est une arborescence couvrante convergeant vers b de coût minimal,
on en déduit que coût(H_b|S)≥coût(G₀|S). Comme coût(H|S)≥coût(H_b|S) on en
déduit que coût(H|S)≥coût(G₀|S).
De même on voit que coût(H|T)≥coût(G₀|T).
En additionnant ces deux dernières inégalités on obtient coût(H)≥coût(G₀).
Cela montre que coût(G₀) est un minorant du coût de tout sous-graphe fortement connexe de G.
Dans le cas où C(i,j)=C(j,i) pour tout couple (i,j) (par exemple pour le problème complet quand C₁=0)
on pourrait définir ce nombre comme poids de l'arête i←→j et
appliquer l'algorithme de Prim. Alors coût(G₀) serait le poids d'un arbre couvrant de poids minimal,
en comptant double son arête la plus lourde.
Exemple :
Supposons que le graphe ait les quatre sommets 0, 1, 2 et 3.
0→1, 1→0, 2→3 et 3→2 sont de coût nul. Les arcs i→i sont de coût infini. Tous les autres arcs sont de coût 1.
Alors s est le cycle 0→1→0 fusionné, t est le cycle 2→3→2 fusionné. Les deux arcs s→t et t→s sont de poids 1.
La première méthode donne un minorant égal à 1. La deuxième méthode donne un minorant égal à 2, qui est optimal.
Mais on doit utiliser Edmonds plutôt que Prim, car la matrice des coûts C peut être très dissymétrique :
Si rm(i) est grand alors que rm(j) est petit, alors C(i,j) peut être beaucoup plus grand que C(j,i).
La méthode d'Edmonds donne un rayon r(i)=d(i,f(i)) pour chaque sommet i et
un minorant du coût de toute solution de ce sous-problème.
De plus ce minorant est atteint si ces rayons donnent un graphe bidirectionnel connexe.
Sinon on peut définir R(i)=max(r(i),max_{j,i=f(j)} d(i,j)), comme le rayon minimal d'émission du capteur i
pour s'assurer que le graphe contiennent tous les arcs j→f(j) et f(j)→j.
On peut alors séparer le sous-problème en deux sous-problèmes en remplaçant l'intervalle [rm(i),rM(i)] par
[rm(i),R(i)[ ou [R(i),rM(i)] pour le sommet i pour lequel c(i,R(i))-c(i,r(i)) est maximal.
Le programme joint fait cela. Il traite sur mon ordinateur le cas aléatoire n=25 en 0.006s et
trouve la solution optimale de coût 950.
Dans le cas où les capteurs sont alignés sur une droite, on peut trouver la solution optimale en O(n³)
par programmation dynamique. On peut d'abord trier les capteurs par abscisse croissante.
On peut alors interdire deux arêtes i←→k et j←→l avec i<j<k<l dans tout arbre couvrant optimal.
En effet si par exemple C(k,i)≥C(j,l) alors
C(i,j)<C(i,k) et C(j,i)<C(k,i)≤C(j,l) donc i et j peuvent dialoguer directement sans surcoût.
C(j,k)<C(j,l) et C(k,j)<C(k,i) donc j et k peuvent dialoguer directement sans surcoût.
On pourrait donc remplacer i←→k par i←→j ou j←→k pour obtenir un autre arbre couvrant avec un coût non majoré
et une somme des longueurs des arêtes strictement plus petite.
Donc parmi les arbres couvrants de coût minimal, un arbre dont la somme des longueurs des arêtes est minimale
n'a pas deux arêtes qui se chevauchent.
Au lieu de chercher un arbre couvrant de coût minimal, on va chercher un arbre couvrant sans arête se chevauchant,
de coût minimal. Dans ce qui suit, implicitement, tous les arbres couvrant seront sans arête se chevauchant.
On peut alors définir cc(i,j) comme le coût minimal d'un arbre couvrant [i..j] et contenant l'arête i←→j,
ccc"(i,j,r) le coût minimal d'un arbre couvrant [i..j] dont la plus longue arête qui sort de i est i←→k avec d(i,k)=r,
ccc'(i,j,r) le coût minimal d'un arbre couvrant [i..j] dont la plus longue arête qui sort de i est i←→k avec d(i,k)≥r et
ccc(i,j,r) le coût minimal d'un arbre couvrant [i..j] avec rayon(i)≥r.
On a alors les relations de récurrence suivantes pour i<j :
cc(i,j)=cc(j,i)=min{ ccc(i,I,d(i,j))+ccc(j,J,d(j,i)) pour i≤I<I+1=J≤j }
car l'arbre couvrant [i..j] est formé de l'arête i←→j et de deux sous-arbres couvrant respectivement [i..I] et [J..j].
ccc"(i,j,d(i,k))= cc(i,k)+ccc(k,j,d(k,i))-C(k,i) pour k∈[i+1,j] et
ccc"(i,j,r)=∞ si r n'est pas de la forme d(i,k) avec k∈[i+1,j],
car un arbre couvrant [i..j] avec une plus longue arête i←→k partant de i, est formé d'un sous-arbre couvrant [i..k]
contenant l'arête i←→k et d'un sous-arbre couvrant [k..j], mais le coût de k est compté dans les deux arbres,
avec un rayon d(k,i) pour l'un et un rayon plus grand pour l'autre. On peut donc décompter le coût de k→i.
ccc'(i,j,r)=min(ccc"(i,j,r),ccc'(i,j,r+1))
ccc(i,j,r)=min(ccc'(i,j,r),ccc(i,j,r-1)-c(i,r-1)+c(i,r))
Pour i>j on a les mêmes relations en remplaçant i≤I<I+1=J≤j par i≥I>I-1=J≥j et k∈[i+1,j] par k∈[j,i-1].
On peut utiliser le même tableau pour ccc, ccc' et ccc", une case de ce tableau contiendra d'abord ∞,
puis ccc"(i,j,r), puis ccc'(i,j,r) et enfin ccc(i,j,r), la valeur décroissant toujours au cours du temps.
On peut donc calculer cc et ccc en O(n³) par l'algorithme suivant :
On remplit ccc avec l'infini.
pour tout i et tout r faire ccc(i,i,r):=c(i,r) fait
pour tous les couples (i,j) avec i≠j pris dans l'ordre croissant des |i-j| faire
cc(i,j) := min ccc(i,I,d(i,j))+ccc(j,J,d(j,i)) pour i≤I<I+1=J≤j ou i≥I>I-1=J≥j
pour k=i+1,i+2..j ou k=i-1,i-2...j faire ccc(i,j,d(i,k)):=cc(i,k)+ccc(k,j,d(k,i))-C(k,i) fait
pour r=n-1,n-2..2 faire ccc(i,j,r-1):=min(ccc(i,j,r-1),ccc(i,j,r)) fait
pour r=2,3..n-1 faire ccc(i,j,r):=min(ccc(i,j,r),ccc(i,j,r-1)-c(i,r-1)+c(i,r)) fait
fait
A la manière du C on notera a min= b pour a:=min(a,b) de même que a += b remplace a:=a+b.
De plus on peut remarquer que pour tout couple (i,j), les valeurs de k et de J sont les mêmes.
C'est pourquoi on remplacera k par J et on utilisera la même boucle pour calculer cc(i,j) et les ccc"(i,j,d(i,k))
Mais il faut faire attention à l'ordre des instructions, car cc(i,j) est utilisé pour calculer ccc"(i,j,d(i,j)).
On remplit ccc et cc avec l'infini.
pour tout i et tout r faire ccc(i,i,r):=c(i,r) fait
pour tous les couples (i,j) avec i≠j pris dans l'ordre croissant des |i-j| faire
pour tous les (I,J) tels que i≤I<I+1=J≤j ou i≥I>I-1=J≥j en terminant par J=j faire
cc(i,j) min= ccc(i,I,d(i,j))+ccc(j,J,d(j,i))
ccc(i,j,d(i,J)) := cc(i,J)+ccc(J,j,d(J,i))-C(J,i))
fait
pour r=n-1,n-2..2 faire ccc(i,j,r-1) min= ccc(i,j,r) fait
pour r=2,3..n-1 faire ccc(i,j,r) min= ccc(i,j,r-1)-c(i,r-1)+c(i,r) fait
fait
La solution est ccc(0,n-1,1)
On peut coder le problème SAT en un problème de capteurs. Par exemple (a∨b∨¬c) ∧ (a∨c∨¬d) ∧ (¬a∨¬b∨d)
donne la matrice des coûts suivante :
a ¬a b ¬b c ¬c d ¬d a∨b∨¬c a∨c∨¬d ¬a∨¬b∨d 1
a . 0 . . . . . . 1 1 . 1
¬a 0 . . . . . . . . . 1 1
b . . . 0 . . . . 1 . . 1
¬b . . 0 . . . . . . . 1 1
c . . . . . 0 . . . 1 . 1
¬c . . . . 0 . . . 1 . . 1
d . . . . . . . 0 . . 1 1
¬d . . . . . . 0 . . 1 . 1
a∨b∨¬c 1 . 1 . . 1 . . . . . .
a∨c∨¬d 1 . . . . . . 1 . . . .
¬a∨¬b∨d . 1 . 1 . . 1 . . . . .
1 1 1 1 1 1 1 1 1 . . . .
Le prédicat est satisfiable ssi il existe une solution de coût 8.(avec 8 capteurs de coût 1 et 4 de coût 0)
Le problème des capteurs est donc NP-difficile.
Pour des capteurs placés dans un plan euclidien, le problème reste NP-difficile. On peut encore coder SAT.
Chaque clause n'est plus réduite à un capteur, mais est représentée par une composante connexe "évidente", contenant
des chaînes de capteurs proches. Deux telles chaînes peuvent se croiser sans se connecter, par exemple :
x x x x
x
y y y y y y y y y y y y y y y y y y
x y
x x x x y
Le long d'une chaîne, l'écartement des capteurs doit varier suffisamment lentement pour que la coupure de la chaîne
ne rapporte pas assez pour payer une connexion ailleurs.
Un atome a intervenant dans les clauses x, y et z tandis que ¬a intervient dans les clauses t et u peut se coder :
z
y Z t
Y T
a A
X U
x 1 u
2
Avec
d(1,X)>1 d(x,X)=d(x,a)=1
d(X,Y)>1 d(y,Y)=d(Y,a)=1
d(Y,Z)>1 d(z,Z)=d(Z,a)=1 d(Z,A)>1
d(Z,T)>1 d(t,T)=d(T,A)=1
d(T,U)>1 d(u,U)=d(U,A)=1
d(U,1)>1 d(2,1)=d(1,A)=d(1,a)=1 d(a,A)<1
Le rayon d'émission minimal de chacun de ces capteurs est 1 sauf pour a et A qui ont un rayon minimal d'émission de d(a,A).
Mais un des deux au moins doit émettre à un rayon 1 pour que le groupe a←→A ne soit pas isolé. On code a vrai comme r(a)=1
et a faux comme r(A)=1. Alors une clause est vraie ssi sa composante connexe est reliée à celle de 1 (et 2).
Ainsi on peut coder dans un problème de capteurs, la satisfiabilité d'un ensemble de clauses, dans lequel chaque atome
apparaît exactement 5 fois, 3 fois positivement et 2 fois négativement.
Cela prouve que le problème des capteurs en dimension 2 est NP-difficile,
car on peut facilement transformer un ensemble de clauses pour que chaque atome apparaisse le bon nombre de fois sans
changer sa satisfiabilité, en appliquant tant qu'on peut une des règles suivantes (prises dans l'ordre) :
Si un atome a apparaît plus souvent négativement que positivement,
on change sa valeur de vérité en remplaçant tous les a par des ¬a et réciproquement.
Si un atome n'apparaît jamais négativement, on considère qu'il est vrai et on supprime donc toute clause où il apparaît.
Si le littéral ¬a n'apparaît qu'une seule fois, on le met en double dans la même clause.
Si le littéral a apparaît moins de trois fois, on le duplique dans une des clauses où il apparaît.
Si un atome a apparaît plus de 5 fois, on crée un nouvel atome a', puis on remplace deux occurrences de a par a' et
une occurrence de ¬a par ¬a' en ajoutant les deux clauses a∨¬a' et a'∨¬a, (qui traduisent a=a').
Alors a' apparaît le bon nombre de fois et a apparaît une fois de moins.
Comparaison avec la méthode d'évaluation qui compte les liens sortants.
Exemple 1:
3
2
1 0 4 5 8 9
6
7
Solution optimale :
C(0,2)+C(1,0)+C(2,4)+C(3,2)+C(4,2)+C(5,8)+C(6,0)+C(7,6)+C(8,5)+C(9,8)=
2 + 1 + 2 + 1 + 2 + 49 + 2 + 1 + 49 + 1 = 110
Minoration basée sur la méthode d'Edmonds :
C(0,2)+C(1,0)+C(2,4)+C(3,2)+C(4,5)+C(5,8)+C(6,0)+C(7,6)+C(8,5)+C(9,8)=
2 + 1 + 2 + 1 + 1 + 49 + 2 + 1 + 49 + 1 = 109
accroissement de coût en fonction du nombre de voisins atteints :
1 2 3
{0,1} C(0,1)+C(1,0)=2 1 1 3
{2,3} C(2,3)+C(3,2)=2 1 1 3
{4,5} C(4,5)+C(5,4)=2 1 1 3
{6,7} C(6,7)+C(7,6)=2 1 1 3
{8,9} C(8,9)+C(9,8)=2 48 63 81
minoration : 5*2+4*1+48=62
Exemple 2:
3 f
2 e
1 0 4 5 8 9 c d
6 a
7 b
Solution optimale :
C(0,2)+C(1,0)+C(2,4)+C(3,2)+C(4,2)+C(5,8)+C(6,0)+C(7,6)+C(8,5)+C(9,a)+C(a,9)+C(b,a)+C(c,a)+C(d,c)+C(e,g)+C(f,e)=
2 + 1 + 2 + 1 + 2 + 49 + 2 + 1 + 49 + 2 + 2 + 1 + 2 + 1 + 2 + 1 = 120
Minoration basée sur la méthode d'Edmonds :
C(0,2)+C(1,0)+C(2,4)+C(3,2)+C(4,5)+C(5,8)+C(6,0)+C(7,6)+C(8,5)+C(9,8)+C(a,9)+C(b,a)+C(c,a)+C(d,c)+C(e,g)+C(f,e)=
2 + 1 + 2 + 1 + 1 + 49 + 2 + 1 + 49 + 1 + 2 + 1 + 2 + 1 + 2 + 1 = 118
accroissement de coût en fonction du nombre de voisins atteints :
1 2 3
{0,1} C(0,1)+C(1,0)=2 1 1 3
{2,3} C(2,3)+C(3,2)=2 1 1 3
{4,5} C(4,5)+C(5,4)=2 1 1 3
{6,7} C(6,7)+C(7,6)=2 1 1 3
{8,9} C(8,9)+C(9,8)=2 1 1 3
{a,b} C(a,b)+C(b,a)=2 1 1 3
{c,d} C(c,d)+C(d,c)=2 1 1 3
{e,f} C(e,f)+C(f,e)=2 1 1 3
minoration : 8*2+8*1=24
Exemple 3:
Capteurs alignés à peu près équidistants.
i 0 1 2 3 4 5 6 7 8
C(i,i+1)=C(i+1,i) 103 102 108 107 102 103 109 107 104
Solution optimale :
103+103+108+108+107+103+109+109+107+104=1066
Minoration basée sur la méthode d'Edmonds :
103+102+108+107+102+103+109+109+107+104=1053
accroissement de coût en fonction du nombre de voisins atteints :
1 2
{0,1,2} 103+102+102=307 6
{3,4,5,6} 107+102+102+103=414 1 7
{7,8,9} 107+104+104=315 2
minoration : 307+414+315+6+7+2=1051
Dans les exemples 1 et 2, la minoration basée sur la méthode d'Edmonds est nettement meilleure, car elle seule
compte double le lien 5←→8 qui est beaucoup plus coûteux que tous les autres liens impliqués dans la
solution optimale.
Cas monodirectionnel
Au lieu de chercher un arbre reliant les n sommets de coût minimal, on va chercher un graphe fortement connexe
de coût minimal. Tout ce qui prédède est encore valable avec quelques aménagements :
Dans le graphe G, l'arc i→j existe ssi d(i,j)≤rM(i) et alors son coût est c(i,max(d(i,j),rm(i))).
Maintenant i→j peut exister indépendamment de j→i.
La minoration par la méthode d'Edmonds marche toujours. Mais on change le choix de la séparation (la majoration).
Au lieu de prendre comme solution réalisable les rayons minimaux pour que tous les arcs du graphe à un cycle
donné par la méthode d'Edmonds puissent être pris dans les deux sens, on va prendre comme solution réalisable
les rayons minimaux pour avoir simultanément toutes les arborescences données par la méthode d'Edmonds pour
tous les choix de racine possibles. Il n'y a en tout pas plus de 2n arcs à inclure, et cela peut se calculer
en O(n²) cf. le programme joint qui traite le cas bidirectionnel quand il contient
#define bi 1
et le cas monodirectionnel avec
#define bi 0
Dans ce cas :
pour tout sommet i∈[0,nbc[ faire
j:=i, k:=ppv(i)
tant que j≥n ou k≥n on remplace le plus grand de j et k par ori(j,k)
rm(j):=max(rm(j),d(j,k)) met dans le graphe l'arc j→k, l'arc d'origine de l'arc i→ppv(i)
fait
Cela ressemble beaucoup à la construction du graphe G₀, mais lors de cette construction,
si j>k et j≥n alors, en notant j'=ori(j,k), non seulement j→k devient j'→k, mais l'ancien arc j'→ppv(j') est supprimé.
C'est pourquoi on fait seulement ppv(j'):=k avant de passer au i suivant. Le calcul se finira quand i vaudra j'.
Ainsi la construction du graphe G₀ ressemble plutôt à :
pour tout sommet i=nbc-1,nbc-2, ..., 2, 1, 0 faire (Il faut les prendre dans l'ordre décroissant)
k:=ppv(i)
tant que k>i et k≥n faire k:=ori(i,k)
ppv(i):=k
si i≥n alors
i':=ori(i,k)
ppv(i'):=k
finsi
fait
pour tout i∈[0,,n-1] on met i→ppv(i) dans G₀
Ainsi les deux calculs se ressemblent beaucoup, la seule différence est que dans la construction de G₀, quand on choisit
un arc j→k qui sort d'un cycle, on ouvre le cycle en enlevant l'ancien arc j→ppv(j), alors que l'on garde tout
le cycle lors de la construction de l'union des arborescences correspondant aux diverses racines possibles.
Dans le premier cas on a exactement n arcs, (il en part un de chacun des n sommets).
Dans le deuxième cas on a un peu moins de 2n arcs. Il peut partir plusieurs arcs de certains sommets,
et on obtient bien ainsi un graphe fortement connexe.
Dans le cas où les capteurs sont alignés sur une droite, on peut trouver la solution optimale par programmation
dynamique en O(n³) comme dans le cas bidirectionnel, ou même en O(n²) si la matrice C des coûts est symétrique.
On supposera encore les capteurs triés par abscisse croissante.
Au lieu d'interdire la présence simultanée des arêtes i←→k et j←→l dans une solution optimale quand i<j<k<l,
on va interdire presque tous les cas où i→k ou i←k coexisterait avec j→l ou j←l.
i←−−k peut être remplacé i←−−k
j←−−l sans surcoût par j←k←l
i−−→k peut être remplacé i→j→k
j−−→l sans surcoût par j−−→l
i←−−k peut être remplacé i←j←k si par exemple C(k,i)≤C(j,l),
j−−→l sans surcoût par j−−→l car C(j,i)≤C(k,i)≤C(j,l)
ou sinon par i←−−k
j→k→l
Enfin
i−−→k peut être remplacé sans surcoût si k≥j+2, car alors il existe un arc e→f avec j<e<k et
j←−−l f hors de l'intervalle ]j,k[. Supposons par exemple que f≥k. Alors
e−→ peut être remplacé e−→
i−−−−→k sans surcoût par i−−→e→k
j←−−−−l j←−−−−l
Une suite de telles transformations remplaçant sans surcoût un arc par deux arcs strictement plus courts
ne peut pas revenir à son point de départ et s'arrête donc forcément au bout d'un nombre fini d'étapes.
Ainsi parmi les sous-graphes fortement connexes de coût minimal, on peut en trouver un qui ne contienne deux
arcs se chevauchant que s'ils convergent vers deux capteurs consécutifs.
i−−−→j+1
j←−−−−l
Mais cela ne suffit pas. On va caractériser autrement les solutions optimales.
Dans une solution optimale, il existe un chemin A qui ne recule jamais qui va de 0 à n-1. En effet en partant d'un chemin
quelconque sans cycle allant de 0 à n-1, on peut supprimer un retour en arrière jusqu'à un capteur i, en tronquant
le premier saut par dessus i. On peut recommencer ainsi jusqu'à ce qu'il n'y ait plus de retour en arrière.
De même il existe un chemin R qui n'avance jamais qui va de n-1 à 0.
On assimilera A et R à des ensembles de capteurs et par exemple #A désignera le nombre de capteurs de A.
Mais on notera aussi (abusivement) i→j ∈ A pour dire que i et j sont deux capteurs consécutifs de A.
Parmi les solutions de coût minimal, on va choisir celles pour lesquelle #A+#R est maximal.
Un capteur qui n'est ni dans A ni dans R, peut être atteint sans surcoût en tronquant l'arc du chemin aller
(ou retour) qui le saute. Il faut donc seulement s'assurer qu'il part de ce capteur un chemin rejoignant A ou R.
Donc en plus des deux chemins aller et retour entre les capteurs extrèmes, la solution optimale contient seulement une forêt
de coût minimal reliant tous les capteurs absents de A et R vers les capteurs de A∪R. Dans cette forêt, jamais
un arc ne saute par dessus une racine possible. De plus cette forêt ne contient pas d'arc dont les extrémités se chevauchent.
En effet si i<j<k<l, alors les deux arcs i→k et j←l ne peuvent coexister car par exemple
si i n'est pas sur le chemin partant de l, i→k peut se tronquer en i→j en diminuant le coût.
Soient a et b deux capteurs consécutifs de A∩R. La suite des capteurs de (A∪R)∩]a,b[ pris dans l'ordre croissant
ne peut pas contenir deux capteurs consécutifs i<j avec i∈A et j∈R car on aurait deux arcs i→ et ←j divergents qui se
chevaucheraient et le moins cher des deux pourrait sans surcoût être coupé en deux, ce qui rajouterait i dans R ou j dans A.
Donc tous les éléments de R∩]a,b[ précèdent ceux de A∩]a,b[. Donc les deux arcs a→a' de A et b'←b de R vérifient a≤b'<a'≤b.
De plus a'=b'+1 car sinon il existerait un arc e→f avec e dans ]b',a'[ et f en dehors et
on pourrait rajouter e dans A ou dans R.
Aucun arc ne saute a ou b et les seuls arcs ayant leurs deux extrémités dans [a,b] sont
a→a' et b'←b et des versions tronquées de ces deux arcs, plus une
arborescence de poids minimal partant des capteurs a à b' et convergeant vers a ainsi qu'une
arborescence de poids minimal partant des capteurs a' à b et convergeant vers b.
Si la matrice C des coûts est symétrique, i.e. si C₁=0, alors ces deux arborescences sont linéaires,
car par exemple si i<j<k alors i→k→j se remplace à moindre coût par i→j←k et j→k→i par i←j←k.
Comme les racines des arborescences sont le plus petit et le plus grand de leurs éléments,
les arborescences de coût minimal sont donc :
a←a+1←a+2←a+3←...←b' et a'→a'+1→a'+2→a'+3→...→b
La solution optimale est formée d'une suite de tels blocs concaténés et
peut se trouver par programmation dynammique en définissant
cc(i) le coût minimal d'un graphe allant de tout capteur de 1 à i vers 0 et de 0 à i+1,
ccc"(i,r) (resp. ccc'(i,r)) le coût minimal d'un graphe fortement connexe couvrant 0..i dont
le plus long arc qui sort de i est i→k avec d(i,k)=r (resp. d(i,k)≥r).
ccc(i,r) le coût minimal d'un graphe fortement connexe couvrant 0..i avec rayon(i)≥r et
aa(i,j) le coût minimal d'une arborescence de racine i partant des capteurs i+1 à j si i<j ou j à i-1 sinon.
Si l'arborescence de coût minimal partant des capteurs i à k et convergeant vers i contient k→j, alors aucun autre arc
de cette arborescence ne traverse j et donc les arcs partant des capteurs i+1 à j forment une arborescence (de coût minimal)
convergeant vers i, tandis que les arcs partant des capteurs j+1 à k-1 forment une arborescence (de coût minimal)
convergeant vers k. Donc :
aa(i,i)=0
aa(i,k)=min{aa(i,j)+aa(k,j+1)+C(k,j) | i≤j<k } si i<k
aa(i,k)=min{aa(i,j)+aa(k,j-1)+C(k,j) | i≥j>k } si i>k
La matrice aa peut donc se calculer en un temps en O(n³).
Si la matrice des coûts est symétrique, alors le maximum est toujours atteint pour j=k±1.
On peut donc garder le même programme en limitant la boucle sur j à une itération ou utiliser
aa(i,k)=aa(i,k-1)+C(k,k-1) si i<k
aa(i,k)=aa(i,k+1)+C(k,k+1) si i>k
ou encore ne garder que la première ligne et la première colonne de aa en remarquant que
aa(i,k)=aa(0,k)-aa(0,i) si i<k
aa(i,k)=aa(i,0)-aa(k,0) si i>k.
De toute façon aa se calcule en O(n²).
Les relations de récurrence permettant de calculer cc, ccc", ccc' et ccc sont :
cc(j)=min{ ccc(i,d(i,j+1)+aa(i,j) | i∈[0..j] } où i=max(A∩R∩[0..j]) et i→j+1 ∈ A
ccc"(J,r)=cc(i)+aa(J,i+1)+c(J,r) si ∃i∈[0,J[ r=d(J,i) car alors J∈A∩R et i←J ∈ R et sinon ccc"(J,r)=∞
ccc'(J,r)=min(ccc"(J,r),ccc(J,r+1))
ccc(J,r)=min(ccc'(J,r),ccc(J,r-1)+c(J,r)-c(J,r-1))
On peut évidemment utiliser le même tableau pour ccc, ccc' et ccc" et calculer cc et ccc par :
on remplit cc et ccc avec l'infini
pour tout r faire ccc(0,r):=c(0,r) fait
pour J=1,2, ..., n-1 faire
j:=J-1
pour i=0,1,2, ..., j faire cc(j) min= ccc(i,d(i,J))+aa(i,j) fait
pour i=0,1,2, ..., j faire ccc(J,d(J,i)) := cc(i)+aa(J,i+1)+C(J,i) fait
pour r=n-1,n-2,n-3, ..., 2 faire ccc(J,r-1) min= ccc(J,r) fait
pour r=2, 3, 4, ..., n-1 faire ccc(J,r) min= ccc(J,r-1)+c(J,r)-c(J,r-1) fait
fait
La valeur de la solution optimale est ccc(n-1,1)
Cet algorithme est en O(n²), une fois que aa est rempli. Dans le cas où la matrice des coûts c n'est pas symétrique,
le temps de calcul global est en O(n³) à cause du calcul de aa.
Le programme joint fait le calcul en n² ou n³ selon c1 : La boucle for(k=c1?l:1;k;k--) est faite 1 ou l fois.
La matrice de coûts utilisée pour coder le problème SAT en un problème de capteurs bidirectionnels, marche sans changement
dans le cas monodirectionnel, qui est donc bien NP-difficile.
Par contre dans le cas des capteurs dans un plan euclidien, le codage du problème SAT avec des atomes apparaissant
exactement 5 fois, ne marche plus, car deux chaînes de capteurs ne peuvent pas se croiser sans que la plus lâche
se branche sur la plus serrée. On ne peut donc pas démontrer ainsi, que le problème des capteurs monodirectionnels
dans un plan euclidien est NP-difficile.
Mais on va définir TSP_E₂D1 comme un problème de voyageur de commerce avec les contraintes :
Toute ville i est représentée par un point P_i du plan euclidien.
∀i, ∀j, d(i,j)=d(j,i)∈{1,∞} d(P_i,P_j)≥1 d(i,j)=1 ==> d(P_i,P_j)=1
Autrement dit, la distance euclidienne entre deux villes est toujours supérieure ou égale à 1.
On cherche un circuit passant par chaque ville une fois et un seule, formé uniquement d'arêtes de longueur 1,
mais certaines arêtes de longueur 1 sont interdites (On peut avoir d(i,j)=∞ et d(P_i,P_j)=1).
Le problème TSP_E₂D1 peut se coder comme un problème de capteurs monodirectionnel dans le plan euclidien :
Chaque arête i←→j (i.e. d(i,j)=1 et donc d(P_i,P_j)=1) donne deux capteurs :
P_iε+P_j(1-ε) proche de P_j et P_jε+P_i(1-ε) proche de P_i.
On définit le coût d'un arc reliant deux capteurs comme le carré de leur distance euclidienne.
Soit t_i le coût minimal d'une arborescence reliant tous les capteurs proches de P_i.
Ce nombre ne dépend pas de la racine, c'est en fait le coût minimal d'un arbre reliant ces capteurs.
Dans une solution optimale, parmi les capteurs proches d'une ville, il y a en a au moins un qui émet
vers une autre ville à un coût au moins égal à (1-2ε)², mais il émet donc vers tous ses voisins,
qui doivent au minimum produire une arborescence (de coût minimal t_i) convergent vers le capteur
qui émet au loin. Cela montre que le coût de toute solution est minoré par ∑_i (t_i +(1-2ε)²).
Si le coût d'une solution atteint ce minorant, alors chaque ville émet vers une seule autre ville.
Le graphe obtenu contient donc un cycle, dont on ne peut pas sortir, et qui doit donc contenir toutes
les villes. On voit donc que TSP_E₂D1 a une solution ssi le problème de capteurs monodirectionnel
à une solution optimale de coût ∑_i (t_i +(1-2ε)²).
Il reste à montrer que l'on peut coder SAT dans TSP_E₂D1.
Un symbole se code comme un ruban de largeur 2 formé d'une suite de carrés et de losanges, qui peut faire des coudes :
――●―――●―――●―――●―――●―――●―――● ● ●―――●―――●―――●―――●――
│ │ │ │ │ │ │ / \ │ │ │ │ │
――●―――●―――●―――●―――●―――●―――● ●―――● ● ●―――●―――●―――●―――●――
│ │ / \ \ / \ │ │
●―――●―――● ●―――● ●―――●―――●―――●
\ \ \ / \ / / / /
●―――●―――● ●―――●―――●―――●
a vrai se code par le chemin :
a―●―――●―a―●―――●―a―●―――●―a―● ● ●―a―●―a―●―――●―a―●――
a a a a a a a a a a │ a a a
――●―a―●―――●―a―●―――●―a―●―――● ●―――● ● ●―a―●―――●―a―●―――●―a
│ a a a a / a │ a
●―a―●―――● ●―a―● ●―――●―a―●―――●
a \ a / \ a a a a
●―a―●―a―● ●―a―●―――●―a―●
a faux se code par le chemin :
――●―A―●―――●―A―●―――●―A―●―A―● ● ●―A―●―――●―A―●―――●―A
A A A A A │ A A A A A A A A
A―●―――●―A―●―――●―A―●―――●―A―● ●―A―● ● ●―――●―A―●―――●―A―●――
A │ / A \ A \ A │
●―――●―A―● ●―――● ●―A―●―――●―A―●
A A A A A A A / A
●―A―●―――● ●―――●―A―●―A―●
Pour éviter des rubans invalides comme :
a―●―a―●―a―●―a―●―a―●―a―●―a―● ● ●―b―●―b―●―b―●―b―●―b
│ │ │ │ │ │ a b b b │ │ │ │
a―●―a―●―a―●―a―●―a―●―a―●―――● ●―――● ● ●―――●―b―●―b―●―b―●―b
a a a a b / b b b
●―――●―a―● ●―――● ●―b―●―b―●―――●
a \ \ a b / / / b
●―a―●―a―● ●―b―●―b―●―b―●
on peut placer deux «filtres» sur le ruban comme :
――●―――●―――●―――●―――●―――●―――●―――● ●―――●―――●―――●―――●――
/ / / / / / / / \ / \ \ \ \ \
――●―――●―――●―――●―――●―――●―――● ● ●―――●―――● ● ●―――●―――●―――●――
\ / / / / \ \ /
●―――●―――●―――● ●―――●
\ /
●
│ │ / \
Un filtre sur un ruban est un échelon ●―――● dont on force l'utilisation en le doublant : ●―――●―――●
│ │ \ /
Un filtre assure quand le ruban est invalide, que les deux cotés du filtre ne sont pas connectés.
Ainsi entre deux filtres sur un ruban invalide séparés par au moins un échelon, il y aurait un cycle.
Donc deux filtres sur un ruban assurent sa validité.
Pratiquement, dans toutes les constructions suivantes, on supposera qu'il y a un filtre à chacune des deux
extrémités d'un ruban. On omettra le filtre au bout d'un ruban quand il se transforme en une chaîne car
cela assure déjà sa validité.
――●―――●―――●―――●―――●―――● ●―――●―――●―――●―――●―――●――
/ / / / / / \ / / / / / /
――●―――●―――●―――●―――●―――●―――●―――●―――●―――●―――●―――●―――●―――●―――●――
Sinon un ruban se terminera toujours par un filtre :
――●― ,●―― ――●― ,●――
│ `●―――●―――●―――●―――●―――●―――●―――●―――●―――●' │ │ `●' │
● │ │ │ │ │ │ │ │ │ │ ● ● │ ●
│ ,●―――●―――●―――●―――●―――●―――●―――●―――●―――●― │ │ ,●― │
――●' `●―― ――●' `●――
Deux rubans peuvent se croiser en gardant leur valeur :
│ │ h H h .
●―――● ●―――● ●―h―●
/ \ H h . h
●―――●―――● ●―――●―――● ●―h―●―h―●
/ \ h H h .
●―――●―――●―――● ○―――☺―――○―――☺ ●―?―●―d―●―d―●
│ │ │ │ │ │ │ │ ? ? . d
●―――●―――●―――● ☺―――○―――☺―――○ ●―?―●―b―● ― ●
/ / \ \ g M m d g . b d
,● ●―――●―――● ●― G,● ●―――●―――● ●―D ,● ●―b―●―b―● ●―
――●' \ \ / / `●―― g―●' \ m M / `●―d g―●' g b . d `●―d
│ ● ●―――● ● │ │ ● ●―――● ● │ g ● ●―b―● ● d
――●― / / \ \ ,●―― G―●―g / M m \ d,●―D ― ●―g g . b d ,● -
`● ●―――●―――● ●' `● ●―――●―――● ●' `● ●―b―●―b―● ●'d
\ \ / / G m M D . b . .
●―――●―――●―――● ●―――●―――●―――● ●―b―● ― ●―b―●
│ │ │ │ │ │ │ │ b . b b
●―――●―――●―――● ●―――●―――●―――● ●―b―●―b―● ― ●
\ / B b . b
●―――●―――● ●―――●―――● ●―b―●―b―●
\ / b B b .
●―――● ●―――● ●―b―●
│ │ B b . b
On notera une lettre comme d, b ou D sur une arête, qui représentera une variable valant 1 (ou vrai) si l'arête est prise
et 0 (ou faux) sinon. On notera aussi D=1-d (ou D=¬d), B=1-b (ou B=¬b) etc.
Le filtre au bout de chacun des quatre rubans extérieurs et les deux filtres sur le ruban central
nous assurent qu'ils sont tous valides. C'est pourquoi six arêtes à droite ont une présence représentée par d ou D.
Idem à gauche avec g et G, en haut avec h et H, en bas avec b et B et au centre avec m et M.
Pour chaque sommet on doit garder deux arêtes sortantes. Cela peut se traduire par une équation :
La somme des variables de présence de toutes les arêtes aboutissant à ce sommet vaut 2.
En additionnant les quatre équations correspondant aux sommets notés ○ et
en soustrayant les quatre équations correspondant aux sommets notés ☺ on obtient : h-H+M-m-g+d=0 donc 2h-2m-g+d=0.
Donc d-g≡0 (mod 2) donc d=g et h=m.
De même on peut peut obtenir D=G et b=m.
Ainsi d=g et h=m=b. Les rubans de gauche et de droite ont la même valeur.
Les rubans du haut, du centre et du bas ont la même valeur.
Quitte à faire une symétrie par rapport à un axe vertical on peut supposer que d=g=1 et D=G=0.
Quitte à faire une symétrie par rapport à un axe horizontal on peut supposer que h=b=m=1 et H=B=M=0.
Ainsi toutes les arêtes avec des lettres majuscules sont rejetées, tandis que celles
avec des minuscules sont prises. Les échelons des rubans et les chaînes sont évidemment pris.
Il y a trois façons de finir le remplissage. Deux sont dessinées.
Le petit carré formé de quatre points d'interrogation peut être utilisé de deux façons :
Le voyageur de commerce peut emprunter les deux cotés horizontaux ou les deux cotés verticaux.
Donc on peut connecter le ruban du haut à celui de droite et le gauche au bas ou bien
le haut à la gauche et la droite au bas. Le bon choix permet de s'assurer que les deux chemins
traversant le dispositif font bien partie du même cycle.
En fait on va construire une instance du problème TSP_E₂D1 à partir d'une instance du problème SAT,
c'est-à-dire d'un prédicat, en assemblant des briques qui ont toutes la même forme extérieure et se
connectent à chacune des quatre briques voisines (au dessus, en dessous, à droite et à gauche) par
un ruban. Chaque brique est donc traversée par deux chemins qui vont du ruban de droite à celui du haut
et du gauche à celui du bas ou du gauche vers le haut et du droit vers le bas. Pour éviter des circuits
fermés trop courts il est important que les deux connexions soient toujours possibles. C'est pourquoi
chaque brique comportera toujours un carré (ou un losange) critique qui permet de passer d'une connexion
à l'autre. A partir d'un choix quelconque pour tous les losanges critiques, si il existe une brique
traversée par deux chemins qui ne sont pas dans le même circuit on peut modifier le choix pour le losange
critique de cette brique, ce qui fusionne deux circuits en un seul et diminue donc d'un le nombre de circuits.
On recommence tant que c'est possible.
Cela s'arrête au bout d'un nombre fini de modifications car le nombre de circuits reste positif.
Alors les deux chemins qui traversent toute brique sont dans le même circuit, et donc il n'y a qu'un circuit.
On peut résumer ce raisonnement en disant que la présence d'un losange critique dans une brique permet
d'assurer que les deux chemins qui la traverse sont dans le même circuit.
La clause a∨c∨¬d peut se traduire par :
∃x, ∃y, ∃z, ∃t, x ∧ (¬x∨a∨y) ∧ (¬y∨c∨z) ∧ (¬z∨¬d∨t) ∧ ¬t
Le prédicat (a∨b∨¬c) ∧ (a∨c∨¬d) ∧ (¬a∨¬b∨d) peut donc se traduire par un rectangle où
quatre rubans horizontaux codant les quatre atomes a, d, c et d, croisent
trois rubans verticaux codant les clauses a∨b∨¬c, a∨c∨¬d et ¬a∨¬b∨d.
A l'intersection des rubans codant l'atome b et la clause a∨c∨¬d on met la construction précédente
qui permet à deux rubans de se croiser en gardant leurs valeurs, car l'atome n'intervient pas dans la clause.
Par contre à l'intersection des rubans codant l'atome c et la clause a∨c∨¬d on doit mettre une construction
qui code ¬y∨c∨z, c étant la valeur commune aux rubans de gauche et de droite, y la valeur du ruban du haut
et z la valeur du ruban du bas.
Ainsi le ruban vertical codant la clause a∨c∨¬d comporte cinq tronçons, puisqu'il est coupé par les quatre
rubans codant a, b, c et d. Ces cinq tronçons codent les valeurs x=1, y, y, z et t=0.
On va donc réaliser une clause à trois littéraux traversée par un ruban horizontal qui garde sa valeur :
/ / H h . J . J
●―――● ●―――● ●―J―●―J―●―J―● ●―G―●―G―●―?―●
/ \ / / u / . J . . G G ? ?
●―――● ●―――● ●―J―● ●―d―●―d ● ― ● ●―?―● .
/ \ J j . J . d . . a a a D
●―――●―――● ●―――●―――● g―●―?―● ●―d―● . ●―a―● ● ― ●
/ \ j J ? ? d . a . . D
――●―――● ●―――●―――●―――● G―●―g―● ●―――●―――●―――● ●―?―●―d―●―d―● ●―a―●―a―●―a―●
/ / \ / / / / / G J / / A . . a
――● ● ●―――● ●―――●―――● g―● ● ○―――☺ ●―――●―d―●
\ / / / \ / / / \ G / / / x / / / D j .
●―――●―――● ●―――● ● ●―― ●―g―☺―――○ ●―――● ● ●―d ●―j―●―j―●―j―●
/ / / \ / / / / A D / / G . . j
●―――●―――●―――● ●―――●―― ○―――☺―――●―――● ●―d―●―D ● ― ● ●―j―● .
\ / A a G j j j .
●―――●―――● ●―――●―――● . ●―?―● ● ― ●
\ / a A ? ? D D
●―――● ●―――● ●―?―●―D―●―D―●
/ \ / / v / A .
●―――● ●―――●
/ / b B
Pour chaque sommet on doit garder deux arêtes sortantes. Cela peut se traduire par une équation :
La somme des variables de présence de toutes les arêtes aboutissant à ce sommet vaut 2.
En additionnant les trois équations correspondant aux sommets notés ○ et
en soustrayant les trois équations correspondant aux sommets notés ☺ on obtient : A+G+J=g+x+1 donc J+A=2g+x
donc g=J∧A et x=J XOR A. De même on peut obtenir d=J∧B. Donc g=d.
On a g=J∧A donc j, a et g ne peuvent pas être nuls simultanément, autrement dit j∨a∨g est vrai.
Les trois exemples d'utilisation de la partie centrale montrent que l'on peut avoir g∧¬a∧¬j ou a∧¬g∧¬j ou j∧¬a∧¬g.
Donc chacune des trois variables j, a et g peut être vraie, les deux autres étant fausses, et dans chacun
des trois cas, le losange critique avec ses quatre points d'interrogation, permet de choisir la connexion des
rubans externes pour s'assurer que les deux chemins qui traversent le dispositif sont dans le même cycle.
Si v=0 alors b=a. Mais si v=1 alors b=1 et a=0. Ainsi l'arête v permet de déclasser en bas un vrai en faux.
Idem pour u qui permet de déclasser en haut un vrai en faux.
On a a+j+g≥1 et b≥a et h≥j donc b+h+g≥1.
Réciproquement à partir de n'importe quelles valeurs de b, h et g vérifiant b+h+g≥1 on peut
choisir a=H∧G et j=A∧B et X=d=g, alors a≤b et j≤h et a+j+g=1 et un des trois remplissages donnés convient.
Cela montre que cette construction code g=d et h+b+g≥1 (ou h∨b∨g).
En fait on a démontré l'équivalence des quatre prédicats suivants :
∃j, ∃a, (b≥a) ∧ (a+j+g=1) ∧ (h≥j)
∃j, ∃a, (b≥a) ∧ (¬a∧¬j=g) ∧ (h≥j)
∃j, ∃a, (b≥a) ∧ (a+j+g≥1) ∧ (h≥j)
b+h+g≥1
On peut utiliser ces deux briques pour coder SAT en un problème de TSP_E₂D1 et donc en un problème de
capteurs monodirectionel dans le plan euclidien :
Chaque atome est représenté par un ruban horizontal, chaque clause par un ruban vertical.
Au croisement d'un ruban vertical et d'un ruban horizontal, on met une construction
qui donne g=d et b∨¬h∨d si l'atome intervient positivement dans la clause ou
qui donne g=d et b∨¬h∨¬d si l'atome intervient négativement dans la clause ou
qui donne g=d et h=b sinon. Les extrémités gauches et droites des rubans des atomes sont reliées
deux par deux par des chaines en ignorant leur valeur. Les extrémités hautes et basses des rubans
des clauses sont reliées deux par deux par des chaînes en forçant la valeur du ruban en haut à 1 et en bas à 0.
Il faut évidemment rajouter des négations sur les rubans pour que les atomes apparaissent
avec des littéraux du bon signe dans les clauses.
Cela montre que la recherche du coût minimal de connexion forte pour des capteurs monodirectionnels
dans le plan euclidien est NP-difficile.
Les briques précédentes doivent être assemblées en les reliant par des rubans. Un ruban suffisamment long peut
avoir des extrémités situées n'importe où et orientées n'importe comment en utilisant des losanges plus ou moins
applatis et des coudes. Mais on peut peut aussi prendre une autre approche. On peut mettre toutes les villes sur
les points d'un réseau triangulaire imposé. Le croisement de deux rubans doit alors être légèrement déformé.
De plus on peut faire quelques simplifications : On garde les filtres sur les rubans verticaux, mais on peut
supprimer ceux des rubans horizontaux, car si les rubans du haut, du bas et de la gauche d'une brique sont valides
alors celui de droite l'est aussi. Comme l'extrémité gauche du ruban est valide car elle se tranforme en une
chaîne, de proche en proche vers la droite, on montre la validité de tous les rubans horizontaux.
De plus sur les rubans verticaux, entre deux clauses à trois littéraux, un seul déclassement suffit.
On peut donc supprimer tous les déclassements du bas.
Le changement de valeur d'un ruban (la négation d'un littéral) peut se faire avec 2 coudes :
●
/ \
――●―――●―――●―――● ●―――●―――●――
/ / / \ \ / / /
――●―――●―――● ●―――●―――●―――●――
\ /
●
Mais on peut s'en passer : Il n'y a pas besoin de négation sur les rubans verticaux et
on peut gérer la négation éventuelle du littéral qui traverse horizontalement une clause à 3 littéraux
en déplaçant sa partie centrale vers la droite ou la gauche. Il y a donc 3 briques : h=b, g∨¬h∨b et ¬g∨¬h∨b
h / h \ h \
●―――● ●―――● ●―――●
/ \ / \ / / \ /
●―――●―――● ●―――● ●―――●
/ \ / h' / h'
●―――●―――●―――● ●―――●―――● ●―――●―――●
/ / / / / \ / \
●―――●―――●―――● ●―――●―――●―――● ●―――●―――●―――●
/ / \ \ / / / \ \ \
○―g―● ●―――●―――● ●―d―○ ○―――●―――● ●―――●―d―● ○ ○―g―●―――●―――● ●―――●―d―○
/ \ \ / / \ / / / \ / / / \ / \ / / / / \ / / /
○ ● ●―――● ● ○ ○ ●―――● ●―――●―――● ☺ ○ ○―――●―g―●―――● ●―――●―――○
\ / / \ \ / \ g \ \ \ d / / / / /
○―――● ●―――●―――● ●―――○ ○ ●―――●―――●―――● ☺―――○ ●―――●―――●―――●
\ \ / / \ / \ /
●―――●―――●―――● ●―――●―――● ●―――●―――●
\ \ \ \ \ / \ /
●―――●―――●―――● ●―――● ●―――●
\ / \ \ \ \
●―――●―――● ●―――● ●―――●
b / b \ b \
○―――○ ○―――○ ○―――○
/ b / \ b / \ b
g=d b=h g=d ¬h∨¬h' g∨h'∨b
Le ciment entre les briques dépend de la nature des briques :
/ \ / \
――● ○ ――●―――○―― ●―――○ ●―――○――
/ \ / \ / / / \ / /
――● ☺ ○ ――●―――○―― ● ○ ● ○――
\ / / \ / \ /
☺―――○ ●―――○ ●
\ / \ /
Un des quatre cas fait intervenir un échelon supplémentaire qui change donc la valeur transmise.
Par exemple (a∨b∨¬c) ∧ (a∨c∨¬d) ∧ (¬a∨¬b∨d) se codera :
a∨b∨¬c a∨c∨¬d ¬a∨¬b∨d
☺―――☺―――☺―――☺―――☺―――☺ ☺―――☺―――☺
x e i \
●―――● ○―――○ ●―――● ☺
/ \ / / \ / / \ / /
●―――● ○―――○ ●―――● ☺
/ x' / e' / i' \
●―――●―――● ○―――○―――○ ●―――●―――● ☺
x' \ e' \ i' \ /
●―――●―――●―――● ○―――○―――○―――○ ●―――●―――●―――● ☺
\ \ \ \ \ \ / / / \
☺―a―●―――●―――● ●―――●―a―○―――○―――○ ○―――○―a―●―――● ●―――●―――● ☺
/ \ / / / \ / / / / / \ / / / / \ / / / a /
☺ ●―a―●―――● ●―――●―――○―a―○―――○ ○―――○―――●―――● ●―――●―a―●―――☺
\ / / / / / / \ \ \
☺ ●―――●―――●―――● ○―――○―――○―――○ ●―――●―――●―――●
/ \ y \ f \ j
☺ ●―――●―――● ○―――○―――○ ●―――●―――●
\ y / f / j /
☺ ●―――● ○―――○ ●―――●
/ \ y \ f \ j
☺ ●―――● ○―――○ ●―――●
\ y \ f \ j \
☺ ○―――○ ●―――● ○―――○
/ / \ / / f / \ /
☺ ○―――○ ●―――●―――● ○―――○
\ / y' f \ / j'
☺ ○―――○―――○ ●―――●―――●―――● ○―――○―――○
/ y' \ / / / / j' \
☺ ○―――○―――○―――○ ●―――●―――●―――● ○―――○―――○―――○
\ \ \ \ / / \ \ \ \ \
☺―b―○―――○―――○ ○―――○ ● ●―――●―――● ●―――○―b―○―――○ ○―――○
\ / / / \ / / b / \ \ / / / / / \ / / \
○―b―○―――○ ○―――○ ☺ ● ●―――● ● ○―――○―――○ ○―――○―b―☺
/ / / \ / / / \ \ b / / / \
○―――○―――○―――○ ☺―b―● ●―――●―――● ● ○―――○―――○―――○ ☺
\ z \ \ / / \ k /
○―――○―――○ ●―――●―――●―――● ○―――○―――○ ☺
z / \ \ \ \ k / \
○―――○ ●―――●―――●―――● ○―――○ ☺
\ z \ f \ k /
○―――○ ●―――●―――● ○―――○ ☺
z \ f / k \ \
●―――● ○―――○ ●―――● ☺
/ \ / / \ / / k /
●―――● ○―――○ ●―――●―――● ☺
/ z' / f' k \ \
●―――●―――● ○―――○―――○ ●―――●―――●―――● ☺
z' \ f' \ / / / / /
●―――●―――●―――● ○―――○―――○―――○ ●―――●―――●―――● ☺
/ / / \ \ \ / / \ \ \
☺―c―●―――● ●―――●―――●―c―○―――○―――○ ○―――○ ● ●―――●―――● ● ☺
/ \ / / \ / / / / / / \ / / c / \ \ / / \ /
☺ ●―――● ●―――●―c―●―――○―c―○―――○ ○―――○ ☺ ● ●―――● ● ☺
\ \ \ \ / / / \ / / / \ \ c
☺ ●―――●―――●―――● ○―――○―――○―――○ ☺―c―● ●―――●―――● ●
/ \ t \ g \ \ / /
☺ ●―――●―――● ○―――○―――○ ●―――●―――●―――●
\ t / g / \ \ \ \
☺ ●―――● ○―――○ ●―――●―――●―――●
/ \ t \ g \ k
☺ ●―――● ○―――○ ●―――●―――●
\ t \ g \ k /
☺ ○―――○ ●―――● ○―――○
/ / t / \ / / \ /
☺ ○―――○―――○ ●―――● ○―――○
\ t \ / g' / k'
☺ ○―――○―――○―――○ ●―――●―――● ○―――○―――○
/ / / / / g' \ k' \
☺ ○―――○―――○―――○ ●―――●―――●―――● ○―――○―――○―――○
\ / / \ \ / / / \ \ \
☺ ○ ○―――○―――○ ○―d―●―――● ●―――●―――●―d―○―――○―――○ ○―――○
\ d \ \ / / / / \ / / / / / / \ / / d
☺ ○ ○―――○ ○ ●―――● ●―――●―d―●―――○―d―○―――○ ○―――○―――☺
\ / / \ \ / \ \ \ / / / \
○ ○―――○―――○ ○ ●―――●―――●―――● ○―――○―――○―――○ ☺
\ \ / / \ h \ l /
○―――○―――○―――○ ●―――●―――● ○―――○―――○ ☺
\ \ \ \ h / l / \
○―――○―――○―――○ ●―――● ○―――○ ☺
\ t \ h \ l /
○―――○―――○ ●―――● ○―――○ ☺
t / h \ l \ \
☺―――☺ ☺―――☺ ☺―――☺ ☺
\ \ \ /
☺―――☺―――☺―――☺―――☺―――☺ ☺―――☺―――☺
La clause a∨b∨¬c peut se traduire de différentes façons :
∃x, ∃y, ∃z, ∃t, x ∧ (¬x∨a∨y) ∧ (¬y∨b∨z) ∧ (¬z∨¬c∨t) ∧ ¬t
∃x, ∃x', ∃y, ∃y', ∃z, ∃z', ∃t, x ∧ (¬x∨¬x') ∧ (x'∨a∨y) ∧ (¬y∨¬y') ∧ (y'∨b∨z) ∧ (¬z∨¬z') ∧(z'∨¬c∨t) ∧ ¬t
∃x, ∃x', ∃y, ∃y', ∃z, ∃z', ∃t, x ∧ (¬x∨¬x') ∧ (x'+a+y≥1) ∧ (¬y∨¬y') ∧ (y'+b+z≥1) ∧ (¬z∨¬z') ∧(z'+c+t≥1) ∧ ¬t
∃x, ∃x', ∃y, ∃y', ∃z, ∃z', ∃t, x ∧ (¬x∨¬x') ∧ (x'+a+y=1) ∧ (¬y∨¬y') ∧ (y'+b+z=1) ∧ (¬z∨¬z') ∧(z'+c+t=1) ∧ ¬t (3)
∃x, ∃x', ∃y, ∃y', ∃z, ∃z', ∃t, x ∧ (¬x∨¬x') ∧ (a=¬x'∧¬y) ∧ (¬y∨¬y') ∧ (b=¬y'∧¬z) ∧ (¬z∨¬z') ∧(c=¬z'∧¬t) ∧ ¬t (4)
Un circuit solution pour le voyageur de commerce, nous donne des valeurs de a, b, c, x, x', ... et t vérifiant (4).
Réciproquement des valeurs de a, b, c, x, x', ... et t vérifiant (3), nous donnent un remplissage de la colonne
correspondant à la clause a∨b∨¬c avec un losange critique dans chacune des quatre briques, qui permet
de nous assurer que tous les chemins passant dans cette colonne sont dans le même circuit.
Comme les formules (3) et (4) sont toutes les deux équivalentes à a∨b∨¬c, et que l'on a les mêmes équivalences
pour les autres clauses et les autres colonnes, on voit que notre problème de voyageur de commerce a une solution
ssi le prédicat (a∨b∨¬c) ∧ (a∨c∨¬d) ∧ (¬a∨¬b∨d) est satisfiable.
On peut prendre des briques rectangulaires plus petites 4x(4√3) au lieu de 5x(5√3) quand on force l'usage
de certaines arêtes. Une arête forcée ●―1―● reliant les sommets i et j donnera deux capteurs
P_i2ε+P_j(1-2ε) proche de P_j et P_j2ε+P_i(1-2ε) proche de P_i.
Le coût attendu pour un circuit doit être diminué de (1-ε)²-(1-2ε)² pour chaque arête forcée.
On peut bien sûr faire un filtre en forçant un échelon, sans l'allonger. Le ruban central d'un croisement de
deux rubans et le ruban situé entre deux croisements superposés peuvent alors être tournés d'un quart de tour,
ce qui gagne deux rangées de villes en hauteur.
La construction suivante quand elle est entourée de quatre rubans valides code (g=d) ∧ (1≤g+h+b≤2).
Si on ajoute un déclassement sur le ruban du haut et un sur celui du bas, on code donc (g=d) ∧ (g∨h∨b)
h H | H | H
●―――●―――● ●―G―●―?―● ●―g―●―?―●
| | | G ? ? g ? ?
G―●―――●―――●―d G―●―――●―?―●―― ――●―――●―?―●―d
| 1 | | b D g B |
g―●―――●―――●―D ――●―b―●―――●―D g―●―――●―B―●――
| | | b | | | | B
●―――●―――● ●―b―●―b―● ●―B―●―B―●
B b | b B |
Les cinq briques possibles sont :
●―――● ○―――○―――○ ●―――●―――● ○―――○ ●―――●―――● ○―――○ ●―――●―――●
/ / 1 \ 1 1 \ 1 / / \ / / / \ /
○―――○ ●―――●―――● ○―――○―――○ ●―――● ○―――○ ●―――● ○―――○
\ / \ / \ / \ \ / \ \ / \ \ / \ \ / \
○―1―○ ●―――●―――●―――● ○―――○―――○―――○ ●―1―● ○―1―○ ●―1―● ○―1―○
/ \ \ \ \ \ \ \ \ \ / \ / \ / \ / \
○―――○―――○ ●―――●―――●―――●―――○―――○―――○―――○ ●―――●―――● ○―――○―――○ ●―――●―――● ○―――○―――○
\ \ \ / / \ / \ \ / / / \ \ \ / / / \ \ \
――○―――○―――○―――○―――☺ ●―――●―――● ○―――○―――○ ●―――●―――●―――●―――○―――○―――○―――○―――●―――●―――●―――●―――○―――○―――○―――○
/ / 1 / / 1 / 1 1 / 1 / 1 / / / / 1 / / 1 / / / / 1 /
○―――○―――○―――○―――☺ ●―――●―――● ○―――○―――○ ●―――●―――●―――●―――○―――○―――○―――○―――●―――●―――●―――●―――○―――○―――○―――○――
/ / / \ \ / \ / / \ \ \ / / / \ \ \ / / /
○―――○―――○ ●―――●―――●―――●―――○―――○―――○―――○ ●―――●―――● ○―――○―――○ ●―――●―――● ○―――○―――○
\ / / / / / / / / / \ / \ / \ / \ /
○―1―○ ●―――●―――●―――● ○―――○―――○―――○ ●―1―● ○―1―○ ●―1―● ○―1―○
\ \ \ / \ / \ \ \ \ / \ / \
○―――○ ●―――●―――● ○―――○―――○ ●―――● ○―――○ ●―――●―――● ○―――○―――○
a∨b∨¬c a∨c∨¬d ¬a∨¬b∨d
☺―――☺―――☺―――☺ ☺―――☺
/ \ / \
●―――● ○―――○ ●―――● ☺
\ / \ \ / \ \ / \ \
●―1―● ○―1―○ ●―1―● ☺
/ \ / \ / \ /
●―――●―――● ○―――○―――○ ●―――●―――● ☺
\ \ \ \ \ \ / / / \
☺―a―●―――●―――●―――●―a―○―――○―――○―――○―a―●―――●―――●―――● ☺
/ \ / / 1 / / / 1 / / 1 / / a /
☺ ●―a―●―――●―――●―――○―a―○―――○―――○―――●―――●―――●―a―●―――☺
\ / / / / / / \ \ \
☺ ●―――●―――● ○―――○―――○ ●―――●―――●
/ \ / \ / \ /
☺ ●―1―● ○―1―○ ●―1―●
\ \ \ / \ \ \
☺ ●―――● ○―――○―――○ ●―――●
/ / / 1 \ 1 / /
☺ ○―――○ ●―――●―――● ○―――○
\ \ / \ / \ \ / \
☺ ○―1―○ ●―――●―――●―――● ○―1―○
/ / \ \ \ \ \ / \
☺ ○―――○―――○ ●―――●―――●―――● ○―――○―――○
\ \ \ \ / / \ \ \ \ \
☺―b―○―――○―――○―――○―b―☺ ●―――●―――● ○―b―○―――○―――○
\ / / 1 / / 1 / 1 / / 1 / \
○―b―○―――○―――○―――☺ ●―――●―――● ○―――○―――○―――○―b―☺
/ / / \ \ / / / / / \
○―――○―――○ ●―――●―――●―――● ○―――○―――○ ☺
\ / / / / / \ / /
○―1―○ ●―――●―――●―――● ○―1―○ ☺
\ \ \ / / \ \
○―――○ ●―――●―――● ○―――○―――○ ☺
/ / \ / 1 \ 1 /
●―――● ○―――○ ●―――●―――● ☺
\ / \ \ / \ / \ \
●―1―● ○―1―○ ●―――●―――●―――● ☺
/ \ / \ \ \ \ \ \
●―――●―――● ○―――○―――○ ●―――●―――●―――● ☺
/ / / \ \ \ / / \ \ \
☺―c―●―――●―――●―――●―c―○―――○―――○―――○―c―☺ ●―――●―――● ☺ ☺
/ \ / 1 / / / / 1 / / 1 / 1 / c /
☺ ●―――●―――●―c―●―――○―c―○―――○―――○―――☺ ●―――●―――● ☺―――☺
/ \ \ \ / / / a \ / /
☺ ●―――●―――● ○―――○―――○ ●―――●―――●―――●
\ \ / \ / / / / /
☺ ●―1―● ○―1―○ ●―――●―――●―――●
/ / \ \ \ \ /
☺ ●―――●―――● ○―――○ ●―――●―――●
\ 1 \ 1 / / \ /
☺ ○―――○―――○ ●―――● ○―――○
/ / \ \ / \ \ / \
☺ ○―――○―――○―――○ ●―1―● ○―1―○
\ \ \ \ \ / \ / \
☺ ○―――○―――○―――○ ●―――●―――● ○―――○―――○
\ / / \ \ \ \ \ \ \ \
☺―d―☺ ○―――○―――○ ●―d―●―――●―――●―――○―d―○―――○―――○
\ / 1 / 1 / / 1 / / / 1 / \
☺ ○―――○―――○ ●―――●―――●―――●―d―○―――○―――○―――○―d―☺
\ \ / / / / / / / / \
○―――○―――○―――○ ●―――●―――● ○―――○―――○ ☺
/ / / / \ / \ / /
○―――○―――○―――○ ●―1―● ○―1―○ ☺
\ / \ \ \ \ \
○―――○―――○ ●―――● ○―――○ ☺
\ / \ /
☺―――☺―――☺―――☺―――☺ ☺―――☺―――☺
]]>