Algorithme nase

En dehors d'écrire des mauvaises blagues sur ce forum, et jouer un spectacle tous les 32 du mois, je suis théoriquement étudiant en informatique. J'aimerai partager avec vous une déconvenue qui m'énerve un peu. Parce que si vous lisez, on sera plus à perdre du temps sur une mauvaise idée, et on se sent mieux quand on est pas seul à faire des trucs bêtes.

Il a été posé sur le forum de l'école la question suivante:

Si on appelle produit d'un ensemble le produit de ses éléments, et si on dit que la valeur d'un sous-ensemble S de E est la somme du produit de S et du complémentaire de S, alors est-il possible de trouver pour chaque ensemble de cardinal pair le sous-ensemble de valeur minimal en temps polynomial.

Vous suivez? Sinon plus clairement, on a une liste de nombre avec un nombre pair d'élément. Par exemple 1, 2, 3, 4, 5, 6, et il faut choisir la moitié de ces nombres. Par exemple si on choisit 1,2,3 alors la valeur est (1*2*3)+(4*5*6)=6+120=126. Alors on cherche à diminuer cette valeur. Ici ce n'est pas bon, par exemple, si on prenait 1,2,6 alors on aurait la valeur (1*2*6)+(3*4*5)=12+60=72 qui est plus petit que 126.

On peut essayer de regarder la valeur de tous les choix de nombre bien sur, mais ça prend énormément de temps, plus exactement un temps factoriel. Donc c'est iréalisable pour les listes de 100 nombres par exemple. Ou alors avec des années de calcul.



J'y ai pensé quelque temps, et me suis dit que ça devait pouvoir marcher avec un algorithme glouton. On créé au fur et à mesure le sous ensembles E et son complémentaire C, avec au départ deux ensemble vide. Pour chaque nombre qu'on voit, on le rajoute à E si le produit de E est inférieur au produit de son complémentaire.

Par exemple, au départ on a E={} et C={}, On a 6 à placer quelque part, par exemple E, alors E=6, C={}, le produit de E est 6, alors que celui de C est 1 (car C est vide), donc le prochain nombre, 5, sera rajouté dans C. On a E=6, C=5. Là puisque 5 est plus petit que 6, le prochain nombre, 4, est rajouté dans C, alors E=6 et C=5,4, le produit de C est alors 5*4=20, et le prochain est rajouté en E, donc on a E=6,3. A la fin, on a comme sous ensemble E=6,3,2. Et la valeur est donc (6*3*2)+(5*4*1)=36+20=56, qui est d'ailleurs inférieur au 72 qu'on avait trouvé tout à l'heure. Donc on est en bonne voie.

A priori, l'idée est bonne, à chaque fois qu'on doit placer un nombre, on multiplie dans l'ensemble où le produit est aussi petit que possible, comme ça on évite de faire monter la valeur. Bien sur, il faut s'arrêter quand on a mis dans l'ensemble ou son complémentaire la moitié des éléments, il ne faut pas en mettre trop.

Le seul problème, c'est que je n'arrive pas à trouver de preuve pour montrer que cet algorithme donnera toujours la meilleur solution ! J'ai beau retourné le problème dans ma tête, regarder par récurrence, à l'aide de matroide, ou pourquoi pas de potentiel (mais ça serait surprenant que la méthode du potentiel fonctionne)

Bien sur il y a la possibilité que cet algorithme soit simplement mauvais, en attendant, pour vérifier si ça pouvait marcher, j'ai programmé (en oCaml) cet algorithme, et j'ai vérifié pour quelques ensembles si on obtenait effectivement la meilleure solution. J'ai comparé en testant sur tous les choix de sous-ensembles possible. Et là je vois que le meilleur sous ensemble c'est 6,4,1 car alors la valeur est (6*4*1)+(5*3*2)=24+30=54. Donc mon algorithme a raté ! J'ai donc perdu pour rien au moins une heure à programmer, et plus à chercher à prouver cette algorithme qui était faux !

Et encore au moins une demi heure à taper ce billet.

Sniff

Commentaires

1. Le mardi 2 juin 2009, 10:06 par Typhon

Si C est vide, son produit n'est pas zéro ? ça contredit pas la def que t'as donnée au dessus ?

Typhon

2. Le mardi 2 juin 2009, 21:08 par Le Créateur Fou

Pas d'bol, hein?
Je ne peut malheuresement rien pour toi. J'ai pu comprendre la situation, et c'est déjà pas si mal.
Bon courage, par contre!

3. Le mardi 2 juin 2009, 21:16 par Blaireauman

Demande à un matheux de l'ENS de te résoudre ça formellement en algèbre, et vois ensuite comment traduire en algorithme, c'est le meilleur conseil que je peux te donner.

Si j'ai bien compris, tu as un ensemble (liste) E contenant n=2p éléments, avec p entier, tu cherches à scinder E en 2 sous ensembles S1 et S2, de telle manière que le produit des p éléments de chaque sous ensemble soit tel que leur somme soit minimale.

Si A=produit(S1) et B=produit(S2), tu cherches donc Min(A+B), ton problème étant que l'égalité Min(A+B)=Min(A)+Min(B) ne peut pas t'aider à résoudre quoi que ce soit, puisque les valeurs de A et B sont interdépendantes (tu ne peux faire que des permutations d'éléments entre A et B pour changer la valeur de l'un, ce qui change aussi la valeur de l'autre)

Donc j'en reviens à ce que disais, demande à un matheux pur et dur, de préférence une grosse brute dans sa matière.

4. Le mercredi 3 juin 2009, 00:18 par Arthur Rainbow

Typhon, non, le produit d'un ensemble vide est bien 1.
Le produit de m nombres, c'est le numéro m fois le produit des m-1 premiers, donc le produit d'un élément, c'est cet élément fois le produit de 0 éléments, il faut donc que le produit de 0 élément soit 1.
Plus généralement, en considérant le monoide (M,.) quand on applique . 0 fois, on dis que le résultat est l'élément neutre de M.

Visiblement, la question vient de gens de maths, et je t'assures que les matheux fréquentent le forum de l'école, donc si ça suffisait, je pense qu'ils auraient trouvé.

Ajouter un commentaire

Le code HTML est affiché comme du texte et les adresses web sont automatiquement transformées.

La discussion continue ailleurs

URL de rétrolien : http://www.milchior.fr/blog/index.php?trackback/84

Fil des commentaires de ce billet