On 30-07-2007, fred wrote:
> William Dode <wilk@flibuste.net> a écrit :
>
>> Moi au niveau puissance de calcul je suis un peu maigre...
>> Un programme qui testerai toutes les combinaisons c'est assez facile
>> à faire mais il faudrait trouver un moyen de l'optimiser, qu'il soit un
>> brin plus intelligent. Des idées ?
>>
> Aller faire un tour sur fr.sci.maths avec comme mot-clé le même que ce
> fil ;-) pour la faisabilité de la chose.
>
> En gros, c'est _très_ loin d'être gagné, même « optimisé ».
>

C'est le but apparement ;-)

Par contre leurs calculs de probas sont très pessimistes malgrès tout
car ils se basent sur le principe du loto où toutes les combinaisons
sont possibles. La ce n'est pas le cas.
Par exemple quand on va tester un agencement de 10 pièces, il se peut
qu'on ne puisse plus rajouter une seule pièce, ce qui fait qu'on gagne
instantanément 4*6! possibilités. De plus il y a peu de probabilité pour
que la dernière combinaison soit la bonne.
Sans compter qu'il y a plusieurs bonnes solutions...

Je viens de faire l'expérience avec le problème des déplacements
à cheval (aux échecs). Je rapelle le principe. Sur une grille on place
le premier cheval où l'on veut, le deuxième par rapport à un déplacement
2/1 il ne faut pas qu'il y ait déjà un cheval à cet endroit, et ainsi de
suite.

Une solution sur 5x5 :

01 10 19 14 03
18 05 02 09 20
11 22 13 04 15
06 17 24 21 08
23 12 07 16 25

Si on compte le nombre de combis totales ça donnerait 25! soit
15511210043330985984000000
On peut compter d'une manière bcp plus optimiste sur les déplacements
possibles ça donnerait 25*8^24 ça ne fait plus que(!)
118059162071741130342400

En fait on trouve la solution en brute force après 26369 essais !

Le prog en python fait 40 lignes, il met 0.5 secondes, pas du tout
optimisé... Avec psyco il met 0.04 secondes.

Tien je vais aller en parler sur sci.math pour voir ce qu'ils prédisent
sur ce petit problème d'entrainement.

Ca n'empêche sûrement pas que pour ethernity le nombre de combis
à tester restera encore trop grand...

--
William Dodé - http://flibuste.net
Développeur informatique indépendant