Bonjour,
> Apparement c'est pas 256x256 mais 256 pièces (seulement !). Donc 16x16.
>
Je crois que c'est bien 256x256. La doc dit 256 carrées, ce qui ne veut
pas dire grand chose. Si c'est 16x16, il pourrait y avoir des
embouteillages pour le 1er prix.

> Ca me dirait bien d'essayer, mais en python sur des vieilles brouettes
> on risque d'être un peu en retard ;-)
>

Ce que je me demandais, c'est s'il y avait moyen de se grouper pour 1:
réaliser le programme, et 2: mutualiser la puissance de calcul.

On 30-07-2007, jean-michel bain-cornu wrote:
> Bonjour,
>> Apparement c'est pas 256x256 mais 256 pièces (seulement !). Donc 16x16.
>>
> Je crois que c'est bien 256x256. La doc dit 256 carrées, ce qui ne veut
> pas dire grand chose. Si c'est 16x16, il pourrait y avoir des
> embouteillages pour le 1er prix.

256 carrés ça fait bien 16x16, mais ça fait quand même un nombre de
combis astronomique... 4x256! bon un peu moins sûrement mais quand
même...


>
>> Ca me dirait bien d'essayer, mais en python sur des vieilles brouettes
>> on risque d'être un peu en retard ;-)
>>
>
> Ce que je me demandais, c'est s'il y avait moyen de se grouper pour 1:
> réaliser le programme, et 2: mutualiser la puissance de calcul.

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 ?


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

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é ».

--
http://scipy.org/FredericPetit

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

William Dode <wilk@flibuste.net> a écrit :

> 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...

[snip]

> Tien je vais aller en parler sur sci.math pour voir ce qu'ils prédisent
> sur ce petit problème d'entrainement.
J'aurais bien fait un fu2 de ton paragraphe plus haut qui dit qu'« ils »
sont pessimistes... :-))))

--
http://scipy.org/FredericPetit