Javascript:Insert_Emoticon('/imgs2/smile_wink.gif'); Un algo simple… Méthode Barby dit d’inondation Tu remplaces 1, 2 et 3 respectivement par X, 1 et B. On démarre donc à 1 et on va vers B, ensuite… Tant qu’on a fait une affectation… Tu parcours ta matrice, pour chaque élément (i, j)… Pour chacun de ces voisins (o, p) soit pour (o, p) les valeurs (i-1, j-1) - > (i + 1, j + 1) si tu autorises les diagonales si nom c’est plutôt (i-1, J), (i + 1, j), (i, j-1) et (i, j + 1)… Si l’un deux a la valeur X ou B tu passes au suivant Si les deux on la valeur 0 tu passes au suivant Soit dist la distance entre les points, 1 ou 1.414 (pour les diagonales), mais on peut avoir n’importe quelle pondération en fonction du terrain par exemple. Tu regardes si (i, j) est supérieur > 0 et si (o, p) = 0 ou-bien (o, p) > (i, j) + dist ==> auquel cas (o, p) = (i, j) + dist. Sinon si (i, j) = 0 ==> (i, j) = (o, p) + dist. Voilà. Attention on ne s’arrête vraiment que quand un passage de toute la matrice ne génère pas une affectation… On peut arriver en B par un premier chemin calculer, mais en trouver un autre plus tard… C’est algo est plutôt fait pour un graphe ou la distance entre les nœuds est variable, ici c’est peut-être pas le cas. Les avantages de l’algo sont : Il est simple d’interrompre (n’importe ou) le calcul pour faire une autre tache, et reprendre au début de l’algo. C’est nécessaire pour une interaction rapide avec l’utilisateur. On peut avoir une solution provisoire, (qui n’est pas forcément la bonne), au fur et à mesure la solution va s’affiner. On a les solutions (si elles existent) pour n’importe quel point de destination de la matrice. Avantage si la destination (cible) se déplace… On peut limiter l'algo a une portion de la matrice. La (es) solution (s) ? On par de B on cherche dans ses voisins, celui qui a la plus petite valeur (différent de X évidement) et on remonte le chemin a rebrousse poil, en choisissant toujours le plus petit
Rien n'est tout noir ou tout blanc...Javascript:Insert_Emoticon('/imgs2/smile.gif');
|