Bonjour,et bonnes fêtes à tous !

Voila , j´ai eu une sorte de casse-tete appelé "l´ane rouge"
( on peut y jouer ici sur internet :
http://ccp14.minerals.csiro.au/ccp/web-mirrors/j-j-rousseau/enseignements/physique/02/divers/anerouge.html )

Apres plusieurs heures à tenter de trouver la solution à la main, j´abdique ^^ et je programme en scheme de façon à trouver la solution ...

( le programme en scheme :
http://rafb.net/p/tBQHtd81.html )

Le problème , c´est qu´ayant lancé le programme hier soir vers 2h , espérant avoir la solution au réveil , je me rends compte qu´à 13h ( oui bon... ) le programme tournais encore jlai arreté ...

pourtant , le programme trouve rapidement la solution quand le jeu est proche d´etre résolu ( une minute quand il reste 5 coups à jouer ) .

Jme demandais si c´etait la faute à scheme , qui est vraiment trop lent , ou si il y avait moyen d´améliorer mon programme pour le rendre plus rapide ?
( si c´est la faute à scheme , tant pis , c´est au programme des partiels alors je le garde quand meme )
enfin si par hasard quelqu´un avait le meme en c++ pour voir...

merci

Oh ben tiens ! Je le reconnais celui la !

Sur Nintendo DS (surement que ton prof tient son idée de la), il y a un jeu qui s´appelle "42 jeux indemodables", avec, dedans, un jeu appelé "fuite" qui ressemble beaucoup a "l´ane rouge"

--> Le but étant d´amener le carré a la sortie (en bas a droite)
J´ai fait un programme qui fait ça
Je te laisse regarder :
https://www.jeuxvideo.com/forums/1-11819-3493-1-0-26-0-0.htm

Pour info, j´ai un algo pseudo récursif (ramené a des itérations) avec une exploration en largeur, et une map (arbre binaire de recherche) qui stocke tous les coups déja joués de façon a ne pas retomber 2 fois sur le meme cas...

jejej : je ne connais pas la vitesse d´exécution de scheme (c´est compilé ?) , mais ce qui est possible c´est qu´il y ait une erreur dans ton algo, typiquement, un mouvement que tu ne prévoit pas de faire, et qui n´est jamais testé, ou alors une boucle infini (entre deux position identique). Chose qui peuvent ne pas arriver si tu es suffisamment proche de la solution

Déjà merci à vous deux pour vos réponses

En fait c´est pas une idée du prof , mais j´ai eu l´idée de programmer ça parceque c´etait exactement ( enfin presque ) le programme de notre cours d´info...
je suis parti d´un TP où l´on devait déplacer des cavaliers sur un échiquier pour arriver à une certaine configuration ; et je l´ai modifié .

Sinon , je ne pense pas que le Scheme soit un langage compilé , on éxécute nos programmes dans un environnement ( DrScheme ), y a pas de .exe ni rien .

On a pas parlé d´exploration en largueur en cours ...
En fait le principe de mon programme est :

Partir d´un état de départ : l´ensemble des positions des pieces .
Et explorer la liste des etats suivants possible
( à partir de l´etat de départ , on peut ainsi réaliser 6 mouvements différents ) , en tenant à jour une liste des etats déjà visités , pour éviter le phénomène de ´boucle´, et ainsi de suite...

En scheme toutes les fonctions sont récursives ( on n´a pas utilisé une seule fois ´for´ ou ´while´ de l´année )

Enfin bon , j´ai relancé le programme tout à l´heure , je vais le laisser tourner encore deux jours si il le faut , sinon j´abandonnerais :p

@ JYY : sympatoche ton programme ! juste un ptit bémol pour la grille qui est pas assez visible je trouve . Enfin il a l´air de marcher ^^ jvais le tester cette nuit en entrant la configuration du jeu de l´ane, on verra bien

Tiens, un problème de planification... Comme algo, je te conseille de passer par un "iterative deepening", l´ensemble d´états à mémoriser est trop grand pour un parcours en largeur normal.

bon, je n´ai pas lu le code. mais ton algorithme a l´air exponentiel. Alors cela ne m´etonne pas tant que ca. Peux tu estimer le temps de calcul de ton programme ?

Ben euh je sais pas trop quoi dire...
Mon but était d´appliquer mon cours d´info en premier lieu , pour réviser mes partiels , et c´est le seul algo qu´on ait vu .
On a pas ( encore ? ) parlé d´autres méthodes d´exploration de graphes , ni du temps de calcul des algorithmes ( si c´est ce que tu entends godrik , ln , constant , exp tout ça ? ) ... ça viendra ptete.

Enfin bon je montrerai ptete le programme à mon prof d´info , ou alors je laisserai couler pour le moment ^^ en tt cas merci tt le monde pour vos réponses

Le probleme avec cet algo, c´est qu´il n´est pas glouton, comme d´autres casses tetes.

En effet, quand tu as bougé une piece, tu peux, en continuant a bouger, retomber sur la meme configuration.
Si tu ne detectes pas cela, alors tu risques boucler a l´infini.

C´est pour cela que dans mon algo, je garde en mémoire (sous forme d´arbre binaire de recherche), toutes les configurations que je connais, ainsi, je suis sur de ne pas faire plusieurs fois la meme chose.
Cela dit, c´est tres couteux en mémoire, et en calcul aussi.

Pour mon parcours en largeur, je tiens une file pour gérer ça, c´est vrai que ça aussi, ça consomme pas mal de mémoire, cependant, avec cet algo, je suis sur que quand je trouverai une solution, c´est celle utilisant le moins de coups.

Mais je suis d´accord avec hitman_alias_47 sur le point que cela consomme un max de mémoire.
J´ai d´ailleurs réussi, sur des puzzle assez compliqués, a faire swapper ma machine de travail, qui a 2.5 Go de RAM...
Il faudrait que j´optimise, voir que je fasse des heuristiques.

Je tiens a dire que ce casse tete n´est pas simple, car il n´est pas glouton, contrairement a d´autres :
chiffre et lettres (chiffres), sudoku, solitaire avec les pions
--> Ces algos la sont gloutons car, dans une configuration donnée, pour avancer, tu es obligé de simplifier le probleme (enlever un pion pour le solitaire, faire une opération donc réduire la liste des opérandes dans les chiffers et lettres, réduire de 1 le nombre de cases vides du Sudoku) , ainsi, tu ne reboucles jamais.

Cela n´est pas vrai pour l´ane rouge (ni dans le taquin, les échecs...)

Mais avec un iterative deepenning, tu aurais la puissance d´une recherche en largeur et la faible consommation d´une recherche en profondeur (Cet algo explore une largeur à une profondeur de plus en plus grande). Regarde la description de l´algo sur google, tu verras que c´est exactement ce dont tu as besoin

hitman, il retrouvera probablement le meme problème, mais il sera moins visible puisqu´il ne tombera pas dans une boucle infini. En outre l´algorithme reste exponentiel; Cela ne m´étonne pas qu´il passe de 5 minutes a plusieurs heures. C´est exactement ce m´est arrivé quand j´ai lister les permutation d´un ensemble en faisant passer sa taille de 12 a 13 ( de mémoire).

Mais peut etre que tu peux facilement ecrire "des coupes". C´est a dire reperer des configurations pour lesquels tu es sur qu´elle ne sont pas bonne. Notes que je ne connais pas le problème de base. Ce que je dis restes théorique.

Je jetterai un oeil sur l´algo du iterative deepening ça m´a l´air intéressant !

Ils ont tous la même complexité exponentielle en temps, par contre, c´est en mémoire qu´on voit une énorme différence avec de l´exponentiel pour un parcours en largeur et du polynomial pour ID. En gros, on conserve la bonne propriété en espace du parcours en profondeur sans tomber dans ses pièges ni en bouffant l´espace brutal d´un parcours en largeur. Et on trouvera toujours la solution en temps fini si elle existe.

En fait iterative deepening consiste a faire une recherche en profondeur limité a la profondeur i. Et on fait varier i de 0 a l´infini.
Sur un arbre équilibré, cela ne fait que doubler le nombre de noeud parcouru et fait gagner de la mémoire par rapport a un ´vrai´ parcours en largeur. Quand on voit le temps que ca peut couter de payer un défaut de cache ca peut etre intéréssant.
Par contre si les structures ne sont pas équilibré ca peut couter tres tres cher. A utiliser avec précaution donc!