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