pb memoire dans un programme recursivite - Page 1

Bonjour,
pour apprendre a maitriser la récursivité je me suis posé ce problème : recherche du plus long déplacement d'un cavalier sur un échiquier vide qui ne devra jamais repasser par une case précédemment occupée.
Le programme initialise un tableau 'gd' de 8 lignes et 8 colonnes (les 64 cases de l'echiquier) une liste 'lst' contenant un seul element {1.01} et une variable 'm'.

au depart
gd[1,1]=1 => la case du premier déplacement
lst = {1.01} => coordonnee premier mouvement
m=1 => mouvement en cour ici on est sur le premier

Le programme dessinne une grille representant l'echiquier et deplace le cavalier sur une case jamais été selectionné
lorsqu'il est bloqué il revient en arrière.

les trois variables sont globales et le programme fonctionne correctement jusqu'a un certain point : il atteint 51 deplacements du cavalier en ayant fait trois retour suite a une impossibilité de poursuivre d'autres deplacement.

Mais il me fait un blocage =>>> 'memory' voici ce que m'informe la calculatrice en stoppant l'execution du programme
j'ai essayé plusieurs modifications mais sans succes.

Je suis loin d’être a saturation niveau mémoire j'ai un doute sur l'utilisation mémoire lors de la recursivité.
j'ai la possibilité de lancé le sous-programme récursif qui me permet d'avancer a chaque nouvel exécution mais ca me penalise sur la fluidite de son execution complet !!
Merci de me renseigner si vous penser avoir une solution permettant une execution complete en une seule fois.

Pour l'instant le record de case atteint est 58 !!

Il s'agit probablement d'une protection pour éviter un "stack overflow", ce n'est pas la ram entière mais juste la pile qui fait ce blocage CPU...

Ensuite, pour ton approche, si tu veux vraiment tester comme ça (en "brute force"), renseignes toi plutôt sur l'algorithme de la fourmi...

(cross)

a mon avis c'est le nb d'appels récursifs qui bloque

puisque tu as une liste de coordonnées, tu dois pouvoir carrément éviter les appels récursifs en travaillant dans une unique routine.

En quel langage de programmation travailles-tu? Parce que certains ont des limites codées en dur pour le niveau de récurrence.

Ok, merci
Je vais supprimer l'appel récursif mais c’était a la base un petit défi perso pour tester cette fonctionnalité !!

bah ça marche apparemment, mais trop

supprimer la récursivité est l'optimisation suivante

Sauf erreur, ce problème revient à la recherche d'un plus long chemin dans un graphe dont les arcs ont tous un poids identique et les sommets ont un degré compris entre 2 et 8. On peut borner le nombre de possibilités par 8^64 mais, à cause de la contrainte "on ne peut passer qu'une seule fois par un sommet", les possibilités sont moins nombreuses, d'autant qu'on peut éviter d'explorer les séquences symétriques. Je veux dire qu'une recherche exhaustive est peut-être possible (implicitement grâce à un élagage), mais j'y crois pas trop. En tout cas, une profondeur de récursivité de 64 est suffisante, dommage que ton ordinateur bloque un peu avant.

Je trouve que ce problème est original et bien choisi pour s’entraîner à la récursivité. Après, il serait intéressant de réfléchir à des méthodes plus efficaces (et plus complexes). Le fait que cette instance du problème du plus long chemin soit homogène (poids tous égaux) et fortement symétrique me laisse penser que l'algorithme des colonies de fourmis (cf. vince) peinerait à donner de bonnes solutions. Peut-être existe-t-il un algorithme exact polynomial pour ce problème ?

Tu n'as pas répondu à ma question: En quel langage de programmation et sur quelle plateforme (machine, système d'exploitation) fais-tu ça?