par lyceen95 » 23 Jan 2021, 23:25
GBZM,
le problème n'est pas celui-ci.
Le problème auquel GBZM répond est celui-ci :
- En dimension 2, pour aller d'un point A à un point B, avec uniquement des pas vers la droite ou des pas vers le haut, on a plein de possibilités ( 30 pas vers la droite, puis 30 vers le haut, ou 17 vers la droite , 30 vers le haut puis 13 vers la droite ) etc etc
On peut donc calculer pour chaque sommet, la probabilité de passer par ce sommet. Par exemple, si on veut aller du point A(0,0) au point B(30,30), la moitié des chemins passent par (0,1) , et l'autre moitié par (1,0)
Et la taille des ronds rouges représentent ces pourcentages.
Le problème de Steph3112 est différent.
1. on est en dimension 3 et pas en dimension 2. Mais ça, disons que c'est un détail.
2. Chaque sommet rencontré a un 'coût' ; tous les sommets n'ont pas le même coût. Pour un chemin donné, le coût est la somme des coûts de tous les sommets utilisés. Il y a donc un chemin, et un seul qui a un coût minimum. L'objectif est de trouver ce chemin.
3. Imaginons qu'on est dans un cube 30x30x30, et que le point de départ soit le point A(2,2,2) et le point d'arrivée soit B(28,2_,28).
Et, pas de chance, les 3 points A1(3,2,2), A2(2,3,2) et A3(2,2,3) ont tous les 3 des coûts très élevés. Dans ce cas, le chemin avec le coût le moins élevé passera peut-être par le point (2,2,1) ; c'est à dire que le chemin va avoir plus de pas que le minimum basique.
On cherche le chemin qui a le coût minimum, quitte à ce que le nombre de pas soit supérieur au minimum 'normal'.
Ce n'est pas une question de maths, mais une question d'algorithme.
On peut recenser tous les chemins possibles, et garder le chemin qui a le coût le plus faible.
Mais, problème, recenser tous les chemins, c'est long en temps de calcul.
La question est donc de trouver le chemin le moins coûteux, en éliminant astucieusement les chemins qui vont forcément coûter trop cher.
Et la petite cerise sur le gateau, c'est qu'apparemment, Chris veut implémenter ça en VBA.
C'est vraiment un exe