Le symptome que tu rencontres est parfaitement normal. Quand on programme en FD, il ne faut pas surestimer le solveur, et attendre de lui une résolution mathématique des problèmes.
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 :)
# Propagation en FD
Posté par tgl . En réponse au message Propagation de contrainte en prolog sous ECLIPSe. É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 :)