Discussion :

[miam]

Bonjour, voilà quelques jours que je me torture l'esprit à trouver une façon de résoudre un problème de façon récursive

Voici l'énoncé :

Vous avez une reine que vous devez placer sur un échiquier nxn depuis le coin inférieur gauche, de coordonnées (1,1) jusqu'au coin supérieur droit (n,n).
Vous pouvez la déplacer à droite, vers le haut ou en diagonale vers la droite, d'UNE SEULE CASE A LA FOIS.
Vous ne pouvez pas descendre ni aller à gauche.
On demande de donner le nombre de trajets possibles.

problème bis :
Vous pouvez la déplacer à droite, vers le haut d'UNE SEULE CASE A LA FOIS ou en diagonale vers la droite d'autant de cases que l'on veut...

Merci d'avance

[Smoke666]

Hum un probleme d'IA que j'ai eut cette année, de tête je ne me souviens plus de la solution mais si mes souvenirs sont exacte tu dois faire un algo de parcours de chemin ou d'optimisation, la j'avoue je me rappel plus la solution mais promis j'essayerais de te la retrouver ce soir.

ca doit etre un truc du style:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
tant que chemin
si chemin courant < chemin alors
chemin = chemin + chemin courant
fin si
fin tant que

[miam]

merci

[Kangourou]

Salut,

je sais pas, mais en faisant une fonction nombreDeTrajets(x, y), qui va retourner le nombre de trajet possibles pour aller a la case (8,8 ) en partant d'une case en (x,y), ca devrait etre possible.

Les cas a traiter :
- cas general :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

nombreDeTrajets(x,y) = nombreDeTrajets(x+1,y) + nombreDeTrajets(x, y+1) + nombreDeTrajets(x,y+1)

- sur une case du bord droit ou du bord haut (ou meme du coin) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

nombreDeTrajets(,y) = 1,

Donc, en pseudo-code, ca doit donner un truc du genre :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
fonction n = nombreDeTrajets(x, y)
// teste le cas des bords :
si x==N ou y==N
   retourne 1;
fin si
 
nx = nombreDeTrajets(x+1,y);
ny = nomrbeDeTrajtes(x, y+1);
nxy = nombreDeTrajets(x+1,y+1);
 
retourne nx + ny + nxy;

Ca parait pas mal en fait ...

essaie !

A+

[Nemerle]

Euh..... c'est vachement simple à calculer de façon exacte... pourquoi chercher à programmer cela??

[miam]

essaie !

Je suis parti de ton idée mais à l'envers...
Voici l'implémentation :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
nbrtrajets (ln, cl) {
  if (ln < 1)
    return(0);
  if (cl < 1)
    return(0);
  if (ln == 1 && cl == 1)
    return(1);
  return nbrtrajets (ln, cl-1) + nbrtrajets (ln-1, cl) + nbrtrajets (ln-1, cl-1);
}

Donc pour connaître le nombre de chemins possible pour une grille de 8x8, il suffit de lancer

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

nbrtrajets (8,8)

J'ai validé mon code en comparant les résultats générés au superbe site des séquences d'entiers (poussez sur recharger s'il génère une erreur)

Euh..... c'est vachement simple à calculer de façon exacte... pourquoi chercher à programmer cela??

1. Ben j'avoue ne pas voir comment faire de façon "simple"
2. La récursivité donne souvent de bons résultats et évite les erreurs de logique (aie je crois que je viens de lancer un débat)

Miam

[duj]

La récursivité donne souvent de bons résultats et évite les erreurs de logique (aie je crois que je viens de lancer un débat)

C'est vrai, mais l'idéal, quand c'est possible, c'est de dérecursifier par la suite ton algo récursif.

En effet, du pur point de vue efficacité, rien de tel qu'un boucle.

Ceci dit, il y a certainement des gens qui raisonnent plus facilement avec une boucle.

[miam]

La récursivité donne souvent de bons résultats et évite les erreurs de logique (aie je crois que je viens de lancer un débat)

C'est vrai, mais l'idéal, quand c'est possible, c'est de dérecursifier par la suite ton algo récursif.

En effet, du pur point de vue efficacité, rien de tel qu'un boucle.

Ceci dit, il y a certainement des gens qui raisonnent plus facilement avec une boucle.

Sauf erreur de ma part, la plupart des compilateurs actuels se chargent assez bien de cette dérécursification non ?

[Nemerle]

Euh..... c'est vachement simple à calculer de façon exacte... pourquoi chercher à programmer cela??

1. Ben j'avoue ne pas voir comment faire de façon "simple"
2. La récursivité donne souvent de bons résultats et évite les erreurs de logique (aie je crois que je viens de lancer un débat)

Miam

Bein, note h pour aller en haut, d pour la diagonale et r pour aller à droite.
Un type de chemin (i.e. à permutation près) est de la forme h(x)d(y)r(z) où h(x) indique qu'il y a x pas en h,etc...

Conditions: x+y=n=y+z et x,y,z>0.

Soit x=z=n-y, où y parcourt 0,1,...,n

A un triplet donné (x,y,z), il y a N(y)=C(x,2n-y)C(x,n) chemins possibles, et donc le nombre de chemins différents est Somme(y=0 à n) N(y).

Bon, en gros et rapidement…

[ceugniet]

Salut Miam,

Je me suis posé la question de savoir pourquoi tu tenais absolument à trouver une solution récursive de ton problème. En fait, la récursivité est super pratique pour coder vite, et sans erreur (encore que... certaines récursivités ne sont pas si facile à débugger). C'est aussi très élégant de coder comme cela ; on a des codes extrêmement concis, donc facile à comprendre. Enfin, c'est aussi très amusant : de se débarrasser d'un problème ardu en trois lignes de code donne effectivement beaucoup de plaisir... Tout cela est vrai, mais, comme tu le dis très justement un peu plus tard, "du pur point de vue de l'efficacité, rien de tel qu'une boucle".

J'ai eu la curiosité d'essayer ton code (en C++), qui marche d'ailleurs très bien. Mais j'ai mesuré le temps de calcul avec cette fonction de l'API Windows "QueryPerformanceCounter" qui donne une clock assez précise.

Ce qui se passe en fait, c'est qu'on appelle un grand nombre de fois nbrtrajets, bien plus que le nombre de chemins à trouver.
nbrtrajets(8,8)=48639, mais pour arriver à ce résultat, tu as appelé 252676 fois la fonction. Le tout a pris 0,005 secondes (sur mon PC, 2GHz). Bon ! On peut attendre ce temps-là sans problème. Mais pour le plaisir, et aussi pour le principe, j'ai fait une autre fonction où je stocke tous mes résultats intermédiaires dans un tableau carré 8*8. Si j'ai le résultat, je le prends, si je ne l'ai pas, alors je le calcule (en appelant récursivement la fonction comme toi) et je le stocke pour une utilisation ultérieure. La fonction est toujours récursive, mais elle est économe : elle est appelée 63 fois (8*8-1) et le calcul prend alors seulement 0,000006 seconde, soit environ 800 fois moins de temps.

Ce n'est peut-être pas très probant, mais imagine maintenant que l'on ait à calculer nbrtrajets(14,14). Le résultat est 1 409 933 619 au prix de 7 655 971 522 appels de la fonction et ça me demande cette fois 131 secondes avec ta fonction contre 0,000013 secondes avec la mienne : cette fois le rapport de performance n'est plus 800, mais près de 10 000 000 ! La valeur de nbrtrajets augmente extrêmement vite. Et malheureusement, la programmation récursive pure provoque largement plus d'appels que le nombre à chercher. Pour un "échiquier 30*30" le calcul direct donne 3 818 162 478 591 427 187, que ma fonction demande 55 microsecondes, soit 0,000055 secondes à calculer, je te laisse deviner combien de temps prendrait ta fonction...

Le vainqueur toutes catégories est évidemment le calcul direct : le raisonnement de Nemerle est parfait, sa formule est légèrement erronée (il faut calculer N(y)=C(x,2n-y)*C(y,n)) et on trouve le résultat en 0,000005 secondes.

Bien sûr pour ton problème, un échiquier, qui a bien sûr 64 cases, quelques millisecondes ou quelques microsecondes, ça ne fait pas grande différence. Mais il faut se rappeler que la récursivité à tous crins est parfois dangereuse sur le plan de l'efficacité (d'ailleurs, elle peut aussi faire exploser la mémoire vive). De toutes façons, comme Smoke666 le soulignait, il semble que ce soit un "problème d'IA" classique. On peut bien imaginer une application qui ait besoin de calculer ce fameux nombre de chemins, mais, au moins a priori, ça ressemble fort à un exercice qui n'a d'autre but que d'enseigner les problèmes récursifs. Dans ce cas, il aurait mieux valu que l'on te demande le même problème avec un "échiquier" 30*30. Là tu aurais été obligé de trouver une astuce pour accélérer ton code...C'est ce qui pourrait bien se passer pour d'autres problèmes récursifs.

@+