Bonjour,


Soit l'équation suivante :

32a + 24b + 16c + 12d + 8e + 4f = X

avec a + b + c + d + e + f <= Y
et a, b, c, d, e et f qui sont des entiers >= 0

Je cherche un algorithme me permettant de trouver toutes les solutions de ce
système sachant que je connais X et Y.

Exemple : pour X = 156 et Y = 6
Je trouve 3 solutions : a = 4 ; b = 1 ; f = 1 ou a = 4 ; c = 1 ; d = 1 ou a
= 3 ; b = 2 ; d = 1

Actuellement, j'utilise une procédure très longue qui pour toutes les
valeurs possible de a teste les valeurs possibles de b, c, d ,e ,f et ainsi
de suite.
Après quelques tests, il apparaît évident que ma procédure n'est pas bonne
car je ne trouve qu'une partie des cas possibles (sur un exemple simple,
j'ai trouvé des solutions à la main que j'ai zappé avec ma procédure)

Quelqu'un a-t-il une idée à me proposer, car le moins que l'on puisse dire,
c'est que je ne suis pas très doué en algorithmes.

Merci d'avance pour tout début de solution, ou une solution complète si le
coeur vous en dit :-)

Cordialement,

David Berthemet

Bonjour,

Merci de vous être penché sur mon problème.
Je vais donc essayer de chercher des infos sur la programmation linéaire en
nombre entier.

Cordialement,

David Berthemet

"gerard sookahet" <gersoo***_NON-SPAM_online.fr> a écrit dans le message de
news: 48726269$0$839$ba4acef3***news.orange.fr...
> David Berthemet wrote:
>> Bonjour,
>>
>>
>> Soit l'équation suivante :
>>
>> 32a + 24b + 16c + 12d + 8e + 4f = X
>>
>> avec a + b + c + d + e + f <= Y
>> et a, b, c, d, e et f qui sont des entiers >= 0
>>
>> Je cherche un algorithme me permettant de trouver toutes les solutions de
>> ce système sachant que je connais X et Y.
>>
>> Exemple : pour X = 156 et Y = 6
>> Je trouve 3 solutions : a = 4 ; b = 1 ; f = 1 ou a = 4 ; c = 1 ; d = 1 ou
>> a = 3 ; b = 2 ; d = 1
>>
>> Actuellement, j'utilise une procédure très longue qui pour toutes les
>> valeurs possible de a teste les valeurs possibles de b, c, d ,e ,f et
>> ainsi de suite.
>> Après quelques tests, il apparaît évident que ma procédure n'est pas
>> bonne car je ne trouve qu'une partie des cas possibles (sur un exemple
>> simple, j'ai trouvé des solutions à la main que j'ai zappé avec ma
>> procédure)
>>
>> Quelqu'un a-t-il une idée à me proposer, car le moins que l'on puisse
>> dire, c'est que je ne suis pas très doué en algorithmes.
>>
>> Merci d'avance pour tout début de solution, ou une solution complète si
>> le coeur vous en dit :-)
>>
>> Cordialement,
>>
>> David Berthemet
>
> Bonsoir,
>
> Il faudrait faire une recherche du côté de la Programmation Linéaire
> en Nombre Entier (PLNE).
>
>
> GS
>

Bonjour,

Merci de vous être penché sur mon problème.
Je réalise effectivement la simplification par 4 et je borne les différentes
variables en fonction de Y (mais X et Y peuvent-être très grand).
La simplification de l'équation ne donne pas 8a+3b+4c+3d+2e+f=X/4 mais 8a+
6b +4c+3d+2e+f=X/4 et je ne comprends pas comment la simplifier encore.

Je vais donc tester ces différentes pistes.

Cordialement,

David Berthemet

"Michel Olagnon" <molagnon***ifremer-a-oter.fr> a écrit dans le message de
news: 487319D1.5010007***ifremer-a-oter.fr...
> David Berthemet wrote:
>> Bonjour,
>>
>>
>> Soit l'équation suivante :
>>
>> 32a + 24b + 16c + 12d + 8e + 4f = X
>>
>> avec a + b + c + d + e + f <= Y
>> et a, b, c, d, e et f qui sont des entiers >= 0
>>
>> Je cherche un algorithme me permettant de trouver toutes les solutions de
>> ce système sachant que je connais X et Y.
>>
>> Exemple : pour X = 156 et Y = 6
>> Je trouve 3 solutions : a = 4 ; b = 1 ; f = 1 ou a = 4 ; c = 1 ; d = 1 ou
>> a = 3 ; b = 2 ; d = 1
>>
>> Actuellement, j'utilise une procédure très longue qui pour toutes les
>> valeurs possible de a teste les valeurs possibles de b, c, d ,e ,f et
>> ainsi de suite.
>
> Si c'est fait correctement, ca ne me parait pas tres long.
> On a 0<=a<=min (Y,X/32), 0<=b<=min(Y-a,(X-32a)/24), etc.
>
> Dans le cas precis, on peut aussi simplifier la premiere
> equation en 8a+3b+4c+3d+2e+f=X/4 et remarquer que l'on peut
> reduire le nombre de variables d'une en prenant g = b+d.
>
>

Bonjour,

et merci de vous être penché sur mon problème.

Actuellement, je fais effectivement des boucles de ce type, et après
vérification de mon code, j'ai trouvé l'erreur de ma procédure qui zappait
certaines solutions.
Par contre je ne n'utilise pas les mêmes bornes que vous mais une borne du
type Max(PartieEntière(X/32), Y) si PartieEntière(X/32)> Y sinon je prends
PartieEntière(X/32)
Ma procédure semble donc maintenant bonne.
Dans votre exemple, les bornes que vous utilisez ne me conviennes pas car
elles induisent que a>b>c>d>e>f ce qui n'est pas vrai pour toutes les
valeurs de Y pouvant survenir (est notamment si Y n'est pas borné ou est
très grand, ce qui peut arriver ou si X est petit - Exemple avec X = 32 et Y
=6)
Par contre, j'aimerais savoir si il est possible de savoir d'avance le
nombre de solutions correctes que l'on doit trouver (3 dans mon exemple
original sachant qu'il y a 796 possibilités de trouver 156 avec cette
équation mais en ayant des Y dépassant 6) afin de pouvoir vérifier si mes
résultats sont bons et éventuellement, si il y a une technique permettant de
ne pas calculer des cas dont on pourrait être certains qu'il ne seront pas
bons car si on ne donne pas du tout de limite à Y, il y a 3 920 000 calculs
à réaliser, ce qui fait pas mal compte tenu du fait qu'il n'y a que 2 379
calculs permettant de totaliser 156.

Cordialement,

David Berthemet
"Pascal J. Bourguignon" <pjb***informatimago.com> a écrit dans le message de
news: 7ciqvgehph.fsf***pbourguignon.anevia.com...
> "David Berthemet" <berthemet.david***neuf.fr> writes:
>> Soit l'équation suivante :
>>
>> 32a + 24b + 16c + 12d + 8e + 4f = X
>>
>> avec a + b + c + d + e + f <= Y
>> et a, b, c, d, e et f qui sont des entiers >= 0
>>
>> Je cherche un algorithme me permettant de trouver toutes les solutions de
>> ce
>> système sachant que je connais X et Y.
>>
>> Exemple : pour X = 156 et Y = 6
>> Je trouve 3 solutions : a = 4 ; b = 1 ; f = 1 ou a = 4 ; c = 1 ; d = 1 ou
>> a
>> = 3 ; b = 2 ; d = 1
>>
>> Actuellement, j'utilise une procédure très longue qui pour toutes les
>> valeurs possible de a teste les valeurs possibles de b, c, d ,e ,f et
>> ainsi
>> de suite.
>> Après quelques tests, il apparaît évident que ma procédure n'est pas
>> bonne
>> car je ne trouve qu'une partie des cas possibles (sur un exemple simple,
>> j'ai trouvé des solutions à la main que j'ai zappé avec ma procédure)
>>
>> Quelqu'un a-t-il une idée à me proposer, car le moins que l'on puisse
>> dire,
>> c'est que je ne suis pas très doué en algorithmes.
>>
>> Merci d'avance pour tout début de solution, ou une solution complète si
>> le
>> coeur vous en dit :-)
>
> Mis à part les algorithmes sophistiqués que tu pourras trouver par
> ailleur avec les conseils avisés des autres, il n'y a pas de raison de
> manquer des solutions:
>
> pour a de 0 à Y
> pour b de 0 à Y-a
> pour c de 0 à Y-a-b
> pour d de 0 à Y-a-b-c
> pour e de 0 à Y-a-b-c-d
> pour f de 0 à Y-a-b-c-d
> si 32a + 24b + 16c + 12d + 8e + 4f = X alors
> afficher (a,b,c,d,e,f) est solution.
> fin si
> fin pour
> fin pour
> fin pour
> fin pour
> fin pour
> fin pour
>
>
> Si c'est pour des cas simples comme l'exemple, ce n'est pas trés long,
> pour Y=6 il n'y a que 924 cas à tester:
>
>
> C/USER[49]> (time
> (let ((x 156) (y 6) (counter 0))
> (loop for a from 0 to y do
> (loop for b from 0 to (- y a) do
> (loop for c from 0 to (- y a b) do
> (loop for d from 0 to (- y a b c) do
> (loop for e from 0 to (- y a b c d) do
> (loop for f from 0 to (- y a b c d e) do
> (incf counter)
> (when (= (+ (* 32 a) (* 24 b) (* 16 c) (* 12 d) (* 8 e)
> (* 4 f)) x)
> (print (list a b c d e f)))))))))
> (print counter)))
>
> (3 2 0 1 0 0)
> (4 0 1 1 0 0)
> (4 1 0 0 0 1)
> 924
> Real time: 0.222618 sec.
> Run time: 0.219987 sec.
> Space: 7316336 Bytes
> GC: 2, GC time: 0.046665 sec.
> 924
>
> --
> __Pascal Bourguignon__

Bonjour,

Et merci de vous pencher sur mon problème.

Ne connaissant pas le langage employé dans votre réponse (je reste limité à
VBA et à Windev), j'ai quelques difficultés à le comprendre. Néanmoins,
comme il parait très concis, il m'apparait fort intéressant de l'étudier et
je vais donc essayer de le décrypter.

Cordialement,

David Berthemet

"Antoine Polatouche" <antoine***galacsys.com> a écrit dans le message de news:
g50dl5$2qnp$1***cabale.usenet-fr.net...
> David Berthemet a écrit :
>>>> Soit l'équation suivante :
>>>>
>>>> 32a + 24b + 16c + 12d + 8e + 4f = X
>>>>
>>>> avec a + b + c + d + e + f <= Y
>>>> et a, b, c, d, e et f qui sont des entiers >= 0
>>>>
>>>> Je cherche un algorithme me permettant de trouver toutes les solutions
>>>> de ce
>>>> système sachant que je connais X et Y.
>
> Pas testé:
>
> void LaFonction( in X, int Y)
> {
> int Z = X/4;
> if(4*Z==X)
> for( int a=0; 8a <= Z && a <= Y; a++ )
> for(int b=0; 6b <= Z-8a && b <= Y; b++ )
> for(int c=0; 4c <= Z-8a-6b && c <= Y; c++)
> for(int d=0; 3d <= Z-8a-6b-4c && d <= Y; d++)
> for(int e=0; 2e <= Z-8a-6b-4c-3d && e <= Y; e++){
> int f = Z-8a-6b-4c-3d-2e;
> if(f >= 0 && f <=Y) AfficheLaSolution(a,b,c,d,e,f);
> }
> }
>

Bonjour,

Et merci de vous pencher sur mon problème.

Ne connaissant pas le langage employé dans votre réponse (je reste limité à
VBA et à Windev), j'ai quelques difficultés à le comprendre. Néanmoins,
comme il parait très concis, il m'apparait fort intéressant de l'étudier et
je vais donc essayer de le décrypter.

Cordialement,

David Berthemet

"Antoine Polatouche" <antoine***galacsys.com> a écrit dans le message de news:
g50dl5$2qnp$1***cabale.usenet-fr.net...
> David Berthemet a écrit :
>>>> Soit l'équation suivante :
>>>>
>>>> 32a + 24b + 16c + 12d + 8e + 4f = X
>>>>
>>>> avec a + b + c + d + e + f <= Y
>>>> et a, b, c, d, e et f qui sont des entiers >= 0
>>>>
>>>> Je cherche un algorithme me permettant de trouver toutes les solutions
>>>> de ce
>>>> système sachant que je connais X et Y.
>
> Pas testé:
>
> void LaFonction( in X, int Y)
> {
> int Z = X/4;
> if(4*Z==X)
> for( int a=0; 8a <= Z && a <= Y; a++ )
> for(int b=0; 6b <= Z-8a && b <= Y; b++ )
> for(int c=0; 4c <= Z-8a-6b && c <= Y; c++)
> for(int d=0; 3d <= Z-8a-6b-4c && d <= Y; d++)
> for(int e=0; 2e <= Z-8a-6b-4c-3d && e <= Y; e++){
> int f = Z-8a-6b-4c-3d-2e;
> if(f >= 0 && f <=Y) AfficheLaSolution(a,b,c,d,e,f);
> }
> }
>

Merci pour ce complément d'info. Je vais ainsi pouvoir analyser votre code.

Cordialement,

David Berthemet

"Antoine Polatouche" <antoine***galacsys.com> a écrit dans le message de news:
g51b35$v17$1***cabale.usenet-fr.net...
> David Berthemet a écrit :
>> Bonjour,
>>
>> Et merci de vous pencher sur mon problème.
>>
>> Ne connaissant pas le langage employé dans votre réponse (je reste limité
>> à VBA et à Windev), j'ai quelques difficultés à le comprendre. Néanmoins,
>> comme il parait très concis, il m'apparait fort intéressant de l'étudier
>> et je vais donc essayer de le décrypter.
>
> C'est du C.
> for( int a=0; 8a <= Z && a <= Y; a++ )
> veut dire
> a=0 en début de boucle
> boucler tant que 8a <= Z et a <= Y (&& est AND en basic je crois)
> en incrémentant a en fin de boucle (a++)
>
>

"Pascal Bourguignon" pjb***informatimago.com à écrit :

> Les bornes de boucle n'impliquent aucun ordre entre les variables de
> boucle, intrinsèquement. Tout dépend de la valeur de Y.
>
> Considérons juste les deux premières boucles:
>
>
> pour a de 0 à Y
> pour b de 0 à Y-a
>
> Quand a=0, b va de 0 à Y et donc b>=a
> Quand a=1, b va de 0 à Y-1 et donc d'abort b<a, puis b=a, puis b>a.
> ...
> Quand a=3<Y, b va de 0 à Y-3 et donc, si Y>a+3, parfois a<b et parfois
> a>b.
> ...
>
> Pour en être sur, il suffit de générer tous les tuples:
>
........

> Ce que les bornes encodent, c'est la condition a+b+c+d+e+f<=Y
>

Merci pour ces précisions qui me permettent de mieux comprendre les
possibilités de résolutions de mon problème.

Cordialement,

David Berthemet

David Berthemet a écrit :
> Soit l'équation suivante :
>
> 32a + 24b + 16c + 12d + 8e + 4f = X
>
> avec a + b + c + d + e + f <= Y
> et a, b, c, d, e et f qui sont des entiers >= 0
>
> Je cherche un algorithme me permettant de trouver toutes les solutions de ce
> système sachant que je connais X et Y.

Bonjour,

si vous cherchez seulement la solution (et pas la manière d'y arriver),
sachez que le langage Prolog est parfaitement adapté Ã*** ce genre de
problèmes. Pour exemple, voici comment on ferait :

equation([A,B,C,D,E,F]) :-
fd_domain([A,B,C,D,E,F], 0, 6),
A + B + C + D + E + F #=< 6,
32 * A + 24 * B + 16 * C + 12 * D + 8 * E + 4 * F #= 156,
fd_labeling([A,B,C,D,E,F]).


Et le bidule ressort :

| ?- equation(L).

L = [3,2,0,1,0,0] ? a

L = [4,0,1,1,0,0]

L = [4,1,0,0,0,1]

yes


Le langage (et son interpréteur, bien sûr) permettent des choses bien
plus complexes que ça, toujours dans l'optique de définir des
contraintes logiques, et laisser faire la machine.

Je ne sais pas si vous avez besoin de cet algorithme pour l'intégrer Ã***
votre logiciel, ou simplement parce que vous vouliez calculer des
solutions, mais dans le second cas, je ne peux que vous conseiller de
jeter un oeil Ã*** Prolog. C'est un langage prévu pour des non
programmeurs, et est assez déconcertant quand on a l'habitude de la
programmation séquentielle, mais sa puissance est grisante.
Il résout des problèmes combinatoires monstrueux en un clin d'oeil.

S'il vous faut coder l'algorithme vous même, c'est un peu plus compliqué...

La solution évidente consiste Ã*** tester tous les n-uplets de nombres
jusqu'Ã*** trouver une solution. Si vous ne définissez pas de bornes, ça
peut être très long (une petite éternité, quoi...)

Même avec des bornes (ici elles sont faciles Ã*** trouver), ça fait quand
même beaucoup : R^N, où N est le nombre de variables, et R l'étendue de
recherche.

Si je me rappelle bien, prolog fait quelque chose de similaire, mais en
réduisant d'abord les intervalles pour chaque variable autant que
possible, simplement Ã*** partir des expressions données. D'ailleurs, quand
on ne lui demande pas d'énumérer avec « labeling », c'est ce qu'il donne :

| ?- equation(L).

L = [_#3(0..4),_#25(0..6),_#47(0..6),_#69(0..6),_#91(0. .6),_#113(0..6)]

yes


Après, il teste tous les cas, mais de manière un peu intelligente, c'est
Ã*** dire qu'il construit un arbre des tests, créant une branche fille Ã***
chaque fois qu'il fixe une variable, et explore toutes les possibilités
au fur et Ã*** mesure.
Quand un choix n'a donné aucune solution, il remonte dans l'arbre et
emprunte une autre branche (change la valeur d'une variable).

Fait simplement comme ça, cela revient Ã*** tester toutes les possibilités.
Les optimisations font que ça va plus vite : si on peut prédire qu'un
choix sera mauvais, on peut supprimer toute une branche sans la visiter.
Par exemple, si A est fixé Ã*** 6, la première condition ne sera remplie
que si tout le reste est nul.
De plus, dans les cas où on cherche une seule solution (et pas toutes),
il est possible de choisir quelle branche explorer d'abord, si elle
semble (selon des critères précis) prometteuse, etc.

Quoi qu'il en soit, c'est un problème qui est assez complexe Ã***
programmer soi-même, et je suppose que la meilleure solution est de tout
tester bêtement, si la combinatoire le permet.

Quelques liens :

http://fr.wikipedia.org/wiki/Prolog
http://fr.wikipedia.org/wiki/Séparation_et_évaluation
http://en.wikipedia.org/wiki/Constra...ic_programming

Bon courage en tout cas, si vous vous lancez dans la solution compliquée

Noé

"Noé Falzon" a écrit :
> si vous cherchez seulement la solution (et pas la manière d'y arriver),
> sachez que le langage Prolog est parfaitement adapté à ce genre de
> problèmes. Pour exemple, voici comment on ferait :
>

Bonjour,

Je vous remercie pour cette piste qui me semble fort prometteuse.
Pour l'instant j'ai réussi à modifier mon code original qui était bogué (car
j'avais bêtement oublié de passer dans une boucle) pour trouver l'ensemble
des solutions possibles. Cela peut s'avérer long en fonction des contraintes
mais tout semble bien fonctionner et je peux donc maintenant continuer mon
programme (je dois maintenant chercher toutes les permutations avec
répétitions pour toutes les solutions trouvées puis leur attribuer une
valeur spécifique en fonction de nouvelles contraintes. J'ai peur que les
temps de calculs explosent, mais cette discussion m'a amenée à mieux
réfléchir sur ce type de problème et j'espère donc que tout va bien se
passer !)

J'essaierais donc d'optimiser cette procédure grâce aux informations glanées
dans ce fil de discussion lorsque l'ensemble du programme sera fonctionnel
et que j'aurais une vision globale du problème.

Merci encore d'avoir pris le temps de vous pencher sur mon problème.

Cordialement,

David Berthemet