algorithme de résolution d'une unique équation à n variables

Version imprimable

15/09/2006, 14h34
Mourad

algorithme de résolution d'une unique équation à n variables

je précise que ce n'est pas un système linéaire ici on a qu'une seule équation comme donnée le problème c'est de trouver ttes les solutions possibles à cette équation qq'un peut-il m'aider là dessus c urgent je cherche à réaliser l'algorithme permettant de parvenir à ttes les solutions possibles
15/09/2006, 14h41
borisd

Ton équation a des particularités spéciales (fonction continue, différentiable, intervalle de recherche borné... ?)
15/09/2006, 14h52
Mourad

ben voilà elle a la forme suivante
A.X1 + B.X2 + ... + Y.Xn = TOTAL

TOTAL et X1, ..... Xn sont connus et sont des paramètres en entrée pour l'alogorithme
maintenant comment faire pour trouver toutes les solutions possibles càd : A, B .....et Y

et tt ceci se passe ds N ts des entiers positifs

Ta fonction est linéaire discrète donc ?
Une solution brutale est d'utiliser un algo de programmation dynamique (ici de complexité pseudo-polynomiale a priori).
Ton problème est vaguement similaire au problème de sac-à-dos en nombre entiers, sauf que toi tu n'as pas de fonction économique et tu as une égalité au lieu d'une inégalité.
En gros, tu énumères toutes les valeurs possibles :
Code:

1 2 3 4 5 6 7 reste <- TOTAL - choisir une valeur entière pour A (tu as le choix entre 0..E(TOTAL/X1)) ; reste<-reste-A - choisir une valeur entière pour B (tu a le choix entre 0..E(reste/X2)) -... - faire pareil pour les autres variables ; si tu as l'égalité, tu ajoutes la solution aux possibles - tu reviens en arrière en passant à une autre valeur possible pour chacune des variables
Tu peux améliorer la méthode en t'arrêtant quand reste<min(Xk,...,Xn), ou des règles simples de ce genre.
Cette méthode a des chances de fonctionner si TOTAL/min(X1,...,Xn) est assez petit et que n aussi.

15/09/2006, 15h44
Mourad

à vrai dire c'est la première fois que j'entends parler de ce problème du sac à dos...
j'ai pas trop saisi ton explication mais je vais réfléchir là dessus...
merci
15/09/2006, 16h01
FrancisSourd

Ton problème est NP-complet donc il est difficile d'espérer mieux qu'un algo pseudo-polynomial. Comme borisd, la programmation dynamique me semble tout à fait adaptée. Voici un algo possible:
J'utiliserais une tableau T de TOTAL booléens initialisés à false. T[i] est mis à true lorsqu'on sait qu'on peut atteindre i.
A l'étape k, on met à true les totaux qui peuvent être atteint à l'aide des nombres x[1]....x[k]
Pour cela:
A l'étape 0 on met T[0] à true et les autres T[i] à false.

A l'étape k, pour chaque T[i] true, on met à true les valeurs T[i+x[k]], T[i+2x[k]], T[i+3x[k]]....

Si, à la fin de l'étape, n T[TOTAL] est true, c'est qu'il existe un solution. Pour la retrouver, il faut faire le fameux "parcours arrière" de la programmation dynamique (si tu ne connais pas, n'hésite pas à regarder un bouquin du style Cormen: c'est très bien expliqué).
15/09/2006, 16h44
Mourad

merci mais je ne vous cache pas que je n'ai rien compris est ce que vous pouvez me donner un peu plus d'explication sur la marche à suivre sinon l'algorithme tout court :) merci encore c vraiment très urgent
16/09/2006, 12h51
ToTo13

Bonjour,

un problème comme ça ne se résoud pas rapidement... désolé.

Etant donné la complexité du problème, il est vraisemblablement impossible de liste TOUTES les solutions.

Certaines méta heuristique (tabou ou recuit simuléà te donneront une bonne solution. Peut être pas la solution optimale, mais une bonne solution.

Pour mieux formaliser, c'est la résolution de

Code:

x[1]y[1] + x[2]y[2] + ... + x[n]y[N] = TOTAL

que voici. Les x[i] et TOTAL sont donnés. Les y[i] sont à déterminer et sont supposés entiers positifs.

Code:

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
29
30
31
32
33
34
35
 
var tableau T[0..TOTAL] de booleens
var from[1..n,0..TOTAL] d'entiers  // pour le backtrack de la programmation dynamique
 
// initialisation
T[0] = true: T[t] = false pour t = 1..TOTAL
from[i,t] = 0 pour i=1..n et t=0..TOTAL
 
// Descente de la programmation dynamique
Pour i allant de 1 à n faire
  Pour tout t allant de 0 à TOTAL tel que T[t] est true
    j = 0
    tant que t + jx[i] <= TOTAL faire
       T[t+jx[i]] = true;
       from[i,t+jx[i]] =j;
       j = j+1;
    fin tant que
  fin pour tout    
fin pour
 
Si t[TOTAL] = false alors pas de solution et stop
 
// Programmation dynamique arrière
// fabrication de la solution
pour tout i=1 à n faire y[i] = 0
t = TOTAL;
i = n;
tant que t > 0 faire
  j = from[i,t]
  Si j > 0 alors
    y[i] = j;
    t = t - jx[i];
  FinSi
  i = i-1
fin tant que

Mais, encore une fois, pour être sûr de bien implanter et de comprendre, je ne saurais trop te conseiller de lire le chapitre sur la programmation dynamique du Cormen (par example)

16/09/2006, 15h24
FrancisSourd

Citation:

Envoyé par ToTo13

Bonjour,

un problème comme ça ne se résoud pas rapidement... désolé.

Etant donné la complexité du problème, il est vraisemblablement impossible de liste TOUTES les solutions.

Certaines méta heuristique (tabou ou recuit simuléà te donneront une bonne solution. Peut être pas la solution optimale, mais une bonne solution.

Justement non ici. Même s'il est NP complet, le problème se résout plutôt bien à l'aide d'algorithme exacts et le recours aux métaheuristiques et plutôt à proscrire. D'autant plus d'ailleurs que général, il n'est que moyennement intéressant d'avoir une solution approximative à une telle équation.
16/09/2006, 15h51
Mourad

merci pour votre aide mais je pense avoir finallement trouvé comment faire tt seul je ne sais pas si c'est de la programmation dynamique comme vous dites mais bon moi aussi j'ai fait un truc en boucles qui avance et parfois revient en arrière tt dépend des conditions bref je ne sais pas si c'est optimal ce que j'ai fait mais apparemment ça marche (testé un peu... ça fonctionne)
en fait ce que je ne vous ai pas dis c que le total s'il n'est jamais atteint alors il faudra prendre toutes les solutions optimales qui minimisent au maximum le dépassement de TOTAL, je trouve que j'ai oublié pas mal de vocabulaires mathématiques :( , donc ça devient de cette forme là mais en minimisant au maximum le dépassement de TOTAL

Code:

x[1]y[1] + x[2]y[2] + ... + x[n]y[N] >= TOTAL

j'ai pas trop compris l'algorithme que tu m'as donné Francis mais en tt cas merci et je vais faire en sorte de m'intéresser à cette programmation dynamique bientôt
merci encore:)

Voici un petit code qui résoud le problème par récurence.
Attention : si le code est court, son execution peut prendre beaucoup de temps!
gare à la pile !!
Header Find.h:

Code:

1
2
3
4
5
6
7
8
9
10
 
//---------------------------------------------------------------------------
 
#ifndef FindH
#define FindH
#define W16     unsigned short
void Search_sol(W16 Xi[], W16 npts, W16 Sigma);
 
//---------------------------------------------------------------------------
#endif

Code Find.c(pp)

Code:

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
 
 
//---------------------------------------------------------------------------
 
 
#pragma hdrstop
 
#include "Find.h"
#include <stdio.h>
#include <stdlib.h >
#include <system.hpp>
#include <SysUtils.hpp>
 
//---------------------------------------------------------------------------
 
#pragma package(smart_init)
static W16 N, Total;     
static FILE *t ;
static void add(W16 Xi[], W16 SL[])
   {
   char C[255];
   AnsiString As = "";
   for (W16 U=0; U < N; U++) As = As + "Coef[" + IntToStr(U) + "] = " + IntToStr(SL[U]) + "   ";
   As = As.Trim() ;
   for (W16 i=0; i < As.Length(); i++)
      C[i] = As[i+1];
   C[As.Length()] = '\n';
   C[As.Length()+1] = '\0';
 
   fprintf(t,C);
   W16 Sm=0;
   for (W16 U=0; U < N; U++) Sm += Xi[U]* SL[U];
   As = "Résultat :   " + IntToStr(Sm) ;
   for (W16 i=0; i < As.Length(); i++)
      C[i] = As[i+1];
   C[As.Length()] = '\n';
   C[As.Length()+1] = '\0';  
   fprintf(t,C);
   }
static void Reduc ( W16 n, W16 SL[], W16 Xi[], W16 Reste )
   {
   W16 or = Reste;
   short np = Reste / Xi[n];  // trunc
   if ( n < N-1 )
      for ( W16 u=n+1; u < N; u++) SL[u] =0;
   if ( Reste == np * Xi[n] )
      {
      SL[n] = np;
      add(Xi, SL);
      np--;
      }
   if ( n < N-2 )
   for ( W16 i =0; i <= np; i++)
      {
      SL[n] = i;
      Reduc(n+1,SL, Xi, or - i * Xi[n]);
      }
   }
void Search_sol( W16 Xi[], W16 npts, W16 Sigma)
   {
   Total = Sigma;
   N = npts;
   for ( W16 i=0; i < N; i++) if ( ! Xi[i] )
      {
      return;    // coef nul pas de sens => le supprimer
      }
   W16 *SL = new W16[N];
   for ( W16 i=0; i < N; i++) SL[i] =0;
   W16 a = 0;
   t = fopen("Possibilitees.txt","wt");
 
   char C[255];
   AnsiString As = "";
   for (W16 U=0; U < N; U++) As = As + "X[" + IntToStr(U) + "] = " + IntToStr(Xi[U]) + "   ";
   As = As.Trim() + "\n" + "\0";
   for (W16 i=0; i < As.Length(); i++)
      C[i] = As[i+1];
   fprintf(t,C);
 
   Reduc(a,SL, Xi,Total);
   fclose(t);
   delete [] SL;
   }

Exemple d'appel

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
//---------------------------------------------------------------------------
W16 *Xi;
 
void  Find_Solutions(void)
{            
W16 n = 10;   // nombre de coef
W16 *Xi = new W16[n];  // allocation de la mémoire
if ( Xi )  // tableau OK
   {
W16 Total_a_atteindre = 30;  // fixer ici le total que l'on cherche
   for ( W16 i=0; i < n; i++)
      Xi[i] = i+1;    // mettre ici les coef souhaités
   Search_sol(Xi,n,Total_a_atteindre); // voir l'unité ci-dessus
   delete []  Xi;  // restitution de la mémoire
   }
else
   ShowMessage("Xi non initialisé");  // un message d'erreur
}

17/09/2006, 15h53
FrancisSourd

Citation:

Envoyé par Mourad

j'ai pas trop compris l'algorithme que tu m'as donné Francis mais en tt cas merci et je vais faire en sorte de m'intéresser à cette programmation dynamique bientôt
merci encore:)

Comme disait mon prof de maths, c'est quelque chose qu'il vaut mieux connaître qu'ignorer!
18/09/2006, 09h52
Freyja

Citation:

Envoyé par Mourad

je précise que ce n'est pas un système linéaire ici on a qu'une seule équation comme donnée le problème c'est de trouver ttes les solutions possibles à cette équation qq'un peut-il m'aider là dessus c urgent je cherche à réaliser l'algorithme permettant de parvenir à ttes les solutions possibles

La ponctuation coûte cher ??

Désolé pour ce message inutile... Mais j'ai eu un peu de mal...
18/09/2006, 10h25
Mourad

@Freyja pourtant on apprend à ponctuer dès l'école primaire :p
Donc considères ça, comme un exercice pour toi :D
à+
18/09/2006, 10h29
Freyja

Citation:

Envoyé par Mourad

@Freyja pourtant on apprend à ponctuer dès l'école primaire :p
Donc considères ça, comme un exercice pour toi :D
à+

ghein ? je ne comprend pas ton message.

Ce n'est pas une raison d'aller jusqu'à écrire en langage sms juste pour nous donner du travail de décodage !!!