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

• # Programmation par contraintes

  Posté par tgl le 09 décembre 2005 à 02:37. É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 tgl le 09 décembre 2005 à 03:22. É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 Tom D le 09 décembre 2005 à 08:52. É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 tgl le 09 décembre 2005 à 09:31. É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 Tom D le 09 décembre 2005 à 11:27. É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 norbs le 09 décembre 2005 à 23:06. É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 à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.