Discussion :

[twilightZone]

bonjour,

Je cherche à programmer le jeu 'Le compte est bon' mais pour n (plus de 8) cartes.
Dans ce cas l'algorithme récursif classique (recherche exhaustive instantanée) qui consiste à avoir un arbre qui calcule toutes les possibilités n'est plus possibles car le temps de calcul devient prohibitif.
http://recursivite.developpez.com/?page=page_5#LIV-G

Il semblerait que l'on puisse utiliser un "algorithme génétique" ou un algorithme par "recherche aléatoire".

Quelqu'un pourrait me donner des pistes sur l'implémentation de ces 2 algorithmes ??

[dourouc05]

L'idée principale est d'éviter la recherche exhaustive pour passer à une recherche locale : au lieu de passer toutes les possibilités, tu y vas au feeling.

Si j'ai bien compris le principe du jeu, on te donne n + 1 cartes, à toi de combiner les n premières pour arriver au nombre inscrit sur la dernière. Les données sont donc les nombres, la solution peut être représentée comme un arbre syntaxique (une représentation d'une formule arithmétique comme 1 + 2 sous forme d'arbre : la racine contient +, avec deux enfants 1 et 2) – cette représentation me semble intuitive, pratique pour l'explication, mais il faudra peut-être en choisir une autre pour te faciliter la vie.

La recherche aléatoire tirera des arbres possibles et testera si le nombre atteint est le bon. Plus précisément, elle partira d'un arbre (tiré au hasard : par exemple, additionner tous les nombres), le testera ; tant qu'il n'est pas bon, elle le modifiera légèrement à l'aide d'heuristiques (changer une addition en soustraction, enlever un nombre, etc., en fonction de ton imagination quand tu codes cette partie et de critères plus ou moins arbitraires : inutile d'ajouter un nouveau nombre si le résultat est trop élevé).

Les algorithmes génétiques sont un poil plus complexes. Au lieu de ne garder qu'une seule solution, qu'un seul arbre, tu en as un certain nombre. Tu associes à chaque élément de la population un score qui indique à quel point la solution est proche de l'objet de ta recherche (ou d'un de ces objets, s'il existe plusieurs solutions : intuitivement, je ne vois pas de raison que la solution soit unique), comme la valeur absolue de la différence par rapport au nombre souhaité : quand le score est nul, tu as ta solution. Ensuite, tant que tu n'as pas la solution, tu effectues une itération : tu mélanges deux ou plusieurs éléments de la population pour en créer un nouveau (des éléments pas forcément choisis au hasard ; l'algorithme de recombination requiert une certaine dose de créativité et de sens artistique : par exemple, si les deux solutions additionnent des sous-expressions, tu peux envisager de créer deux nouveaux enfants, pour faire toutes les combinaisons possibles de somme) ; certains individus décèdent (de préférence, les solutions les plus éloignées de l'objectif et qui n'ont pas beaucoup de chance d'arriver à une solution faisable par les itérations suivantes, afin de maintenir une population de solutions à un niveau raisonnable) ; certains individus mutent (ce qui revient à utiliser les heuristiques précédentes) – certains auteurs considèrent que seuls les nouveaux-nés peuvent muter.

La programmation génétique requiert de définir pas mal de paramètres et d'algorithmes, qui peuvent tous fortement influencer l'efficacité de la procédure. Dans les deux cas, l'aléatoire a une énorme contribution ; également, ton sens artistique sera vraiment à l'œuvre pour coder les parties spécifiques au problème : ces algorithmes ne ressemblent pas vraiment à ta recherche par récursion . Par contre, cet algorithme exact pourra t'aider à trouver des heuristiques qui ont du sens, qui amènent plus rapidement à la solution (si tu remarques que ta recherche exhaustive génère des solutions qui, très légèrement modifiées, tombent directement sur la bonne solution, assez souvent, c'est une bonne heuristique – mais le constat peut fortement dépendre du nombre de cartes : une bonne heuristique pour six cartes peut être exécrable pour douze).

Pour plus d'informations, le problème des huit reines (généralisé à ) est, il me semble, plus étudié sur le Web, tout en ayant une structure proche. Par exemple, http://mnemstudio.org/genetic-algori...troduction.htm me paraît intéressant. Avant de te lancer dans ce problème, il pourrait être intéressant de refaire les huit reines avec ces métaheuristiques, histoire de bien saisir tous les concepts.

[twilightZone]

Avant toute chose, je te remercie d'avoir passé autant de temps à me répondre, c'est vraiment très gentil.

Tu as parfaitement compris le problème, il s'agit de trouver la solution au jeu le compte est bon mais avec plus de 6 cartes.
Par exemple pour
3866
avec les cartes
9 2 50 7 3 10 25

Le résultat est
9+7=16
3*25=75
75+2=77
77*50=3850
3850+16=3866

Avec 7 cartes, une méthode brute est acceptable mais après il y a trop d'itérations.
Comme je n'ai jamais fait de recherche aléatoire ni de recherche génétique, c'est un bon test mais j'avoue que c'est un peu compliqué.
Encore merci pour ta réponse, si j'arrive à quelque chose je mettrais un post (ce n'est pas certain :-))
Patrick

[Canvas]

Bonsoir,

Je ne sais pas si cela peut servir de point de départ pour dégrossir le calcul, mais l'une des stratégie humaine (donc non-aléatoire) pour résoudre Le compte est bon dans le jeux télévisé consiste à utiliser la carte la plus forte (en général 100 ou 75 multiplié par une autre carte) pour s'approcher le plus possible du résultat final. Ensuite on utilise le reste des cartes plus petites pour affiner le calcul.

----
Canvas

[cgMorpheus82]

Bonjour,

J'ai tester avec

3866
avec les cartes
9 2 50 7 3 10 25

Et le programme (algo récursif type brute force) met 32ms pour trouvé le calcule.
Je trouve pas ça prohibitif.

[10_GOTO_10]

Si je comprends bien la règle du jeu, le but est de trouver un arbre binaire tel que l'arbre ci-dessous, où chaque lettre est un nombre, et chaque "@" est une des 4 opérations. J'appelle un nombre soit une des huit cartes, soit le résultat (unique) de l'opération qui est au dessus (blanc si un des opérandes au dessus est lui-même blanc)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
A B C D E F G H I J K L M N O P
 @   @   @   @   @   @   @   @
 Q   R   S   T   U   V   W   X
   @       @       @       @
   Y       Z       a       b
       @               @
       c               d
               @
               e

Par exemple, avec l'exemple donné ci-dessus, on a l'arbre suivant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
3 25 ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ??
 *     @     @     @     @     @     @     @
 75    2    ??    ??    ??    ??    ??    ??
    +           @           @           @
   77          50           9           7
          *                       +
         3850                    16
                       +
                     3866

Un arbre de niveau N contient 2^N - 1 nombres et 2^(N-1) - 1 opérations. Notre exemple contient 5 niveaux donc 31 nombres (2^5 - 1) et 15 opérations (2^4 - 1).

En termes de combinatoire, explorer tous les arbres de niveau 5 nécessite donc de tester 31 * 9 * 15 * 4 = 16740 combinaisons possibles pour 8 cartes (31 nombres * 8 cartes + blanc * 15 opération * 4 valeurs possibles pour une opération). 16740 cas à tester, avec des entiers et les opérations de base, en informatique, c'est une affaire de quelques millisecondes tout au plus. D'autant plus que le nombre de niveaux est, me semble-t-il, limité (Au début j'avais écrit N+1 niveaux maximum pour N cartes, mais c'est plus compliqué). Donc on peut tester une solution en 3 niveaux, puis en 4, 5, jusqu'au maximum ou bien s'arrêter si une solution a été trouvée.

Je fais abstraction du fait qu'une carte ne doit être utilisée qu'une seule fois. Cette contrainte devra être vérifiée après coup lorsqu'une solution sera trouvée.

[edit] en fait c'est pas compliqué du tout, une solution pour N cartes contient au plus N niveaux : la première ligne doit comporter au moins deux nombres pour qu'aucun des opérandes soit blanc, et comme dans ce cas on n'a qu'un résultat calculé, chaque ligne sauf la dernière doit avoir un nouveau nombre venant d'une carte. [/edit]

[10_GOTO_10]

La nuit porte conseil...

D'abord je voudrais corriger la bête erreur de dénombrement que j'ai faite: le nombre de combinaisons n'est pas 31 * 9 * 15 * 4 comme je l'ai écrit, mais plutôt 9 ^ 31 * 4 ^ 15 ce qui fait... légèrement plus (409654436471130063202143433004591087616 pour être exact).

En fait, je pense qu'on ne trouvera pas d'algorithme réalisable : En y réfléchissant, le "compte est bon" et un sur-ensemble du "problème du sac à dos" qui est une sorte de "compte est bon" avec une seule opération, l'addition. Or on sait que ce problème est NP-complet, donc pratiquement impossible à résoudre dès que les données de départ deviennent un peu nombreuses.

[twilightZone]

Bonjour,
J'ai fait une routine qui est récursive car je n'ai rien trouvé d'autre.
Par contre les optimisations sont très nombreuses
Pour chaque pair de carte, on a 4 opérations possibles (+ - * /)
La plupart des opérations sont commutatives donc a + b = b +a et a*b = b*a
De plus la division doit être entière donc 3/6 est interdit mais 6/3 est autorisé 7/2 et 2/7 sont interdits
si a ou b sont égales à 1 la multiplication ou la division est inutile
pour la soustraction le résultat doit être positif donc 3 -5 est interdit et 5 - 3 est autorisé
Si le fait de combiner deux cartes a et b donnent une troisième carte c qui vaut a ou b, c'est inutile ainsi 6 - 3 = 3 est inutile ou 4/2 = 2
En gros quand on combine 2 cartes avec les 4 opérations on a au maximum (et très rarement) 4 combinaisons possibles
Dans la plupart des cas c'est 3 ou moins.
Ainsi avec 5 et 7 on aura 5+7 7-5 et 7*5
Après pour faire encore plus fort on peut couper des branches de l'arbre en évitant de ré-examiner des cartes qui auraient données le même résultat
Ainsi si avec les cartes 10, 7, 2 on a déjà trouvé la valeur (10 - 7) + 2 = 5 il est inutile de considérer (10 + 2) - 7 = 5

[Jpittelo]

Je ne sais pas si c'est une classe différente de problème mais le compte est bon peut être complexifié en au compte le plus près et alors à mon avis il est aussi difficile de vérifier la solution.