je me sers de eclipse pour de la programmtion par contrainte et j'ai remarqué que la propagation des contraintes ne se faisait pas pour les contraintes linéaires du style A #=B+C avec la librairie Fd, un exemple :
[A,B,C,D] ::0..10, A+B+C+D#=10,S#=B+C,A#=0,D#=0, dom(S,Dom)
A = 0
B = B{[0..10]}
C = C{[0..10]}
D = 0
S = S{[0..20]}
Dom = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, ...]
There are 2 delayed goals.
Yes (0.00s cpu)
le resultat que je souhaite pour S est : S = S{[10..10]}
1) savez pourquoi ca ne marche pas ?
2) sauriez vous comment resoudre ce probleme ???
merci
sernin
# Propagation en FD
Posté par tgl . Évalué à 2.
La propagation de contraintes FD consiste simplement à répercuter d'une variable à l'autre les réductions de leurs domaines de valeurs possibles. Simplifions encore un peu ton exemple pour bien expliquer ça :
?- [A, B] :: 0..10, A+B #= 10, A+B #= C, A #>= 5, dom(C, Dom).
A = A{[5..10]}
B = B{[0..5]}
C = C{[5..15]}
Dom = [5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
There are 2 delayed goals.
Yes (0.00s cpu)
Ici, tu as 3 variables contraintes, qui sont A, B et C. On voit aisement que la dernière contrainte ("A #> 5") s'est propagée, puisque la réduction du domaine de A (de [0..10] à [5..10]) a provoquée celle en conséquence sur B (de [0..10] à [0..5], via la contrainte "A+B #= 10").
Quid sur C ? Et bien lui aussi, son domaine a été réduit (de [0..20] à [5..15], via la contrainte "A+B #= C"). C'est le mieux qu'on pouvait déduire de cette contrainte (la seule affectant C) et des domaines des variables mises en jeu (A et B).
Encore une fois, seuls les domaines des variables sont des vecteurs de la propagation de contraintes. Or "A+B" n'est pas une variable. Cette somme dans la première contrainte n'est aucunement liée (et encore mois identifiée) à celle dans la deuxième, et il n'y a donc rien dans ce programme qui permettrait de directement transmettre la valeur 10 à la variable C.
Bien sûr, ce fonctionnement, mis en exergue par un exemple aussi simple, peu sembler un peu stupide. Et bien oui, il l'est. FD est stupide. Mais il est aussi exact (encore heureux) et diablement efficace. Ce qui compte, ça n'est pas la précision (ou plutôt l'imprécision) des domaines qu'il peut inférer sur des problèmes à demi spécifiés, mais uniquement l'exactitude des résultats concrets qu'il rend (ceux associants une unique valeur à chaque variable), et la rapidité avec laquelle ils sont obtenus. Les domaines contenant plus d'une valeur ne sont pas vraiment des résultats, mais plutôt de la cuisine interne, et il ne faut pas les regarder de trop prêt. On peut facilement formuler des systèmes de contraintes equivalents en termes de solutions concrètes, mais qui provoquent des domaines intermédiaires différents. Si on y a accès, c'est principalement à des fins de debugage et d'optimisation en fait : ils te permettent de mieux comprendre, par exemple, pourquoi un système n'aboutit pas à une solution concrète, ou encore de coder une heuristique d'exploration des valeurs concrètes (labeling) qui soit vraiment efficace pour ton problème.
Quant à "résoudre ce problème", bah tu dois maintenant te douter de la réponse : ça n'est pas possible. Enfin, bien sûr, ajouter un "labeling([A,B,C,D])" ou un "labeling([S])" (selon ce que tu veux résoudre) te donnera bien des solutions "S=10", mais je me doute que ça n'est pas ce que tu attendais.
À part ça, bah, tu peux changer de solveur... Perso je ne connais rien qui travailles sur les domaines finis (avec tous les avantages que ça présente) et qui fasse aussi une résolution "intelligente" des contraintes linéaires. Et j'avoue que je n'en comprendrais pas bien le besoin, mais bon, ça veut pas forcement dire grand chose...
Par contre, si tu travailles spécifiquement sur des problèmes numériques linéaires, alors utiliser plutôt "clpq" (rationnels) ou "clpr" (réels) semble tout indiqué :
?- lib(clpq), {A+B = 10}, {A+B = C}.
A = A
B = B
C = 10
Yes (0.01s cpu)
% Linear constraints:
{
B = 10 - A
}
Mais bon, c'est un tout autre domaine d'applications, avec d'autres contraintes, et ça n'est pas moi qui peut te dire si tu es dedans ou non :)
[^] # Re: Propagation en FD
Posté par Sernin . Évalué à 1.
j'ai en effet concu une stratégie d'instanciation qui commence par les valeurs max du domaine de chaque variable
%***********************************************************%
% instanciation des variables : on choisit en priorite la %
%valeur max du domaine, de façon à caler les activites au %
%plus tot %
%**********************************************************%
instancier([]).
instancier(L):-
deleteff(X,L,Xs),
indomain(X,max),
instancier(Xs).
pour la librairie fd, si on la remplace, deleteff ne fonctionnera plus, et surement la même chose pour quelques autre fonctions dans mon programme
toutefois je te remerci beaucoup de ta rapidité, tu m'as bleuffé !
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.