combinatoire tres difficile

Version imprimable

Voir 40 message(s) de cette discussion en une page

08/08/2008, 08h09
Zavonen

Citation:

Envoyé par zhao

oui mais je sais que j'ai quand meme 25% de chance d'avoir un coeur et plus je fais de tirage sans avoir de coeur et plus j'ai de chance que mon coeur apparaisse au prochain tirage :-) ( enfin je crois :-) )

Non, c'est inexact. Sauf s'il s'agit d'un tirage sans remise, si tu tires les cartes d'un même paquet en les conservant. Sinon, comme l'a fort bien résumé certain, "le hasard n'a pas de mémoire" et une succession d'échecs ni n'augmente ni ne décroit la probabilité d'un succès.
08/08/2008, 08h55
zhao

Bonjour Zavonen .
Bien entendu je parlais de tirage sans remise :-)

cordialement
08/08/2008, 10h29
pseudocode

J'avais prévenu que tu serais déçu. :P

Mon heuristique de recherche est vraiment très basique, et tous les probèmes viennent de là. Pour "9 6 5", il est meme très possible que mon heuristique empeche de trouver une bonne solution :aie:.

Plusieurs pistes de recherches:

- trouver une meilleure heuristique (methode "findCandidats()" )... bon courage pour en trouver une.

- ne pas mettre d'heuristique du tout et tester n'importe quelle grille... et ca peut prendre très longtemps.

- choisir une autre technique que "monté-carlo"... il faut se documenter sur les techniques d'optimisation.
08/08/2008, 10h53
zhao

Bonjour pseudocode :-)
Deçu ? non pas du tout mais je ne comprends pas pourquoi il trouve pour 10 et pas pour 12 ou 14 ( je crois que ton algo le fait que ce soit des chiffres pairs a une importance enfin bon je dit bien je crois ;-) )

comment modifier ton programme pour qu'il n'y est pas d'heuristique mais qu'il y est quand meme le MAXLENGTH cela te serais difficile a faire ? si cela met longtemps tant pis je veux voire le resultat sortir, les combinaisons je les aient mais cela ne m'interesse pas :)

Pour l'algo j'avais pensé a un truc ( mais comme je suis nul ;-) )
si au lieu de comparer des combinaisons on cherchaient deja dans un premier temps tous les groupe possible :
je m'explique par exemple on sait que pour 10 le minimum est de 14 .

il faudrais grace a ton MAXLENGTH generer tous les groupes possible de 14 et ensuite les comparer pour voire si un groupe reponds a notre demande ( peut etre meme comme tu le fais en prenant un groupe au hazard) si un groupe est OK on arrete la recherche comprends tu ce que je veux dire et cela est t'il difficile ? l'avantage c'est que ce genre de chose marcheras quelque soit les chiffres en mettant plus ou moins de temps mais apres on pourras toujours l'optimiser :-)

Citation:

Envoyé par zhao

comment modifier ton programme pour qu'il n'y est pas d'heuristique mais qu'il y est quand meme le MAXLENGTH cela te serais difficile a faire ? si cela met longtemps tant pis je veux voire le resultat sortir, les combinaisons je les aient mais cela ne m'interesse pas :)

il faut modifier la méthode computeSolutions(), mais ca va être très très peu probable de trouver la meilleure solution dans un temps raisonnable.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 public int[] computeSolutions() { // calcul de la liste de tous les tirages possibles int[] tirages = new Cnp(N,P).results; int tiragescount=tirages.length; // allocation de la liste des solutions int[] solutions = new int[tirages.length]; int solutionscount=0; // tant qu'il reste des tirages possibles while(tiragescount>0) { // on choisit une grille au hasard dans la liste des tirages restants int random = (int)(Math.random()*tirages.length); int grille = tirages[random]; if (grille==0) continue; // a été supprimée => on recommence // on ajoute la grille a la liste des solutions solutions[solutionscount++]=grille; // on supprime les tirages gagnants de la liste des tirages possibles tiragescount=removeMatching(grille, tirages); } // on retourne la liste des solutions return Arrays.copyOf(solutions, solutionscount); }
Citation:

Envoyé par zhao

il faudrais grace a ton MAXLENGTH generer tous les groupes possible de 14 et ensuite les comparer pour voire si un groupe reponds a notre demande ( peut etre meme comme tu le fais en prenant un groupe au hazard) si un groupe est OK on arrete la recherche comprends tu ce que je veux dire et cela est t'il difficile ?

Nombres de grilles possibles a 6 elements parmis 10: C(10,6)=210
Nombres de groupe de 14 grilles parmis 210: C(210,14) = +2*10^21

Mettons une milliseconde pour tester un groupe, ca nous fait une durée totale de : 2*10^21*0.001 = 2.10^18 secondes = 75.77 milliards d'années

C'est un peu long comme méthode. :P

08/08/2008, 14h53
zhao

ok pseudocode :-)
mais tu oublie un petit detail qui as son importance ,prenons l'exemple de ton programme pour 10 6 5 14 a chaque fois qu'il trouve 14 c'est jamais la meme cela signifie que meme pour 10 il y a probablement des millier voire plus de groupes de 14 valable donc on sera loin tres loin de tester toutes les possibilitées car quand un groupe est trouvé on stop d'ou aussi l'interet de prendre un groupe au hazard ,maintenant tu vas me dire que pour par exemple 20 6 5 X les chiffres sont enorme oui mais la ses par dizaines de millions que les groupes valable serons possible voila pourquoi je te parlais eventuellement de cette solution :-)
08/08/2008, 15h17
pseudocode

Citation:

Envoyé par zhao

cela signifie que meme pour 10 il y a probablement des millier voire plus de groupes de 14 valable donc on sera loin tres loin de tester toutes les possibilitées car quand un groupe est trouvé on sto

Ok. Mettons qu'il y a 1 million de solutions possibles... non, allez, 10 millions.

Comment être sur que ces 10 millions de solutions ne seront pas toutes les DERNIERES à etre testées ?

Ok. Imaginons qu'elles sont réparties equitablement et qu'on fasse des tirages aléatoires.

Probabilité de tomber sur une bonne solution: 10 millions / 2.10^21 = 0.0000000000005 % de chance

Hum... autant jouer au loto, y a plus de chance de gagner.
08/08/2008, 16h02
zhao

bon ok tu est dur pseudocode tu est en train de briser mes reves qu'un programme puisse enfin resoudre ce probleme quel monde cruel :-)

donc faut trouver autre chose si j'ai bien compris ? :-)
08/08/2008, 17h10
pseudocode

Citation:

Envoyé par zhao

bon ok tu est dur pseudocode tu est en train de briser mes reves qu'un programme puisse enfin resoudre ce probleme quel monde cruel :-)

donc faut trouver autre chose si j'ai bien compris ? :-)

Je ne sais pas. Je ne me suis jamais vraiment interessé aux problèmes des systèmes réducteurs. Il y a surement des techniques plus performantes que monté-carlo et des heuristiques plus puissantes que compter les numeros en communs. A toi de voir...
08/08/2008, 17h19
zhao

oui et bien c'est pas gagné c'etait ma raison sur ce forum :-)
en tout cas merci beaucoup de ta patience et pour toutes ses infos que tu m'as fourni je vais reflechir a une autre methode et si cela ne te derange pas je posterais ici mon idée pour voire si il y a moyen d'ameliorer ce que eventuellement je trouverais :-)
cordialement

ah oui pseudocode si cela ne te derange pas pourrais tu changer ton programme tout en gardant les parametre n p k et maxlength pour tester sans heuristique par curiosité je le ferais tourner pour voir si cela ne te derange pas ?
cordialement
08/08/2008, 17h28
pseudocode

Citation:

Envoyé par zhao

ah oui pseudocode si cela ne te derange pas pourrais tu changer ton programme tout en gardant les parametre n p k et maxlength pour tester sans heuristique par curiosité je le ferais tourner pour voir si cela ne te derange pas ?
cordialement

J'ai déja répondu au post #30. Il y a juste une méthode a modifier. ;)
08/08/2008, 18h16
zhao

ah ok j'ai pas fais attention que tu l'avais deja modifier escuse moi :-)
20/08/2008, 23h03
vaxaul

Hello,

Je "bosse", comme certains d'entre vous sur les systèmes réducteurs

J'ai en tête de trouver un programme qui optimise le nombre de tirage pour assurer le système de garantie voulue

Par exemple:
On prend 18 n°( de 1 à 18),
on veut une garantie de 3 bons si le tirage qui sort est composé de 6n°
Le résultats est 7. Il s'agit d'aller sur le site
On ne peut pas garantir 3 parmi 6 (avec 18n° de base) en mois de 7 tirages de 6 n°
J'arrive en programmation à arriver à ce résultats.

Là où ça se complique c'est lorsque le n° de base augmente (19,20,21...)
Les calculs deviennent beaucoup trop long. Le nombre de combinaisons mises en jeux devient incroyablement elevés
20/08/2008, 23h08
vaxaul

...............j'ai pas fini !!!!

Bref, où en êtes vous ?

Pour ma part, j'ai décomposé la garantie 3/6 en 18 en garantie de 3/4 en 12
Ca permet de travailler sur des tailles de tableaux limités à 924 lignes et colonnes alors qu'en concervant 18 n°, la taille passe à 18564 !!!

Voilà, dans l'attente de réponse...
A+

Vaxaul
13/06/2009, 11h40
Aguire_

Bonjour.

Post extremement interresant.

Une interpretation en langage basic standart serait un plus pour l'adaptation de ces codes.

je vous remercie pour toute infos complementaire.

+
19/08/2009, 23h08
vaxaul

Salut,

Aquire, toi aussi tu "bosses" sur les systemes réducteurs ?

Voir 40 message(s) de cette discussion en une page