Forum général.cherche-logiciel Générer un tableau à partir de contraintes

Posté par  .
Étiquettes : aucune
0
9
déc.
2005
Bonjour,
Après trois heures de recherches infructueuses sur sourceforge, freshmeat et google, je me retourne vers le forum.
Je cherche un logiciel qui pemettrait de remplir un tableau à partir de contraintes fixées sur les cellules.

Par exemple:

En entrée, je donne:
\ABCDE
a
b
c


somme de la ligne a = 19
somme de la colonne A=10
aB=3
pas de 5 sur la ligne a
chaque éléments de chaque ligne est unique
bE=5
cD différent de 2


En sortie, parmi les possible, le programme me donne:
\ABCDE
a13249
b78965
c21364

Ce que j'ai trouvé de plus proche, c'est FET, pour générer des horaires dans une école:
http://www.lalescu.ro/liviu/fet/

Mais j'aimerais trouver quelque chose de plus flexible.
  • # Programmation par contraintes

    Posté par  . Évalué à 5.

    Ce que tu décris ressemble à un premier TP de programmation par contraintes. D'autant que j'imagine que les nombres que tu cherches sont des chiffres bien que tu ne l'as pas précisé, donc c'est faisable avec des solveurs de type FD, qui sont très courants. C'est une classe de solveurs qui marchent sur les domaines finis (Finite Domain, d'où leur nom), c'est à dire sur des ensembles de valeurs énumérables, du style "les entiers de 0 à 1000" (par opposition à "les entiers" tout court).

    Tu trouveras des solveurs pour différents langage de programmation :
    - en programmation logique, tu en as d'intégrés dans pas mal de Prologs, genre dans GNU Prolog [1], Ciao Prolog [2] (libre aussi, et perso je l'aime bien), ou encore Eclipse Prolog [3] (excellent, mais pas complètement libre, ça dépend des morceaux). Je sais plus si y'en a dans SWI Prolog, je le connais à peine.
    - en programmation impérative, ça existe sous forme de bibliothèque pour différents langages : C++ mais j'en n'ai plus de nom en tête, Python [4,5], et probablement bien d'autres.

    En gros, comme le nom l'indique, c'est un mode de programmation qui consiste (essentiellement) à déclarer des contraintes liants entre elles les valeurs de variables. À la syntaxe prêt, ton énnoncé là haut est un programme (désolé les puristes pour les affreuses simplifications que je vais faire). Il est exécuté par une moulinette qui à l'aide des contraintes réduit les domaines de valeurs possibles des variables, pour converger vers une/des solution(s).

    C'est un peu comme quand tu joues au Sudoku : de voir qu'il y a déjà un 9 dans une case te permet d'exclure cette valeur pour les autres de la même ligne ou colonne, et pour le reste du carré, ce qui te permet de déduire la valeur d'une autre case qui n'avait plus beaucoup de possibilité, et elle en influence une autre encore, etc. ; les règles du Sudoku sont en fait un ensemble de contraintes, et l'on raisonne avec de la même façon que fonctionnent ces solveurs, en cherchant à en tirer toutes les conséquences possibles pour arriver à l'unique solution. Évidemment, au Sudoku comme en programmation par contrainte, l'exploitation immédiate et un peu triviale des contraintes directes entre les variables ne suffit pas forcement à aboutir. C'est là qu'intervient l'énumération bourrine des valeurs, qui est possible puisque leur domaine est fini : on prend par exemple une case qui peut valoir soit 2 soit 5, on fait l'hypothèse qu'elle vaut 2, et on voit jusqu'où ça peut nous mener ensuite (à une solution, ou à un échec).

    Si tu googles "programmation contraintes", tu trouveras pas mal de cours (c'est au niveau maitrise ou assimilé qu'on enseigne ça souvent), plutôt orientés Prolog en général ("programmation logique avec contraintes" donc), et qui devraient t'aider à t'y mettre sans trop de peine.

    Amuses toi bien, tu verras que c'est vraiment un mode de programmation extrêmement plaisant, concis, et efficace, enfin pour les problèmes qui s'y prêtent.

    [1] http://pauillac.inria.fr/~diaz/gnu-prolog/
    [2] http://clip.dia.fi.upm.es/Software/Ciao/
    [3] http://www.icparc.ic.ac.uk/eclipse/
    [4] http://www.logilab.org/projects/constraint
    [5] http://codespeak.net/~niemeyer/constraint/
    • [^] # Re: Programmation par contraintes

      Posté par  . Évalué à 3.

      En relisant ton message, je vois que tu cherches "un logiciel", et pas vraiment un langage. Bon, donc je suis limite off-topic, mais en fait non, pas vraiment : on n'a finalement pas besoin d'un logiciel bien paufiné quand on a un bon interpréteur Prolog sous la main... Voilà ton problème en Prolog Eclispe (le seul que j'ai sous la main). Le gros du code servirait pour n'importe quel autre problème du même type, donc c'est fait une fois pour toutes, et seul le prédicat "contraintes(M)" est spécifique à ton cas :
      % chargement du solveur
      :- lib(fd).
      
      % tableau 2D -> ligne (liste)
      ligne(M,I,L) :-
      	dim(M,[_,Y]),
      	length(L,Y),
      	(for(J,1,Y), foreach(A,L), param(M,I) do
      		A is M[I,J]).
      
      % tableau 2D -> colonne (liste)
      colonne(M,J,C) :-
      	dim(M,[X,_]),
      	length(C,X),
      	(for(I,1,X), foreach(A,C), param(M,J) do
      		A is M[I,J]).
      
      % contrainte sur la somme des éléments d'une liste
      sigma(L,S) :-
      	(foreach(X,L), fromto(0,A,B,S) do
      		B #= A + X).
      
      % liste de toutes les variables d'un tableau 2D
      variables(M,V) :-
      	dim(M,[X,_]),
      	(for(I,1,X), fromto([],V1,V2,V), param(M) do
      		ligne(M,I,L), append(V1,L,V2)).
      
      % impose un domaine sur toutes les variables
      domaine(M,D) :-
      	variables(M,V), V::D.
      
      % les contraintes particuulières
      contraintes(M) :- 
      	% le tableau est de dimension 3x5
      	dim(M,[3,5]),
      	% avec des valeurs entières dans [1,9]
      	domaine(M,[1..9]),
      	% AB vaut 3
      	AB is M[1,2], AB #= 3,
      	% BE vaut 5
      	BE is M[2,5], BE #= 5,
      	% CD ne vaut pas 2
      	CD is M[3,4], CD #\= 2,
      	% la somme de la ligne A est 19...
      	ligne(M,1,LigA),
      	sigma(LigA,19),
      	% ...et elle ne comporte pas de 5
      	(foreach(X,LigA) do X #\= 5),
      	% la somme de la colonne A est 10
      	colonne(M,1,ColA),
      	sigma(ColA,10),
      	% les valeurs d'une même ligne sont distinctes
      	(for(I,1,3), param(M) do
      		ligne(M,I,L),
      		alldifferent(L)).
      
      probleme(M) :-
      	% on impose des contraintes
      	contraintes(M),
      	% et on énumère les valeurs possibles des variables
      	variables(M,V),
      	labeling(V).
      
      Pour obtenir les solution, je demande "probleme(M)" à Prolog, et il me répond :
      ?- probleme(M).
      M = []([](1, 3, 2, 4, 9), [](1, 2, 3, 4, 5), [](8, 1, 2, 3, 4))
      Yes (0.00s cpu, solution 1, maybe more)
      M = []([](1, 3, 2, 4, 9), [](1, 2, 3, 4, 5), [](8, 1, 2, 3, 5))
      Yes (0.01s cpu, solution 2, maybe more)
      (et j'arrête là, mais il y a évidemment beaucoup d'autres solutions)
      • [^] # Re: Programmation par contraintes

        Posté par  . Évalué à 2.

        Merci beaucoup pour cette réponse détaillée.
        Je verrai ce que je peux en faire, mais ça m'aide déjà beaucoup.

        J'aurais peut-être dû préciser que la raison pour laquelle je cherche un tel soft, c'est pour m'aider dans des prises de décisions complexes incluant un grand nombre de facteurs dans mon boulot.
        Si c'est réellement du niveau 1er lab de TD, je devrais effectivement pouvoir faire ça moi-même.

        Tom
        • [^] # Re: Programmation par contraintes

          Posté par  . Évalué à 2.

          c'est pour m'aider dans des prises de décisions complexes incluant un grand nombre de facteurs dans mon boulot.
          C'est vague, mais ça sonne bien comme ce qui est effectivement un domaine de prédilection de la programmation par contraintes. Un aspect dont je n'ai pas parlé, mais qui est lié, c'est que bien souvent le but réel d'un programme par contraintes n'est pas trouver toutes les solutions possibles, mais plutôt une solution optimale selon un certain critère. Par exemple, on aurait pu chercher une solution minimisant la somme de toutes les variables :
          probleme(M,S) :-
          	% on impose des contraintes
          	contraintes(M),
          	% et on cherche une solution minimisant la somme des variables
          	variables(M,V),
          	sigma(V,S),
          	min_max(labeling(V),S).
          
          Qui nous donne :
          ?- probleme(M, S).
          M = []([](1, 3, 2, 4, 9), [](4, 1, 2, 3, 5), [](5, 1, 2, 3, 4))
          S = 49
          Yes (0.71s cpu)
          
          C'est le genre de truc qui est utilisable dans plein de domaines, que ce soit de l'ingénierie, de la finance, de la logistique, etc., souvent avec en tête de minimiser un coût, une durée, etc. Et les problèmes de la vraie vie mettent facilement en jeu des milliers de variables et dix ou cent fois plus de contraintes encore, sans que ce soit forcement une difficulté si le problème s'y prête bien.
          Si c'est réellement du niveau 1er lab de TD, je devrais effectivement pouvoir faire ça moi-même.
          J'en ai peut-être rajouté un tout petit peu : disons que ça peut être un premier TP contraintes pour des gens qui aurait déjà des notions de Prolog. Je dis ça parce que là il n'y a pas d'écueuil, juste des contraintes simples sur des variables ("machin ne vaut pas truc") ou listes de variables ("tous les éléments de cette listes sont différents"). Le plus compliqué dans mon programme vite fait, c'est finalement la manipulation du tableau (récupérer une colonne, etc.), mais ça c'est du Prolog tout court, ça n'est pas spécifique à la programmation par contraintes.
          • [^] # Re: Programmation par contraintes

            Posté par  . Évalué à 2.

            > C'est vague

            Un exemple concret, comment distribuer le travail entre 9 ingénieurs sur une semaine.
            9 ingénieurs
            10 demi journées
            5 domaines à couvrir

            contraintes "hard"
            chaque ingénieur peut couvrir 3 domaines définis (selon ses compétences)
            chaque domaine doit être couvert par un ingénieur chaque demi-journée (ça s'appelle un shift)
            les ingénieurs auront chacun un nombre équivallent de shifts (plus ou moins 1). 6 par semaine environ
            un ingénieur peut être absent (1 ou plusieurs jours) et donc ne pas prendre de shifts ces jours-là

            contraintes "soft"
            certains ingénieurs préfèrent les shifts du matin, d'autres, l'après-midi
            certains ingénieurs préfèrent regrouper les shifts (couvrir plusieurs domaines sur une matinée), d'autres préfèrent les disperser
            au moins deux jours sans shift par ingénieur
            pas plus de la moitié des shifts d'une semaine pour un ingénieur ne devraient couvrir le même domaine

            Toutes les contraintes ne seront pas facile à formuler, mais d'après ce que tu me dis, Prolog serait la voie à explorer

            Encore merci,
            Tom
            • [^] # Re: Programmation par contraintes

              Posté par  . Évalué à 1.

              Si tu ne veux ou peux pas utiliser prolog, l'excellente bibliothèque lp_solve (lpsolve.sourceforge.net) est très facilement interfaçable avec la plupart des langages.

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n’en sommes pas responsables.