+- N-PN White-Hat Project (https://dev.n-pn.fr/forum)
+-- Forum : Programmation (https://dev.n-pn.fr/forum/forumdisplay.php?fid=72)
+--- Forum : Langages compilés (https://dev.n-pn.fr/forum/forumdisplay.php?fid=25)
+--- Sujet : [Algorithmie] Descends les escaliers mais ne remonte jamais. (/showthread.php?tid=3583)
[Algorithmie] Descends les escaliers mais ne remonte jamais. - Kiwazaru - 25-02-2014
RE: [Algorithmie] Descends les escaliers mais ne remonte jamais. - b0fh - 25-02-2014
Chouettos !
Cela dit, on peut faire mieux: voici comment.
Cet algorithme marche sur tous les chemins possibles, puis incrémente un compteur a la fin de chaque chemin. Tu fais donc un nombre d'appels de fonction proportionnel au nombre de chemins multiplié par la longueur du chemin (qui est la même partout.) Pour une grille de taille NxN, il y a de l'ordre de C(2n,n) chemins, tu fais donc de l'ordre de N! appels de fonction.
Mais, une grande partie du travail est redondant. Quand tu explores le point (x,y), tu commences par marcher sur (x+1,y). Cette marche te conduit à marcher, d'abord sur tous les chemins partants de (x+2,y), ensuite ceux partant de (x+1,y+1). Ensuite, tu remontes, et tu explores (x,y+1), qui te conduit d'abord en (x+1,y+1), puis en (x,y+2). Mais, tu as déja exploré (x+1,y+1) dans la passe précédente ! Il suffirait de mémoizer le nombre intermédiaires de chemins, et il n'y aurait plus q'un appel de fonction par point, de l'ordre de N^2.
La différence n'est pas flagrante sur une aussi petite carte, mais elle deviendra vite colossale.
Aussi, je te propose l'algorithme suivant:
- Initialiser un tableau des comptes.
- Pour x de 0 à dernier_x, et pour y de 0 à dernier_y:
-- si x = 0 et y = 0: compte[x][y] = 1 et suivant
-- si (x,y) contient un mur: compte[x][y] = 0 et suivant
-- compte_horizontal = 0 si x == 0, cout[x-1][y] sinon;
-- compte_vertical = 0 si y == 0, cout[x][y-1] sinon;
-- compte[x][y] = compte_horizontal + compte_vertical;
- retourner compte[dernier_x][dernier_y]
Voici une implémentation vite faite en Haskell:
Code :
import Data.Array
import Data.Set
dimensions = ((1,1),(11,8))
murs = fromList [
(4,2), (8,2),
(2,4), (5,4),
(3,6), (7,6),
(4,8) ]
tableCouts = array dimensions [ ((x,y), cout (x-1) y + cout x (y-1)) | (x,y) <- range dimensions ]
cout 1 1 = 1
cout 0 _ = 0
cout _ 0 = 0
cout x y | (x,y) `member` murs = 0
| otherwise = tableCouts ! (x,y)et le résultat (il va falloir comprendre pourquoi ça diverge.. le problème est mal défini, mais je suppose que par "chemin" tu entends un chemin qui commence au coin supérieur gauche et finit au coin inférieur droit ?):
Code :
*Main> cout 11 8
3239EDIT: j'ai trouvé un bug dans ton code.
Lorsqu'en un point, le seul chemin possible est en bas, la dernière condition de ta boucle (celle qui fait y++) se déclenche; mais immédiatement après, le x++ de la boucle interne se déclenche, ce qui fait
que tu prends un pas en diagonale au lieu de suivre le chemin vers le bas.
Lorsque je change le y++ en y++;x--; (hack dégeulasse, nous en conviendront), j'obtiens le même résultat avec les deux algos.
RE: [Algorithmie] Descends les escaliers mais ne remonte jamais. - Kiwazaru - 25-02-2014
J'me disais bien qu'il y avait un problème avec le y++, thanks
