Algorithme "Des chiffres et des lettres" - Page 1

En ce moment, j'essaye de programmer en TI-Basic un algorithme inspiré du jeu "des chiffres et des lettres". Le but est le suivant :
L'utilisateur donne quelques chiffres simples (1, 2, 3, 5, 10...) puis un nombre "but" et la calculatrice doit trouver une opération en utilisant
chaque chiffre une seule fois et uniquement les opérations de base (+, -, *, /) qui permet d'arriver au nombre "but".
Par exemple, si j'entre 1,3,4,7 et 50 comme nombre but, la calculatrice me retournera quelque chose comme (7+3)*(4+1).

Pour l'instant, le programme fonctionne mais est extrêmement lent : pour 3 chiffres simples, il faut compter au moins 5 minutes de recherche, et pour 4 chiffres, plus d'une heure. Les routines utilisées sont principalement des routines récursives (avec un nombre souvent assez élevé de récursions). Avez vous des idées d'optimisation ?

Edit: L'algorithme que j'utilise actuellement consiste simplement à essayer toutes les combinaisons possibles

changer de langage ?

pour des raisons pratiques (notamment la flemme) je préfère rester en Ti Basic

eviter les appels recursifs, deja...

À moins que ton code ne soit trop long (> 100 lignes), tu peux peut-être le poster ici, ça sera plus parlant pour essayer de trouver des optimisations (en tout cas des optimisations plus intelligentes que "changer de langage").

Pourquoi "plus intelligentes"? Passer en C résoudrait sans doûte tous les problèmes de vitesse.

On peut peut-être faire mieux qu'un algo polynomial.

Tu as essayé de chercher "le compte est bon" algorithme sur google ? parce que des gens s'y sont sûrement déjà intéressés ^^

Sinon pour ce type de problème il n'existe pas vraiment d'autre solution exacte que d'essayer toutes les combinaisons possibles ; c'est sans doute possible de réduire d'un certain facteur le temps mis en suivant les conseils de liquid et Yoshi, mais ça n'aboutira pas à des miracles (même si tu arrives à diviser le temps par 100 mettons, tes 5 minutes deviendront trois secondes ce qui est acceptable, ton heure deviendra 36 secondes, mais si tu veux résoudre le problème avec 5 nombres ça prendra toujours très longtemps...)
Ceci dit il est vrai que passer à un langage compilé te fera sans doute gagner un facteur beaucoup plus grand que 100 (enfin je ne connais pas du tout les caractéristiques du TI-Basic, mais ça me semble probable), donc tu pourras peut-être aller jusqu'à 6 ou 7 nombres².

Mais si tu veux résoudre le problème avec plus de nombres il te faudra chercher une solution approchée (= tu n'es pas sûr que c'est la meilleure solution possible — sauf si ça tombe exactement sur le nombre, bien sûr, mais bon¹ ^^) en utilisant des heuristiques.

¹je suppose que tu as déjà fait l'optimisation consistant à ne pas continuer à chercher si tu tombes sur une telle solution ? ^^
²Mais bon comme dit Zephyr l'exercice manque d'intérêt, et si le but est juste d'avoir des solutions du compte est bon on peut sûrement télécharger des trucs sur internet

Kevin Kofler (./6) :
Pourquoi "plus intelligentes"? Passer en C résoudrait sans doûte tous les problèmes de vitesse.

Parceque quand on poste dans "algorithmie et optimisation", je suppose qu'on s'attend à quelque chose d'un peu plus fin que changer de langage. Et puis c'est quand même nettement moins intéressant que de chercher des solutions plus efficaces.

Et puis surtt, un algo de merde, restera un algo de merde et pourra etre plus lent en C qu'un algo correct en Ti Basic...

Zephyr (./5) :
À moins que ton code ne soit trop long (> 100 lignes), tu peux peut-être le poster ici, ça sera plus parlant pour essayer de trouver des optimisations (en tout cas des optimisations plus intelligentes que "changer de langage").

En fait mon code est beaucoup plus long que 100 lignes, notamment à cause des sous-programmes se chargeant d'évaluer ou d'afficher les opérations (que je stocke sous forme de listes en utilisant un format de "notation polonaise" (càd l'opération est notée en préfixe et non en infixe) qui permet de se passer de parenthèses).

Sally (./8) :
¹je suppose que tu as déjà fait l'optimisation consistant à ne pas continuer à chercher si tu tombes sur une telle solution ? ^^

oui heureusement j'y ai pensé

Sally (./8) :
Tu as essayé de chercher "le compte est bon" algorithme sur google ? parce que des gens s'y sont sûrement déjà intéressés ^^

http://www.lucas-nussbaum.net/writings.php?lceb
Malheureusement, la solution récursive proposée est celle que j'utilise, et la solution dynamique est difficilement imaginable à implémenter sur la TI, surtout en Basic...

Oui d'ailleurs « essayer toutes les solutions possibles » n'est pas vraiment une description de l'algorithme, j'ai dit qu'on ne pouvait pas vraiment faire mieux que ça mais ça ne veut pas dire qu'on ne peut pas améliorer ce que tu as fait : il n'y a certainement pas qu'une seule manière d'essayer toutes les possibilités...

exemple au pif : si a et b sont deux de tes nombres, il existe un grand nombre de possibilités où intervient a*b ; tu dois a priori tester toutes ces possibilités, mais ça ne veut pas dire que tu dois recalculer a*b à chaque fois.

Mais sans savoir ce que tu as fait, c'est difficile de donner autre chose que des exemples au pif ^^

J'essaie de majorer rapidement le nombre de solutions pour 4 nombres. A priori on n'a pas de buts négatifs ou non entiers (?) donc il n'y a qu'une seule manière d'appliquer une opération à deux nombres (si c'est une soustraction on soustrait toujours le plus petit du plus grand, idem pour une division). Donc pour choisir les deux premiers nombres tu as 6 possibilités (s'ils sont tous différents), fois 4 opérations, ça fait 24. Pour la deuxième opération il te reste trois nombres, tu as trois manières d'en choisir deux, fois 4 opérations, ça fait 12, et ensuite il te reste à choisir la troisième opération, 4 possibilités.

Donc au total il y a au plus 24×12×4 = 1152 possibilités. Ça ne semble pas vraiment énorme, si ton programme met une heure à toutes les tester c'est qu'il met plus de trois secondes par possibilité (et encore, normalement c'est seulement dans le pire cas qu'il va toutes les tester), ça me semble assez long : c'est certainement possible d'optimiser même en gardant l'idée de tester toutes les possibilités...

(cross)

Ce qu'il demande est relatif à de l'optimisation combinatoire en recherche opérationnelle. On a à faire à un problème de classe NP.
Ça s'approche du problème du sac à dos.
http://fr.wikipedia.org/wiki/Probl%C3%A8me_du_sac_%C3%A0_dos
L'algorithme glouton pourrait donner des résultats intéressants mais pas optimal (si le but est d'arriver à un résultat sans minimiser les opérations ça doit suffire). Mais sachant que le problème peut être modélisé sous forme d'arbre, personnellement, j'utiliserai l'algorithme de "branch and bound"
http://fr.wikipedia.org/wiki/S%C3%A9paration_et_%C3%A9valuation

Lucas Nussbaum, son nom me disait quelque chose et là je vois qu'il a fait des TD à l'ensimag

merci pour vos commentaires, j'ai réussi à créer un code récursif à peu près potable en TI-Basic qui prend un peu de temps pour trouver une solution avec 5 chiffres, mais qui va plus vite que moi pour 4 chiffres (je ne prétends pas être une référence...). Je le poste ici dès que j'arrive à faire marcher TI-Connect.

Sally (./12) :
exemple au pif : si a et b sont deux de tes nombres, il existe un grand nombre de possibilités où intervient a*b ; tu dois a priori tester toutes ces possibilités, mais ça ne veut pas dire que tu dois recalculer a*b à chaque fois.

Si l’algorithme est récursif, a*b ne sera pas recalculé mais passé en argument de la « méthode à N-1 arguments » (façon de parler).

Sally (./12) :
A priori on n'a pas de buts négatifs ou non entiers (?) donc il n'y a qu'une seule manière d'appliquer une opération à deux nombres (si c'est une soustraction on soustrait toujours le plus petit du plus grand, idem pour une division).

Oh, très bien vu !
Certes, on pourra argumenter du fait que l’on ait envie de calculer (4-9)+12, avec donc un nombre intermédiaire négatif, mais quand on va calculer (12-9)+4, on trouvera de toute façon le même résultat, donc autant éliminer immédiatement les cas dont on sait qu’ils réapparaîtront sous une autre forme lors de la recherche exhaustive des cas possibles.

Sally (./12) :
J'essaie de majorer rapidement le nombre de solutions pour 4 nombres. […] Donc pour choisir les deux premiers nombres tu as 6 possibilités (s'ils sont tous différents), fois 4 opérations, ça fait 24. Pour la deuxième opération il te reste trois nombres, tu as trois manières d'en choisir deux, fois 4 opérations, ça fait 12, et ensuite il te reste à choisir la troisième opération, 4 possibilités.
Donc au total il y a au plus 24×12×4 = 1152 possibilités.

Il s’agit d’ailleurs du décompte de l’algorithme récursif, dans lequel la « méthode à 4 arguments » ([ie.[/i] avec en argument une liste de 4 valeurs, pour l’implantation) fait 24 appels à elle-même, mais « avec 3 arguments » (laquelle faut 12 appels à elle-même « avec 2 arguments ».

De mon côté, je suis d’abord parti en explicitant, pour N=2 à 5 nombres, les différents « arbres de calcul » et en permutant ensuite les nombres dans ces arbres.
Exemple : pour N=4, on a 2 arbres différents (le signe ¤ représente 1 des 4 opérations) :[ul][li]((A¤B)¤C)¤D => 768 possibilités maximum ;[/li][li](A¤B)¤(C¤D) => 384 possibilités maximum.[/li][/ul]On retrouve bien les 1152 possibilités annoncées plus haut.
Puis, en cherchant la construction de l’ensemble des arbres à N nombres à partir des arbres à N-1 nombres, pour en déduire la formule de récurrence sur le nombre maximum de possibilités.

En bref, le nombre maximum de possibilités à N nombres vaut :[ul][li]Nmp(2) = 4[/li][li]Nmp(N>2) = 4^(N-2) × (N-1) × N![/li][/ul]

Notez que Nmp(4) = 1152 et Nmp(5) = 30720, et donc que Nmp(5)/Nmp(4) = 80/3 et non 40 comme on s’y attendrait en suivant le raisonnement de Sally (avec lequel plusieurs arbres de calcul sont en double).
Démonstration complète à la demande …

Mais attention, il s’agit d’un simple majorant (à peine plus recherché que celui de Sally qui m’a quand même ouvert la voie) qui ne donne pas grand chose sur l’algorithme de recherche exhaustive (à part le fait qu’il sera récursif ).

My two cents.

Ethaniel (./16) :
Oh, très bien vu !Certes, on pourra argumenter du fait que l’on ait envie de calculer (4-9)+12, avec donc un nombre intermédiaire négatif

Tu peux toujours faire "redescendre" le signe moins pour qu'il s'applique uniquement aux feuilles (donc ici ça donnerait 12-(9-4) ; ton exemple utilisait l'associativité, c'est overkill et ça ne marche pas dans tous les cas)

Ethaniel (./16) :
Mais attention, il s’agit d’un simple majorant (à peine plus recherché que celui de Sally qui m’a quand même ouvert la voie) qui ne donne pas grand chose sur l’algorithme de recherche exhaustive (à part le fait qu’il sera récursif ).

La suite que tu cherches est http://www.research.att.com/~njas/sequences/A001147 à un facteur 4^(n-1) près. Asymptotiquement elle est plus grande que ta suite, donc je doute que la tienne soit un majorant

(ah tiens en fait elle y est aussi avec 4^(n-1), et même en double http://www.research.att.com/~njas/sequences/?q=4,48,960,26880&sort=0&fmt=0&language=english&go=Search )

Pollux (./17) :
Tu peux toujours faire "redescendre" le signe moins pour qu'il s'applique uniquement aux feuilles

C’est bien ce que je dis : même s’il y a a priori 6 manières de combiner 2 nombres positifs A et B et une des 4 opérations — à savoir A+B=B+A ; A-B ; B-A ; A*B=B*A ; A/B ; B/A —, on peut en réalité se contenter de 4 combinaisons différentes pour, au final, arriver quand même à couvrir tous les résultats possibles — à savoir A+B=B+A ; A--B=B--A=abs(A-B) ; A*B=B*A ; A//B=B//A=max(A,B)/min(A,B).
D’où 4^(N-1) et non 6^(N-1).

Pollux (./17) :
La suite que tu cherches est http://www.research.att.com/~njas/sequences/A001147 à un facteur 4^(n-1) près.

Ah oui, tiens !

a(n) is the number of distinct products of n+1 variables with commutative, nonassociative multiplication. - Andrew Walters

En effet, c’est tout à fait ça !
Comment as-tu trouvé cette suite ?
Effectivement, pour les cas N=4 et N=5 (je rappelle que je m’étais arrêté là), et en comparant avec l’exemple donné sur ta page, je m’aperçois que j’avais compté quelques arbres en double, et le bon dénombrement donne maintenant la même chose que ta suite, ouf  !

Pollux (./17) :
Asymptotiquement elle est plus grande que ta suite, donc je doute que la tienne soit un majorant

En effet : jusqu’à N=5, je comptais trop de cas, mais dès N=6, j’en compte moins (900×4^5 au lieu de 945×4^5) .
Finalement, j’aurais dû aller jusqu’à N=6 avant de me lancer dans la récurrence …
Bon allez, au boulot, moi !
Même si je n’entends pas redémontrer totalement le résultat d’Andrew Walters, j’aimerais quand même voir où je me suis planté dans mon dénombrement des arbres de calcul…

Pollux (./17) :
(ah tiens en fait elle y est aussi avec 4^(n-1), et même en double http://www.research.att.com/~njas/sequences/?q=4,48,960,26880&sort=0&fmt=0&language=english&go=Search )

Ne faudrait-il pas prévenir les admins du site que la seconde suite, qui date seulement du 21 septembre dernier, fait doublon avec la première ?

Ethaniel (./18) :

Pollux (./17) :
La suite que tu cherches est http://www.research.att.com/~njas/sequences/A001147 à un facteur 4^(n-1) près.

Ah oui, tiens !

a(n) is the number of distinct products of n+1 variables with commutative, nonassociative multiplication. - Andrew Walters

En effet, c’est tout à fait ça !Comment as-tu trouvé cette suite ?

Si tu appelles ta suite c[n] tu as la relation :
c[0] = 0
c[1] = 1
c[n] = 1/2 sum[k=0..n] C(n,k) c[k] c[n-k] pour n>1

Si tu poses c'[n] = c[n]*2^(n-1) ça te donne une relation un peu plus simple
c'[0] = 0
c'[1] = 1
c'[n] = sum[k=0..n] C(n,k) c'[k] c'[n-k] pour n>1
( http://www.research.att.com/~njas/sequences/A001813 )
C'est la version étiquetée des http://en.wikipedia.org/wiki/Catalan_number (on peut aussi faire le lien avec les nombres de Catalan directement : c'[n] = catalan[n-1]*n! puisque pour avoir une version étiquetée d'un arbre non étiqueté il suffit de rajouter une permutation quelconque des feuilles, et c[n]*2^(n-1) = c'[n] puisque pour avoir une version asymétrique d'un arbre symétrique il suffit de rajouter une information de direction à chaque noeud).


Ou bien tu peux trouver l'expression de c' directement en notant tes arbres en RPN : si tu rajoutes à tes n nombres n-1 opérateurs distincts o1..on-1 (donc au total tu as un alphabet A à 2n-1 éléments), tu peux faire correspondre à chaque arbre son expression RPN, qui est une permutation de A. Mais si tu prends une permutation quelconque de A, ça ne correspond pas toujours à une expression RPN... Heureusement il existe une unique permutation circulaire de ta permutation qui correspond à une vraie expression RPN : si tu notes p[k] la profondeur de la pile (éventuellement négative) avant le k-ème symbole, tu prends le plus grand k tel que p[k] soit minimale et en faisant une rotation de k éléments tu obtiens une expression RPN (et c'est le seul k vérifiant cette propriété). Ca te donne une relation d'équivalence entre permutations de A, et chaque classe d'équivalence a 2n-1 éléments. Donc il y a (2n-1)!/(2n-1) = (2n-2)! arbres utilisant o1..on-1. Puisqu'on veut un seul opérateur, il faut diviser par le nombre de permutations de o1..on-1 : ça donne bien c'[n] = (2n-2)!/(n-1)!

Ne faudrait-il pas prévenir les admins du site que la seconde suite, qui date seulement du 21 septembre dernier, fait doublon avec la première ?

Essaye toujours (par contre je crois que les contributions anonymes sont refusées, mais dans la mesure où c'est pas vraiment une contribution je sais pas trop)

Quand je demandais « Comment as-tu trouvé cette suite ? », je voulais dire « Comment as-tu trouvé la suite répondant au problème, sur les quelques milliers de suites du site ? »

Pour ce qui est de ma formule pourrie, le fait qu’elle ne marche pas pour N=2 aurait dû me mettre la puce à l’oreille pour m’apercevoir que ma récurrence était foireuse …
La prochaine fois, j’irai au moins jusqu’à N=7  !

Ethaniel > ben tu peux chercher une suite par ses premiers nombres

Ethaniel (./20) :
Quand je demandais « Comment as-tu trouvé cette suite ? », je voulais dire « Comment as-tu trouvé la suite répondant au problème, sur les quelques milliers de suites du site ? »

Ah ben c'est très facile, tu tapes 3-4 termes de la suite et voilà ^^ (c'est tout l'intérêt du sloane)

La prochaine fois, j’irai au moins jusqu’à N=7  !

Si une suite majore une autre jusqu'à N=7, c'est certainement vrai pour tout N

Pollux (./22) :

Ethaniel (./20) :
Quand je demandais « Comment as-tu trouvé cette suite ? », je voulais dire « Comment as-tu trouvé la suite répondant au problème, sur les quelques milliers de suites du site ? »

Ah ben c'est très facile, tu tapes 3-4 termes de la suite et voilà ^^ (c'est tout l'intérêt du sloane)

Ah, donc tu as d’abord calculé les premiers termes de la suite de ton côté, sans te laisser embobiner par Sally ou moi  ?

j'ai lu en diagonale, mais de toute façon ce que vous calculiez c'était juste un majorant et pas l'expression exacte si ?

euh perso j'ai juste calculé un majorant rapide pour 4 nombres oui (le but étant simplement de montrer que son truc était lent même pour un algo explorant toutes les possibilités même en basic ^^)

Oui oui, juste un majorant.
Le nombre réel de résultat sera inférieur s’il y a des nombres identiques (au départ ou en cours de récurrence), mais ça, on ne peut pas le déterminer dans le cas général.
Le résultat d’Andrew Walters est donc, à mon avis, le meilleur majorant possible dans le cas général.

(je sais pas si le résultat est de lui, c'est juste que c'est lui qui l'a mis dans la base de données)


Et la suite que j'ai postée est un majorant de la complexité, mais c'est aussi la cardinalité exacte du nombre d'arbres à 4 opérateurs symétriques... Donc "majorant" voulait dire majorant de cette cardinalité, pas majorant de la complexité ^^

Si tu parles de la complexité exacte c'est forcément moins que ça puisqu'on a pas pris en compte l'associativité de l'addition/multiplication, ou encore le fait que a-(b-c) = a-b+c. On a juste supposé qu'on avait des opérateurs commutatifs opaques...

On est bien d’accord .

ben moi je suis pas d'accord avec ça :

Ethaniel (./26) :
Le résultat d’Andrew Walters est donc, à mon avis, le meilleur majorant possible dans le cas général.

Tu as mieux ?
J’entends dans le cas général, c’est-à-dire sans savoir si des paires (voire n-uplets) de nombres vont apparaître en cours de route.