Enumération de somme

[Patastronch]

Voila un petit problème qui me parait très simple, mais toutes les façon de le résoudre que je trouve sont trop gourmande a mon gout.

On a un ensemble de N nombres rationnel distinct (ou pas mais on peut considérer qu'ils sont tous distinct).
On cherche a énumérer dans l'ordre décroissant les sommes de P nombres parmi les N.

Par exemple :
Pour un ensemble S={1,2,4,6,8} et pour P=2

On cherche à avoir l'énumération :
8+6=14
8+4=12
6+4=8+2=10 (on peut choisir qu'ils sont énumérés en meme temps ou alors imposer un ordre total par exemple en considérant en cas d'égalité un ordre lexicographique des sur les termes)
8+1=9
6+2=8
6+1=7
4+2=6
4+1=5
2+1=3

Pour l'instant la meilleur méthode que j'ai trouvé et qui me parait trop gourmande vu la "simplicité" du problème consiste a utiliser un arbre d'énumération :
On cherche d'abord la plus grosse somme (facile c'est les P plus grands nombres).
Ensuite on sait que la seconde meilleur somme correspond a une variation d'un unique nombre, il s'agit donc soit de 8+4, soit de 6+4, c'est donc 8+4.
La troisième meilleure somme est une variation d'un nombre parmi les états qu'on a pas encore totalement développé, c'est a dire soit 6+4, soit 8+2.
Et on continue jusqu'au bout.

Ce qui correspondrait a un arbre de type :

8+4 -> 6+4 -> 6+2
***| **** |
***| **** -> 4+2
***-> 8+2 -> 6+2
******** |
******** -> 8+1

Dont le principe serait de partir de la racine et à chaque énumération prendre l'ensemble des nœuds a somme maximaux parmi les nœuds encore non énumérés. La taille de l'arbre est énorme puisque en chaque nœud on a potentiellement P branches. Ce qui est problématique puisqu'a chaque énumération on doit alors retenir un ensemble de plus en plus grand de nœuds non développé entièrement et le calcul de la k ème meilleure somme deviens alors très lourd si k est grand.

Pour résumer on cherche une fonction qui renvoie toutes les sommes maximales inférieur à M donné de P termes parmi N.

Des idées ??

[aviateurpilot]

si j'ai bien compris ton exo cela reviens à chercher une relation binair qui va classicifier les sous-emsenble a p elements, non??


si oui, voila une relation,
pour et deux sous ensemble a p elements
si et seulement si tel que:
pour
et

___________________
application pour ton exemple S={1,2,4,6,8} et pour P=2
{8,6}<
{8,4}<
{6,4}<{8,2} (meme si 6+4=8+2, on a 6²+4²<8²+2²)
{8,1}<
{6,2}<
{6,1}<
{4,2}<
{4,1}<
{2,1}<

[Patastronch]

Tout d'abord merci aviateur pour t'intéresser à ce probleme qui me taraude !

Oui en effet ta méthode fonctionne parfaitement ! Mais je me suis mal exprimé, en fait je cherche non pas une CNS pour déterminer l'ordre entre 2 sommes, mais la méthode qui effectue le moins de calcul (retenir un nombre en mémoire est considéré comme un calcul), pour énumérer. Par exemple si j'applique ta méthode il faut comparer 2 a 2 tous les sous-ensemble possible à P éléments pour déterminer leur ordre (je t'accorde qu'on peut surment feinter en utilisant la transitivité) ce qui fait un nombre de comparaison terriblement combinatoire !

Plus précisement, ce que j'aimerais c'est non pas une méthode qui donne l'ordre final, mais une méthode capable d'énumérer les K premiers seulement par exemple. Donc en appliquant ta CNS on obtiens toujours le meme nombre de calcul puisqu'il va falloir vérifier tous les sous-ensembles !

Je sais pas si j'ai été plus clair mais voila :)

[aviateurpilot]

Tout d'abord merci aviateur pour t'intéresser à ce probleme qui me taraude !

Oui en effet ta méthode fonctionne parfaitement ! Mais [...]
Plus précisement, ce que j'aimerais c'est non pas une méthode qui donne l'ordre final, mais une méthode capable d'énumérer les K premiers seulement par exemple. [...]

j'essaye tjrs de comprendre ce que tu veut trouver,
j'ai trouver une methode pour:
i) donner un classement des sous-ensembles à p elements.
ii) trouver les k 1er elements avec un clacule minimal et tres tres simple.
(pour trouver la k-eme sous ensemble il faut trouver la 1er et puis la 2eme.....jusqu'a la k-eme)
j'espere que c'est ce que tu veux :id:

voila ma methode (meme si je ne fait pas la programation, mais je suis sure que ce que je vais faire donnera surement un programme qui trouve les k 1er ensemble dans la classification que j'ai defini):

soit on peux supposer que [TEX]x_1 {1,2}
U_1=(1,3) ==> {1,4}
U_2=(1,4) ==> {1,6}
U_3=(1,5) ==> {1,8}
U_4=(2,3) ==> {2,4}
U_5=(2,4) ==> {2,6}
U_6=(2,5) ==> {2,8}
U_7=(3,4) ==> {4,6}
U_8=(3,5) ==> {4,8}
U_9=(4,5) ==> {6,8}
________________________________________
pour la consruction de la suite , je n voulais pas entrer dans les detailles mathematique inutile pour montrer que cette suite donne bien tous les sous ensembles possible, je crois que l'important ici, c'est bien definir l'algorithm de construction, j'espere que j'ete bien clair.
( j'ai pensé a cette construction en m'insperant de la base decimal lool :we: )
________________________________________
exemple de construction d'une suite sur S={1,2,3,4,5,6,7,8,9} et p=4

1,2,3,4
1,2,3,5
1,2,3,6
1,2,3,7
1,2,3,8
1,2,3,9
1,2,4,5
1,2,4,6
1,2,4,7
1,2,4,8
1,2,4,9
1,2,5,6
1,2,5,7
1,2,5,8
1,2,5,9
1,2,6,7
1,2,6,8
1,2,6,9
1,2,7,8
1,2,7,9
1,2,8,9
...
...
...
6,7,8,9

[scelerat]

L'idee sur laquelle j'ai rumine est de construire l'arbre en partant du plus grand element, et donc pour cet element on choisit entre l'ensemble suivant dans l'enumeration des P parmi les N-1 inferieurs, et l'element plus l'ensemble suivant dans l'enumeration de P-1 parmi les N-1 inferieurs.
On voit que si on a une fonction d'enumeration "consciente de son etat courant", le seul probleme devient le nombre d'etats courants a conserver (en gros, la frontiere entre la partie de l'arbre deja enumeree et celle restant a enumerer).

Par contre, je n'ai pas trouve de methode pour limiter la croissance de ce nombre, et je dois dire que ca me rappelle des histoires de partition en deux sous-ensembles de sommes egales (on y passe forcement a un moment de l'enumeration) dont il me semble que c'est l'exemple meme du NP-complet.

[abcd22]

Bonjour,
J'ai regardé dans _Introduction à l'algorithmique_ de Cormen, Leiserson, Rivest et Stein (2e édition) pour voir s'ils parlaient de problèmes proches. La partie 34.5.5 (p. 979) parle du problème de la somme de sous-ensembles : on a un ensemble fini S d'entiers naturels, un entier t, on veut savoir s'il existe un sous-ensemble de S dont la somme des éléments est t. Ils démontrent que ce problème est NP-complet, ce qui montre que le problème qu'on a ici l'est aussi, si je ne me trompe pas. Un peu plus loin (partie 35.5, page 1007), ils donnent un algorithme (exponentiel) pour le problème de la somme de sous-ensembles, puis un schéma d'approximation à temps polynomial, qui donne un sous-ensemble dont la somme n'est pas trop éloignée du résultat optimal, mais si tu as vraiment besoin de calculer toutes les sommes ça ne va pas t'aider...

[scelerat]

Bien entendu, si N et P sont petits et les elements entiers petits, il suffit de faire un tableau de listes chainees de dimension S, somme des P plus grands elements, puis un tri-distribution (explorer toutes les combinaisons de P elements dans un ordre arbitraire pour les ajouter a la liste correspondant a leur somme, et vider le tableau pour produire l'enumeration souhaitee). Apres tout, tant qu'on est suffisamment jeune pour avoir le temps de regarder toute l'enumeration defiler sur son ecran, il ne doit pas y avoir de probleme pour la stocker en totalite dans la memoire d'un ordinateur moderne...

[Patastronch]

j'essaye tjrs de comprendre ce que tu veut trouver,
j'ai trouver une methode pour:
i) donner un classement des sous-ensembles à p elements.
ii) trouver les k 1er elements avec un clacule minimal et tres tres simple.
(pour trouver la k-eme sous ensemble il faut trouver la 1er et puis la 2eme.....jusqu'a la k-eme)
j'espere que c'est ce que tu veux :id:

Je me suis encore mal exprimé alors. Je cherche :
i) donner un classement des sous-ensembles à p elements selon l'ordre décroissant ed leur somme.
ii) trouver les k 1er elements avec un clacule minimal et tres tres simple.

TOn algo si je ne m'abuse reviens a donner l'ordre lexicographique, il en faudrait un similaire mais pour les sommes

[Patastronch]

L'idee sur laquelle j'ai rumine est ...

On a la meme méthode a peu de choses près.

[Patastronch]

Bonjour,
J'ai regardé dans _Introduction à l'algorithmique_ de Cormen, Leiserson, Rivest et Stein (2e édition) pour voir s'ils parlaient de problèmes proches. La partie 34.5.5 (p. 979) parle du problème de la somme de sous-ensembles : on a un ensemble fini S d'entiers naturels, un entier t, on veut savoir s'il existe un sous-ensemble de S dont la somme des éléments est t. Ils démontrent que ce problème est NP-complet, ce qui montre que le problème qu'on a ici l'est aussi, si je ne me trompe pas. Un peu plus loin (partie 35.5, page 1007), ils donnent un algorithme (exponentiel) pour le problème de la somme de sous-ensembles, puis un schéma d'approximation à temps polynomial, qui donne un sous-ensemble dont la somme n'est pas trop éloignée du résultat optimal, mais si tu as vraiment besoin de calculer toutes les sommes ça ne va pas t'aider...

Merci pour la référence.
Oui ce problème est bien-entendu NP-complet !

Le problème peut se réduire en :

Existe-t il un sous-ensemble de P élément dont la somme soit égale à M sachant qu'on connait toutes les sommes supérieur à M.

Ce problème se résoud facilement avec la méthode de Scélérat et la méthode est polynomial en la taille de l'enoncé (qui lui ne l'est pas cependant).

Maintenant le probleme serait de voir si il est nécessaire de retenir toutes les sommes superieur à M ou s'il est possible d'en conserver moins. On sait déjà que le nombre de sommes retenue ne peut-être polynomial en P et N puisqu'on pourrait alors résoudre polynomialement le probleme que tu exposes qui est NP-complet (et on suppose P différent de NP). La méthode de scélérat et celle a laquelle je pensait permettent de ne pas tout retenir mais seulement les noeuds de l'arbre non développé totalement. Cependant je trouve ca encore trop gourmand meme pour un probleme NP-Complet. D'ou ma question, avez vous une idée pour faire mieu ?

Je vais regarder de plus pres le schéma d'approximation polynomiale que tu proposes, et s'il est possible de restreindre ce shcéma uniquement aux valeurs approchées inférieur à M, peut etre qu'un algo comme suit pourait etre efficace :

1/ Trouver la meilleure somme (égale à S_1)
2/ Fixer epsilon de maniere raisonnable pour que l'algorithme ne soit pas trop long.
3/ Pour i variant de 1 à K faire
4/ Calculer une aproximation pour chercher une somme egale à (ou inférieur par aproximation) epsilon+S_i
5/ Fin pour


Bon je doute que ce soit possible car j'ai l'impression que cela reviendrait à rendre polynomiale la résolution. Ca doit donc surment coincer quand je dit qu'on peut restreindre ce schéma d'approximation uniquement aux valeurs approchées inférieur à M.

Je sais pas si je suis bien clair ...

Merci pour vos réponses en tous cas.

edit : Ca aurait peut-etre eu plus sa place dans informatique, si un modérateur pense qu'il faut le déplacer qu'il ne se gène surtout pas.

[abcd22]

En fait le schéma d'approximation expliqué dans le livre consiste justement à « retenir » moins de données : on regarde ce qu'on peut faire comme sommes inférieures à t avec les premiers éléments de l'ensemble, puis avant de regarder ce qu'on obtient en ajoutant un élément à chaque ensemble obtenu, on supprime des éléments proches, par exemple si on obtient comme sommes possibles {10, 11, 12, 15, 21, 22, 23, 24}, on ne garde que {10, 12, 15, 21, 24}. L'algorithme obtenu est bien polynomial en temps et en 1/epsilon où epsilon est le pourcentage d'erreur permise par rapport à la solution optimale, mais il ne donne pas forcément la somme la plus proche possible de t, après je ne sais pas si tu peux te contenter de résultats approximatifs ou s'il te faut les sommes exactes (en particulier s'il y a beaucoup d'ensembles de p éléments qui donnent presque la même somme ils seront presque tous éliminés). S'il te faut les sommes exactes, il ne doit pas y avoir beaucoup mieux que ta solution ou celle de scelerat.