TD Exercice 5

Ce
problème est notamment utilisé en Tomographie.
Modéliser le problème et trouver la solution
au problème en utilisant le solveur Choco 2.0.
Solution
Modèle 1
- On
utilise les contraintes génériques :
- Une
variable (0/1) par case
-
Une contrainte par ligne / colonne :
- Vérifiant
lexistence des blocs (séparation
blocs vides)
- Vérifiant
leur longueur
Voici
le code java en Choco
2.0 de ce premier modèle :
import
choco.kernel.model.Model;
import choco.kernel.model.variables.integer.IntegerVariable;
import choco.kernel.solver.Solver;
import choco.kernel.solver.constraints.integer.extension.TuplesTest;
import choco.cp.model.CPModel;
import choco.cp.solver.CPSolver;
import choco.Choco;
public
class TomoAC {
static
int nbCol = 10;
static
int nbLig = 10;
static
int[][] colBlocs = new int[][]{

new
int[]{2, 3},

new
int[]{1, 2},

new
int[]{1, 1, 1, 1},

new
int[]{1, 2},

new
int[]{1, 1, 1, 1},

new
int[]{1, 2},

new
int[]{2, 3},

new
int[]{3, 4},

new
int[]{8},

new
int[]{9},
};
static
int[][] ligBlocs = new int[][]{

new
int[]{3, 6},

new
int[]{1, 4},

new
int[]{1, 1, 3},

new
int[]{2},

new
int[]{3, 3},

new
int[]{1, 4},

new
int[]{2, 5},

new
int[]{2, 5},

new
int[]{1, 1},

new
int[]{3},
};
public
static void main(String[] args)
{

Model
m = new CPModel();

IntegerVariable[][]
vars =


Choco.makeIntVarArray("case",
nbCol, nbLig, 0, 1);

for
(int i = 0; i < ligBlocs.length; i++)

{


IntegerVariable[]
ligne = new IntegerVariable[nbCol];


for
(int j = 0; j < ligne.length; j++)


{



ligne[j]
= vars[j][i];


}


int[]
blocs = ligBlocs[i];


postConstraint(m,
ligne, blocs);

}

for
(int i = 0; i < colBlocs.length; i++)

{


IntegerVariable[]
colonne = new IntegerVariable[nbLig];


for
(int j = 0; j < colonne.length; j++)


{



colonne[j]
= vars[i][j];


}


int[]
blocs = colBlocs[i];


postConstraint(m,
colonne, blocs);

}

Solver
s = new CPSolver();

s.read(m);

s.solve();

s.printRuntimeSatistics();

for
(int i = 0; i < nbLig; i++)

{


for
(int j = 0; j < nbCol; j++)


{



IntegerVariable
v = vars[j][i];



System.out.print(s.getVar(v).getVal()
== 0 ? " " : "#");


}


System.out.println();

}
}
private
static void postConstraint(Model m,






IntegerVariable[] ligne, final int[] blocs)
{

m.addConstraint(


Choco.relationTupleAC(ligne,
new TuplesTest()


{



public
boolean checkTuple(int[] tuple)



{




int
currentBloc = 0;




int
i = 0;




while
(i < tuple.length)




{





while
(i < tuple.length && tuple[i] == 0) i++;





if
(currentBloc == blocs.length && i == tuple.length)






return
true;





if
(currentBloc >= blocs.length) return false;





int
l = 0;





while
(i < tuple.length && tuple[i] == 1)





{






i++;






l++;





}





if
(l != blocs[currentBloc]) return false;





currentBloc++;





if
(currentBloc == blocs.length && i == tuple.length)






return
true;




}




return
false;



}


})

);
}
}
Solution
Modèle 2
- Utiliser
la contrainte Regular :
- Il
sagit dexpression régulière
- Par
exemple pour 1,4,3
0* 1 0+ 1111 0+ 111 0*
- Rappel
: dans une Regexp
+ = apparait au moins une fois
* = apparait un nombre quelconque de fois.
Voici
le code java en Choco
2.0 de ce second modèle :
import
choco.cp.model.CPModel;
import choco.cp.solver.constraints.global.regular.DFA;
import choco.cp.solver.CPSolver;
import choco.kernel.model.Model;
import choco.kernel.model.variables.integer.IntegerVariable;
import choco.kernel.solver.Solver;
import choco.Choco;
public
class TomoReg
{
static
int nbCol = 10;
static
int nbLig = 10;
static
int[][] colBlocs = new int[][]{

new
int[]{2, 3},

new
int[]{1, 2},

new
int[]{1, 1, 1, 1},

new
int[]{1, 2},

new
int[]{1, 1, 1, 1},

new
int[]{1, 2},

new
int[]{2, 3},

new
int[]{3, 4},

new
int[]{8},

new
int[]{9},
};
static
int[][] ligBlocs = new int[][]{

new
int[]{3, 6},

new
int[]{1, 4},

new
int[]{1, 1, 3},

new
int[]{2},

new
int[]{3, 3},

new
int[]{1, 4},

new
int[]{2, 5},

new
int[]{2, 5},

new
int[]{1, 1},

new
int[]{3},
};
public
static void main(String[] args)
{

Model
m = new CPModel();

IntegerVariable[][]
vars =


Choco.makeIntVarArray("case",
nbCol, nbLig, 0, 1);

for
(int i = 0; i < ligBlocs.length; i++)

{


int[]
blocs = ligBlocs[i];


StringBuilder
sb = new StringBuilder();


sb.append("0*");


for
(int j = 0; j < blocs.length; j++)


{



if
(j > 0) sb.append("0+");



int
bloc = blocs[j];



for
(int n = 0; n < bloc; n++) sb.append("1");


}


sb.append("0*");


IntegerVariable[]
ligne = new IntegerVariable[nbCol];


for
(int j = 0; j < ligne.length; j++)


{



ligne[j]
= vars[j][i];


}


m.addConstraint(



Choco.regular(new
DFA(sb.toString(), nbCol), ligne));

}

for
(int i = 0; i < colBlocs.length; i++)

{


int[]
blocs = colBlocs[i];


StringBuilder
sb = new StringBuilder();


sb.append("0*");


for
(int j = 0; j < blocs.length; j++)


{



if
(j > 0) sb.append("0+");



int
bloc = blocs[j];



for
(int n = 0; n < bloc; n++) sb.append("1");


}


sb.append("0*");


IntegerVariable[]
colonne = new IntegerVariable[nbLig];


for
(int j = 0; j < colonne.length; j++)


{



colonne[j]
= vars[i][j];


}


m.addConstraint(



Choco.regular(new
DFA(sb.toString(), nbLig), colonne));

}

Solver
s = new CPSolver();

s.read(m);

s.solve();

s.printRuntimeSatistics();

for
(int i = 0; i < nbLig; i++)

{


for
(int j = 0; j < nbCol; j++)


{



IntegerVariable
v = vars[j][i];



System.out.print(s.getVar(v).getVal()
== 0 ? " " : "#");


}


System.out.println();

}
}
}
Voici
le plan de cette présentation sur la programmation par contraintes
- Les
notions de base
:
- Quelques
notions avancées :
- Quelques
exemples pour utiliser la P.P.C. :
Cette page
a été co-réalisée avec Guillaume
Rochart, docteur en mathématiques dans mon équipe de
recherche au Bouygues
e-lab.10/03/2009.
