méthode pour trouver un sous-ensemble

[invite8b421ec7]

Bonjour,

Je cherche une méthode (enfin un algorithme) qui permet de trouver intélligement un ou plusieurs sous ensemble d'un ensemble de n éléments tel que la somme des élements de sous-ensemble égale à zéro.
Voici un exemple:
J'ai un ensemble a : +5, +10, +11, +19, -26, -12, -3, -3, -1
Je connais déjà que la somme des éléments de mon ensemble a est égale à zéro.
Je cherche à déterminer un ou plusieurs sous ensmble de a à condition que la somme de sous ensemble est égale à zéro.

Donc:
Sous ensemble 1: +5, +11, +10, -26.
Sous ensemble 2: +19, -12, -3, , -3, -1

Des idées?
Merci par avance
-----

[invite4492c379]

Hello Céline2,

Tu as donc une liste de n entiers relatifs A=(a_i)ⁿ_i=1. Sans perdre en généralité on peut supposer que les a_i sont non nuls et triés : a₁<a₂< ... < a_n-1 < a_n. On ne perd pas en généralité en les supposant non nuls ; en effet soit A^* une liste d'entiers relatifs certains pouvant être nuls et A la sous liste de A^* qui contient tous les éléments non nuls de A^*. Si on note L (resp. L^*) la liste des sous listes solution de A (resp A^*) alors L^* est L auquel on ajoute les solutions composées uniquement de 0 et toutes les solutions de L auxquelles on aura ajouté les 0.

Par exemple avec A*=(-2,-1,0,1,1) on a A=(-2,-1,1,1), L=( (-2,1,1),(-1,1),(-1,1) ) et du coup
L^*= (
(-2,1,1),(-1,1),(-1,1), les solutions de L
(0), les solutions qu'avec des 0
(-2,0,1,1),(-1,0,1),(-1,0,1) les solutions de L avec les 0
)

Ensuite il faut juste que tu nous précises si L est un ensemble (on ne compte pas les solutions doubles) ou une liste (dans l'exemple c'est une liste d'où deux fois le (-1,1)).


Donc en première approche, tu vas parcourir toutes les sous-listes possibles, calculer leur somme, ne garder que celles dont la somme est nulle. Au pire tu vas devoir parcourir 2ⁿ sous listes.

Les doublons comptent-ils ?
As-tu une idée comment faire ça ou as-tu besoin d'aide ?

[invite8b421ec7]

Merci photon57 pour votre réponse rapide.

Ensuite il faut juste que tu nous précises si L est un ensemble (on ne compte pas les solutions doubles) ou une liste (dans l'exemple c'est une liste d'où deux fois le (-1,1)).

le L est un ensemble.

Donc en première approche, tu vas parcourir toutes les sous-listes possibles, calculer leur somme, ne garder que celles dont la somme est nulle. Au pire tu vas devoir parcourir 2ⁿ sous listes.

oui mais si n est égale à 100. le temps de calcul va exploser.

Les doublons comptent-ils ?

non.

As-tu une idée comment faire ça ou as-tu besoin d'aide ?

J'ai besoin d'aide carje ne vois pas de tout comment trouver un sous-ensemble d'un ensemble de 100 entiers.
Merci d'avance

[invite4492c379]

Ça avec 100 entier et un algo en O(2ⁿ) ...
Ton problème se nomme SUBSET SUM et est NP-complet.
Pour n petit tu peux essayer une recherche exhaustive, pour n plus grand un algo dynamique.
Est-ce que la somme de ta liste de départ est toujours nulle ?

[A voir en vidéo sur Futura]

[invite8b421ec7]

La somme de la liste de départ est toujours nulle.

Qu'est ce que qu'un algo dynamique?
Sais-tu jusqu' à quel n entiers ils ont pu calculer toutes les combinaisons possibles sur les ordinateurs de nos jours?
Merci

[invitea8d03b1e]

bonsoir,

dénombrement des chemin du graphe/combinatoire,
partant d'un élément bien choisis (est-ce pertinent?)

[au pif ]

- à vérifier/éxercer avec un langage quasi quelquonque,
vous permettant d'implémentation un banalisation
du traitement de cette catégorie de chemins... -

[invite4492c379]

Il s'agit d'une discussion en double, tu peux demander à un modérateur de les fusionner ?

[invitea8d03b1e]

il semble que ce soit "plus" mathématique qu'informatique, en effet.

[invite4492c379]

Non, il s'agit du subet sum problem, c'est un problème NP complet. Mais on peut améliorer les perfs ici car la somme initiale est nulle.

[invitea8d03b1e]

Ah oui pardon,
bien que j'inclue la "cryptologie"
et surtout l'algorithmique aussi dans la discipline mathématique.

Graphes et Algorithmes [Gondran et Minoux]


En effet,... Catégories (Problème NP-complet & Logique mathématique).
http://fr.wikipedia.org/wiki/Probl%C...sous-ensembles
sous-ensemble, cryptologie (arithmétique modulaire), partitions, "complétude", P=NP.... Maths? Info?
- mon coeur balance -

En fait, mais là j'exagère, j'inclue l'informatique comme une "extension" d'une "catégorie" de mathématiques (...)

[invitea8d03b1e]

Qu'est ce que qu'un algo dynamique?
...

D'un point de vue informatique,
ce serait ce qu'on appelle la programmation "paresseuse"
- Listes paresseuses (déclaratif)
- Evaluation paresseuse (déclarative)
etc.

http://crteknologies.fr/programmatio...dynamiques.php

[invite332de63a]

Bonjour, tu peux déjà te faciliter le boulot en remarquant que si l'ensemble A a une somme nulle, une partie P de A aussi, alors A\P également. Cela doit pouvoir ainsi réduire les calculs en ne considérant que les partie de cardinal inférieur ou égal à la moitié du cardinal de A.

[JPL]

Fusion de deux discussions et suppression du doublon.

[invite8b421ec7]

Bonjour, tu peux déjà te faciliter le boulot en remarquant que si l'ensemble A a une somme nulle, une partie P de A aussi, alors A\P également. Cela doit pouvoir ainsi réduire les calculs en ne considérant que les partie de cardinal inférieur ou égal à la moitié du cardinal de A.

Pourrais-tu STP m'enxpliquer un peu plus?
Merci.

[invite8b421ec7]

Non, il s'agit du subet sum problem, c'est un problème NP complet. Mais on peut améliorer les perfs ici car la somme initiale est nulle.

Comment? une idée?
Merci.

[invite8b421ec7]

J'ai trouvé l' algorithme meet-in-the-middle utilisé pour résoudre Subset sum problem(voir description ci-dessous). Il est de compléxité O(n2n/2)
Il décompose l'ensemble A en deux sous-ensembles égaux A1 et A2. Ensuite on calcule la somme de toutes les solutions possibles de A1: s1. Ces derniers sont triées puis sauvegradées dans un tableau T. Ensuite, on calcule la somme de toutes les solution possibles de A2: s2. On calcule la différence entre la somme et s2: L. Ensuite rechercher L dans T avec L = s-s2. Si on a touvé . Une solution est X1||X2.
Pourrait-on l'améliorer ? Comment peut-on le perfectionner car la somme de l'ensemble A est nulle.
Merci.

Input: a knapsack vector A = (a1, ..., an) and a sum s. 
Output: a vector X with AX = s, provided a solution exists. 

Divide the knapsack A = (a1, ..., an) into A1 = (a1, ..., at) and A2 = (at+1, ..., an). Here t is n/2, if n is even, else (n-1)/2
For every vector X1 = (x1, ..., xt) 
compute s1 = A1X1 
store s1 togeter with the corresponding x-vector in a table T 
sort this table by the sum 
Now for all possible vectors X2 = (xt+1, ..., xn) 
compute s2 = A2X2 
get the difference L = s - s2 
search L in T. If found, a solution vector is X = X1||X2.

[invite4492c379]

Hello,

Juste par curiosité ... dans quel cadre essayes-tu de résoudre ce problème ? c'est un exercice dans un cours particulier ? Y a-t-il un énoncé précis ?

[danyvio]

Sans entrer dans le détail, il faut aussi remarquer que, pour moins faire exploser le nombre de sous-ensembles, on peut mettre d'un côté les sous-ensembles composés de sommes de nombres positifs, de l'autre les sous-ensembles composés de sommes de nombres négatifs, puis apparier les éléments de l'un et de l'autre et retenir ceux dont la somme est nulle.

[invite8b421ec7]

Hello,

Juste par curiosité ... dans quel cadre essayes-tu de résoudre ce problème ? c'est un exercice dans un cours particulier ? Y a-t-il un énoncé précis ?

. Ce n'est pas un exercice. C'est un projet que j'ai commencé histoire de faire quelque chose pendant le temps libre que j'ai....

[invite8b421ec7]

Sans entrer dans le détail, il faut aussi remarquer que, pour moins faire exploser le nombre de sous-ensembles, on peut mettre d'un côté les sous-ensembles composés de sommes de nombres positifs, de l'autre les sous-ensembles composés de sommes de nombres négatifs, puis apparier les éléments de l'un et de l'autre et retenir ceux dont la somme est nulle.

Si si j'ai besoin de détails. Quelle est la complexité de l'algo dans ce cas?
Merci.

[invite4492c379]

OK, donc aucune hypothèse sur les entiers que tu manipules (du style uniquement entre -200 et +200, que quelques entiers souvent répétés, ...).

Si c'est purement personnel, ce genre de projet va te permettre de :
* chercher des articles sur le net qui explorent ce problème, proposent des solutions
* implémenter ces solutions
* voir des problèmes classiques approchant, comment on résout des problèmes «durs»

Alors où en es-tu dans tes recherches ?

[invite4492c379]

As-tu déjà essayé le problème suivant qui est plus simple à résoudre et qui te montrera comment améliorer un algorithme par étape et par réflexion :
On te donne une liste de n entiers relatifs, il faut trouver la séquence (=une liste d'entiers qui sont consécutifs dans la liste d'origine) dont la somme est maximale.

[invite8b421ec7]

OK, donc aucune hypothèse sur les entiers que tu manipules (du style uniquement entre -200 et +200, que quelques entiers souvent répétés, ...).?

si les entiers sont entre -30 et + 30.

Si c'est purement personnel, ce genre de projet va te permettre de :
* chercher des articles sur le net qui explorent ce problème, proposent des solutions
* implémenter ces solutions
* voir des problèmes classiques approchant, comment on résout des problèmes «durs»

Alors où en es-tu dans tes recherches ?

J'ai cherché sur le net sur des problèmes similaires. La méthode qui propose suppose qu'il n'y a pas de doublons comme l'algorithme plus haut...

[invite4492c379]

si les entiers sont entre -30 et + 30.

J'ai cherché sur le net sur des problèmes similaires. La méthode qui propose suppose qu'il n'y a pas de doublons comme l'algorithme plus haut...

Dans la littérature anglaise, un ensemble qui autorise plusieurs «exemplaires» d'un élément s'appelle multiset.
Entre -30 et +30 ... ça va réduire l'espace de recherche car "plus il y aura d'éléments" et "plus tu aurau des sous listes identiques" ...

Mais comme ce problème est NP complet tu ne trouveras aucun algo polynomial ...
Le plus simple dans un premier temps est de chercher les solutions et d'y ajouter un timeout si ça prend trop de temps.

[invite8b421ec7]

voici mon idée:

A: ensemble d'entiers
Etape 1- diviser A en deux sous-ensembles A₁ et A₂.
A1: ensemble composé d'entiers positifs.
A2: ensemble composé d'entiers négatifs
Etape 2- trouver toutes les sous-listes a_2jde A₂.
Etape 3-calculer la somme de toutes les combinaissons possibles .
Etape 4- Eliminer les doublons de somme dans A₂.
Etape 5 -Sauvegarder les sommes dans T₂
Etape 6- trouver le minimum min dans T₂.
Etape 7- trouver toutes les sous listes de a_1i de A₁ tel que la somme de a_1i> min
Etape 8- Sauvegarder les sommes dans T₁
Etape 9- si T₁[i] == T₂[j] alors L [i]= a_1i inclut a_2j
Qu'en pensez-vous? y-at-il un truc que j'ai loupé? Est ce qu'on peut améliorer? Quelle est la complexité de cet algo?
Merci!

[invite4492c379]

Rapidement ...
Ton étape 2 calcule toutes les sous listes, mais si ta liste est composée de 30 éléments distincts alors tu auras 2³⁰ (~10⁹) sous listes ... ça fait déjà beaucoup

[danyvio]

Rapidement ...
Ton étape 2 calcule toutes les sous listes, mais si ta liste est composée de 30 éléments distincts alors tu auras 2³⁰ (~10⁹) sous listes ... ça fait déjà beaucoup

C'est vrai qu'on se heurte au mur de la combinatoire. Mais comme j'ai programmé avec succès un "compte est bon" je connais un peu ce problème, ou plutôt les améliorations à apporter en cours de route. Il y en a sûrement une flopée, j'en livre une qui me vient à l'esprit :

Ici, perso, je commencerais en prélable à calculer la plus grande somme positive (facile) MAX+ et la plus grande (en valeur absolue) somme négative (facile) MAX-.

Ensuite, au fur et à mesure que je calculerais les sous-ensembles de nombres positifs, j'éliminerais ceux dont la somme est > que MAX- (puisqu'ils n'ont aucune chance d'être annulés par addition).
Pour la même raison, en calculant les sous-ensembles de nombres négatifs, j'éliminerais ceux dont la somme en valeur absolue est > que MAX+

D'autre part, je reprends l'idée de celine2, mais en éliminant les "doublons" au fur et à mesure avant stockage.
Encore faut-il s'entendre sur la notion de doublon. 2+2+6 = 5+5 mais ce ne sont pas doublons au sens de l'énoncé initial puisqu'on recherche toutes les combinaisons. Mais si on trouve 2 sous-ensembles 2+2+6 effectivement c'en est est un...
A suivre...

[invite4492c379]

MAX+ et MAX- seront forcément égaux car la liste de départ est de somme nulle.

[danyvio]

MAX+ et MAX- seront forcément égaux car la liste de départ est de somme nulle.

Certes, mais c'est un cas particulier...

[invite4492c379]

Disons que c'est les spécif de Céline2 (qu'on a du mal à obtenir). Ce cas particulier possède au moins l'avantage d'être plus facile à résoudre (surtout la limite des valeurs entre -30 et 30).