Discussion :

[roberto44]

Bonjour,
Quelqu'un disposerait-il de l'algorithme de réduction de mise lotofoot utilisé par les sites de type reducmiz.com, pronosoft.com etc. ?
Pour le premier, je suis surpris de la vitesse de calcul. J'ai testé 15 triples (en garantie N-1 avec 100% de couverture) et le résultat optimal s'affiche quasi instantanément !!! Comment font ils ?!! J'ai testé plusieurs combinaisons et le résultat est tout aussi ahurissant.

J'ai fait un petit programme avec des itérations et des fonctions récursives etc. et je pars dans des temps de calculs longs sans forcément obtenir le résultat optimal au bout.

Si quelqu'un a connaissance des méthodes de calcul ou de l'algorithme utilisé par ces sites, j'aimerais comprendre.

Merci

[tbc92]

Je viens d'expérimenter ReducMiz, je ne connaissais pas du tout. Si je devais faire la même chose, je ferais un recensement de toutes les configurations. 4 possibilités pour le Pourcentage de garantie * 3 possibilités pour le nombre d'erreurs * environ 100 possibilités pour le nombre de doubles ou de triples, ça ne fait pas beaucoup.

En effet, si un joueur jouer 12 simples + 3 triples pour les matches 1 2 3 ou bien 12 simples + 3 triples pour les matches 4 5 6 , c'est la même chose.

Je calculerais les réponses pour ces 1200 scénarios, et je stockerais tout ça dans une base de données. Et je n'aurais quasiment plus qu'un traitement d'affichage à effectuer pour chaque requête.

[roberto44]

Merci, mais même avec une technique comme celle que tu décris, je ne m'explique pas comment ils parviennent à trouver une combinaison optimale pour des grilles très complexes !!!

[bm]

Si toutes les config sont stockées dans une base NoSql ( clef , valeur )
Chaque clef donne une valeur instantanée

[tbc92]

Même pour une grille très complexe, c'est du parcours d'arbre. Si on le fait de façon brutale, on envisage toutes les combinaisons, et on retient une solution parmi celles qui sont le plus avantageuses en respectant l'objectif fixé.

[roberto44]

En effet, je pense aussi que c'est du parcours d'arbre mais quel est l'algorithme de parcours de cet arbre ?

[anapurna]

salut

pour le parcours d'une grille c'est assez simple
en connaissant la largeur et la hauteur l'algorithme est

Code :

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

1
2
3
pour tout i de 0 a largeur faire
  pour tout j de 0 a hauteur faire 
    Mon_traitement(i,j)

pour les arbres
il existe différente solution

pre-ordre :

Code :

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

1
2
3
4
5
6
7
8
9
 
parcourir ( Arbre ) 
faire
  si Arbre différent de nul  alors 
    Mon_traitement(info(Arbre.Racine)) ; 
    parcourir ( Arbre.filsG ) ; 
    parcourir ( Arbre.filsD ) ; 
  Finsi 
FinFaire

Post-order

Code :

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

1
2
3
4
5
6
7
8
9
 
parcourir ( Arbre ) 
faire
  si Arbre différent de nul  alors 
    parcourir ( Arbre.filsG ) ; 
    parcourir ( Arbre.filsD ) ; 
    Mon_traitement(info(Arbre.Racine)) ; 
  Finsi 
FinFaire

ordre infixé :

Code :

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

1
2
3
4
5
6
7
8
9
 
parcourir ( Arbre ) 
faire
  si Arbre différent de nul  alors 
     parcourir ( Arbre.filsG ) ; 
     Mon_traitement(info(Arbre.Racine)) ; 
     parcourir ( Arbre.filsD ) ; 
  Finsi 
FinFaire

hiérarchique ou en largeur :
pour celui-ci il faut utiliser une pile supplémentaire

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
parcourir ( Arbre ) 
  si Arbre différent de nul  alors 
    ajouter dans Fifo Arbre.racine ; 
    TantQue Fifo n'est pas vide faire 
       Mon_traitement(premier de Fifo); 
       ajouter dans Fifo filsG de premier de Fifo ; 
       ajouter dans Fifo filsD de premier de Fifo ; 
       efface dans Fifo premier de Fifo ; 
    finTantQue
  Finsi 
FinFaire

voici globalement les 4 façon de parcourir un arbre
apres il existe un cas particulier qui est l'arbre binaire mais ceci est un autre débat

[roberto44]

Bon je ne suis pas plus avancé.
Je ne sais toujours pas quel algorithme de recherche utilisent les sites cités

[dourouc05]

Si tu veux une réponse ferme et définitive à ce sujet, ton seul choix est de leur demander ce qu'ils font…

Sinon, une autre manière d'explorer un arbre de décision est le MCTS (https://en.wikipedia.org/wiki/Monte_Carlo_tree_search), ça semble s'appliquer à ce cas pour ce que j'ai lu la discussion (trouver rapidement une très bonne solution dans un arbre de décision extrêmement grand).