Aller au menu - Aller au contenu

Découverte de la programmation par contraintes

Pour accéder à cette section
Connectez-vous !
connexion_rpx
Page 1 
Pseudo Commentaire
Page 1 
Hors ligne JeromeJ # Posté le 02/12/2009 à 01:16:15
Cet espace est trop petit pour
Avatar

 J'hésite presque: est-ce qu'on apprend vraiment la programmation par contraire ou alors apprenons-nous comment s'utilise des bibliothèques comme Gecode qui utilisent ce procédé ?

Sinon, sujet très intéressant et tutos assez bien rédigé :)
www.olissea.com
Site communautaire et multi-thème

Olissea recrute ! Cliquer ici pour voir le sujet.

Olissea c'est: Tchat (à venir), Forums, Articles, Programmes, etc. (+ Tout ce que vous souhaitez)
 
Hors ligne spider-mario # Posté le 02/12/2009 à 07:42:36
Avatar

Ville : Montigny-lès-cormeilles
Pays : France métropolitaine
Études : INSA Rouen

 Le lien vers Wikipedia à la fin ne fonctionne pas, tu as dû mettre
Code : Zcode
1
<lien type="wikipedia" url="http://fr.wikipedia.org/wiki/Carré_magique_(mathématiques)">wikipedia</lien>

(résultat : wikipedia) au lieu de
Code : Zcode
1
<lien type="wikipedia" url="Carré magique (mathématiques)">wikipedia</lien>

(résultat : wikipedia).

Tuto très intéressant par ailleurs ;)
Hors ligne Rushou # Posté le 02/12/2009 à 10:11:54
Avatar

Études : ENS Lyon

 Coucou :) ,

spider-mario > Merci pour la correction ! J'avais testé pourtant...

JeromeJ > Ce tuto est une simple solution "toute faite" pour les carrés magiques. C'est ce qui fait que je n'entre dans aucun détail de la prog' par contraintes. Donc oui, c'est plus une découverte de Gecode que du paradigme derrière... Tu es quand même obligé de découvrir quelques concepts si tu veux utiliser cette bibliothèque et c'est un but du tuto.
mini-tuto prog' par contraintes
 
Hors ligne The Camel # Posté le 02/12/2009 à 19:57:23

Ville : Bruxelles
Pays : Belgique

 Bonjour,

J'ai décelé une petite erreur dans le paragraphe suivant :

Citation

Pour les carrés magiques on devrait donc commencer par dire qu'on se place sur un tableau d'entiers carreMag de taille n*n, chaque entier ayant pour domaine les nombres de 1 jusqu'au nombre de cases du tableau (soit n*n). Le domaine d'une variable est l'ensemble des valeurs qu'elle peut prendre. Dans un carré magique, chaque case peut contenir chaque nombre, tant qu'on a pas commencé à le résoudre. Donc ici les variables de notre tableau doivent bien avoir comme valeurs possibles tout les nombres de 1 à n.


Si le carré est de taille n*n, il y a n² cases (n² = n*n). Donc les variables de notre tableau doivent bien avoir comme valeurs possibles tout les nombres de 1 à n².

Sinon, très bon tuto ;)
Hors ligne Rushou # Posté le 02/12/2009 à 22:28:28
Avatar

Études : ENS Lyon

 The Camel > Ahah, c'était pour voir si t'étais attentif :-° (excuse bidon passe-partout).
Merci, je corrige ça !
mini-tuto prog' par contraintes
 
Hors ligne bluestorm # Posté le 09/12/2009 à 14:25:28
dont ask to ask
Avatar
Groupe : Anciens
Flux RSS
close

Motivé par le topic sur une lib Python, j'ai décidé de voir ce que ça donne en OCaml, avec la lib Facile (jamais fait de programmation par contraintes avant) :
Code : OCaml
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
open Facile
open Easy

let carre n =
  let carre = Fd.array (n * n) 1 (n * n) in
  let case i j = carre.(i * n + j) in
  Cstr.post (Alldiff.cstr carre);
  let sum_cstr = i2e ((n * (n*n + 1)) / 2) in
  let post_sum f =
    let band = Array.init n (fun k -> let (i, j) = f k in case i j) in
    Cstr.post (Arith.sum_fd band =~ sum_cstr) in
  for k = 0 to n - 1 do
    post_sum (fun j -> (k,j)); (* ligne *)
    post_sum (fun i -> (i,k)) (* colonne *)
  done;
  post_sum (fun i -> (i,i)); (* diagonales *)
  post_sum (fun i -> (i,n-1-i));  
  
  if not (Goals.solve (Goals.Array.labeling carre))
  then print_endline "pas de solution"
  else for i = 0 to n - 1 do
         for j = 0 to n - 1 do
           Printf.printf "%3d " (Fd.elt_value (case i j))
         done;
         print_newline ()
       done
  
let () = carre (read_int ())
big tuto algorithmique | tuto récursivité [PHP] | tuto typage | textes divers

Ours & Hippy
— le blog
 
Hors ligne Rushou # Posté le 09/12/2009 à 15:31:20
Avatar

Études : ENS Lyon

 bluestorm > Elle semble bien cette bibli OCaml !

Pour information, il existe bien entendu beaucoup de languages/bibliothèques intégrant la prog' par contraintes, dont voici quelques exemples parmis les plus connus ou intéressants.
  • Choco, une bibli Java
  • mozart, langage
  • Comet, langage aussi
  • SICStus Prolog (ou autre Prolog), de la prog' logique avec possibilité de faire de la prog' par contraintes.

Auquels on peut ajouter FaCiLe et Gecode.

J'ai choisi d'utiliser Gecode pour pas mal de raisons (plus ou moins bonnes). Déjà c'est libre, gratuit, multiplateforme et maintenu (dernière version le 30 novembre 2009). C'est performant : Gecode fait aussi bien voir mieux que les systèmes sortis de l'industrie. C'est ce que je connais le mieux. Et enfin, j'espère que le fait que ce soit du C++ attire plus de gens.

J'aimerais avoir vos avis quand à un possible changement de support pour le big-tuto que j'envisage sur le même sujet.

P.S. : pour l'anecdote, des travaux sont fait en ce moment pour utiliser Haskell avec Gecode. Miam :p .
mini-tuto prog' par contraintes
 
Hors ligne bluestorm # Posté le 09/12/2009 à 23:53:40
dont ask to ask
Avatar
Groupe : Anciens
Flux RSS
close

Oui enfin, l'intérêt de la lib Haskell c'est pas du tout son backend Gecode, c'est surtout sa présentation unifiée et composable des différentes stratégies de recherche et de résolution.

J'ai envisagé d'écrire l'exemple en Haskell avec cette lib en vérité, mais je me suis dit que l'exemple ne correspondait pas vraiment à son "marché", les problèmes pour lesquels elle est intéressante.

Ce serait amusant de tenter en Prolog, langage qui est quand même assez adapté pour ce genre de choses.
big tuto algorithmique | tuto récursivité [PHP] | tuto typage | textes divers

Ours & Hippy
— le blog
 
Hors ligne Alp # Posté le 10/12/2009 à 02:06:48

Je pense que ceci pourrait être rajouté à la fin étant donné la qualité de la lib concernée (Castor) par l'article en question : http://come-david.developpez.com/tutoriels/castor/
Blog (EN - nouveau) - Mes articles - FAQ C++0x - Conseils sur le C++ - La meilleure FAQ du monde - Le site du commité C++

Nouveau Le guide pour bien débuter en C++
 
Hors ligne Rushou # Posté le 11/12/2009 à 12:52:57
Avatar

Études : ENS Lyon

 Alp > Non, je ne pense pas : Castor c'est de la programmation logique, ce qui n'est pas de la prog' par contraintes.

bluestorm > J'ai pas bien compris ce que tu dis être l'intêret de la bibli Hsakell. Ce que j'ai compris ce qu'ils veulent utiliser Haskell pour coder bien et Gecode pour l'efficacité (l'autre backend existant servant de test pour comparer, si j'ai bien suivi).
Dans l'intro du dernier papier sur MCP, ils expliquent qu'ils tirent le meilleur d'haskell et de Gecode en même temps...

Je prendrais le temps de lire leurs papiers précédents en entier, là effectivement ils parlent de stratégies de recherche plus précisement. Cela reste quand même de la prog' par contraintes, donc je ne vois pas ce que devrait être la cible de cette bibli en dehors de ça :euh: .

Et sinon, code pas générique du tout, mais en Prolog :
Code : Autre - carré magique de taille 4, en Prolog
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

:- use_module(library(clpfd)).

carreMag(Vars) :-
        Vars = 
           [
           A1,A2,A3,A4,
           B1,B2,B3,B4,
           C1,C2,C3,C4,
           D1,D2,D3,D4
           ],
        Vars ins 1 .. 16,
        Sum in 1 .. 64,
        all_different(Vars),
        A1 + A2 + A3 + A4 #= Sum,
        B1 + B2 + B3 + B4 #= Sum,
        C1 + C2 + C3 + C4 #= Sum,
        D1 + D2 + D3 + D4 #= Sum,
        A1 + B2 + C3 + D4 #= Sum,
        D1 + C2 + B3 + A4 #= Sum,
        label(Vars),
        write(Vars), nl, write(Sum).

J'ai peur du résultat en passant ça pour 'n' quelconque >_< ...
mini-tuto prog' par contraintes
 
Hors ligne Karel # Posté le 17/01/2010 à 18:09:25

Je t'encourage à engager la rédaction d'un big-tuto à la fois théorique et pratique sur la programmation par contraintes et sur Gecode.

Ton mini-tuto est très intéressant; il ouvre les portes à un domaine de l'informatique pas très connu du grand publique. Et je trouve vraiment dommage d'avoir une mise en bouche aussi légère sur la programmation par contraintes. Le sujet mérite bien plus !
Hors ligne jinux95 # Posté le 27/02/2010 à 11:42:37
Avatar

 Salut tout le monde, :D

Tout d'abord, je te remercie pour ce tuto très intéressant. Ça faisait longtemps que je voulais coder un résolveur de Sudoku, je l'ai déjà fait avec une méthode par logique et par force brute. Je vais certainement essayer par contrainte. Mais en revanche je souhaiterais savoir :

Est-il possible de compiler avec Qt un projet programmé par contrainte ?

Voilà tout,
JB
Hors ligne Rushou # Posté le 27/02/2010 à 12:08:42
Avatar

Études : ENS Lyon

 Coucou,

Je suis certain que c'est possible, mais je ne peux pas t'aider là-dessus car je n'utilise pas Qt.

Sinon tu vas t'embêter en codant les contraintes pour le sudoku. Chaque ligne, colonne et zone est soumise à une contrainte "distinct" et c'est tout ^^ ...
mini-tuto prog' par contraintes
 
Hors ligne jinux95 # Posté le 27/02/2010 à 17:08:20
Avatar

 OK,
Mais est ce que tu utilise juste la console comme interface graphique pour tes programmes programmés par contraintes où alors tu utilise une interface GUI ? Si oui est-ce que tu peux m'indiquer la bibliothèque que tu utilise ?

Merci d'avance ;)
JB
Hors ligne deathman # Posté le 19/03/2010 à 14:53:23
Avatar

 Bon j'avoue que j'ai un peu survolé le tutorial mais je me demande si ce n'est pas des complications inutiles ?
Tu aurais peut-être du donné un autre exemple, je ne sais pas, mais sa ne m'a pas convaincu :(
En plus sa semble assez limité, si le temps de calcul pour plus de 6 cases de coté est "long" ce n'est pas adaptable pour tout les problèmes.
Perso j'opterai plutôt pour une métaheuristique (= méthode de résolution approximative générale) plutôt qu'une résolution exacte qui n'est efficace que sur des "petits problèmes" genre ton tableau de moins de 6 cases de côtés.
Puis comme sa a déjà été dit, ton tuto semble trop spécifique, personnellement même si je n'ai pas tout lu, je n'arrive pas à me faire une réelle idée de ce qu'est la programmation par contraintes, pour commencer tu aurais peut-être du prévoir ton tuto pour la partie algorithme plutôt que C++ ;)

Après je ne veux pas n'ont plus te décourager, c'est très sympa de ta part de prendre du temps pour expliquer tes connaissances aux autres et je t'en remercie ;)
My config :
Mobo : ASUS Maximus 2 Formula || proco : INTEL E8400 @ 2*3.0Ghz || Memory : 8Go DDR3
Sound : PCI SOUND BLASTER X-Fi || Kit 5.1 LOGITECH Z-5500 || Casque Sennheiser HD 25
Video : HD 5870 1Go || iiyama Prolite 24 Pouces 16/10e || Onduleur : Konig 1200 VA
HDD : Raptor 74Go + RAID-5 3To + 3To || Carte Controller RAID : SIL 3124

 
Hors ligne Rushou # Posté le 19/03/2010 à 15:43:40
Avatar

Études : ENS Lyon

 Coucou,

Ce tuto n'est qu'une introduction et il faut un problème simple pour présenter le domaine. Du coup ce n'est pas impressionant comme résultat.
Cependant, le problème du carré magique est difficile à résoudre et la programmation par contraintes offre un bon compromis entre le temps de modélisation/programmation et l'efficacité du programme. En améliorant un peu le modèle que je propose dans le tuto, on doit pouvoir résoudre un carré magique de taille 11 ou 12 sur un ordi normal en quelques minutes. Pour faire beaucoup mieux il faut développer un algo sur mesure pour le problème, et cela demande beaucoup de temps.

Il y a un domaine proche de la programmation par contraintes telle que je la présente ici, la recherche locale basée sur les contraintes. On y abandonne la recherche exhaustive des solutions, mais on espère trouver une solution bien plus rapidement. C'est un sujet plus avancé, c'est plus compliqué à utiliser en programmant, mais cela correspond à ton idée de métaheuristiques.

J'ai hésité à mettre ce tuto dans la catégorie C++, effectivement il serait peut-être mieux placé dans la section algo.

En tout cas, merci pour tes commentaires :) .
mini-tuto prog' par contraintes
 
Hors ligne eoxo # Posté le 14/07/2010 à 13:22:18
Avatar

Avis : Très bon

Études : TELECOM SudParis

 génial comme tuto. Je t'encourage vivement à en faire un big tuto en détaillant plus et en présentant la librairy de façon plus approfondi car il faut dire qu'elle est pas super user_friendly

bon courage
Une société prête a sacrifier un peu de liberté contre un peu de sécurité ne mérite ni l'une, ni l'autre, et finit par perdre les deux. (Benjamin Franklin)
 
Pour accéder à cette section
Connectez-vous !
connexion_rpx