Propagation: Trouver le plus court chemin dans une matrice

Bonjour à toutes et tous,

Voici le nouveau Propagation réécrit de A à Z. Il s’agit d’un Pathfinder opérant sur une grille (la WorkSheet) de points pondérés (les cellules de cette WorkSheet). Un Pathfinder est un outil répondant au problème mathématique du plus court-chemin.

Cette nouvelle version est devenue bien plus performante et facile à réutiliser. (Je sais ce n’était pas difficile la version précédente accumulant toutes les erreurs). Pour vous donner une idée la matrice présentée dans la page d’aide (une 200x200 périphérique) était solvée en 8 minutes, avec cette nouvelle version le résultat est obtenu en à peine plus d’une seconde en arrivée flottante (donc environ 480 fois plus rapide).

Je vous invite donc à l'essayer.

Merci

Bonsoir,

j'ai testé et je dois dire que cela fonctionne bien.

J'ai sur ma machine un code similaire fourni par h2so4, je vous l'ai fourni pour vous amuser à faire quelque tests de rapidité de l'un par rapport à l'autre. Attention ! C'est juste pour voir, mais si j'ai bien compris le votre il y a des accès "feuilles Excel" pour mettre en mémoire des données de parcours, donc cela devrait le ralentir quelque peu, non ?

Une fois de plus bienvenu dans le "petit" monde des contributeurs !

@ bientôt

LouReeD

Bonjour LouReeD et merci beaucoup pour tes retours. Je commence seulement à chercher à comprendre (j'étais trop absorbé par la finalisation de la version 2 de Propagation) le code de Hero Quest que tu m'as envoyé en MP et vu mon petit niveau en VBA cela risque de me prendre un peu de temps. Ton jeu me semble très prometteur je suis impatient de l'essayer, bravo pour le soin apporté à la présentation ! Et merci de ne m'avoir envoyé que le code qui m'intéresse le plus. Une fois que j'aurai assimilé le code de h2so4 je mènerai un banc d'essai Chrono sur des plateaux de grandes dimensions.

Effectivement le fait d'utiliser des feuilles Excel pour stocker des données n'est peut-être pas le plus judicieux en termes de temps de calcul. Si le code de h2so4 est significativement plus rapide j'essaierai de trouver un autre procédé plutôt que d'utiliser ces feuilles.

A bientôt pour un compte-rendu du comparatif

Bonsoir,

aviez vous vu ce sujet ?

@ bientôt

LouReeD

Merci beaucoup pour ce nouveau Post. Non je ne connaissais pas ce sujet très riche. Je commence à peine à me familiariser avec le code que tu m'as envoyé et avec ce nouveau sujet je sens que je n'ai pas fini de m'amuser… Merci aussi de m'avoir sensibilisé au problème du temps des accès feuille je pense qu'il ne devrait pas être trop difficile de procéder autrement; à voir les résultats en termes de temps de calcul.

Donc très reconnaissant à vous monsieur LouReeD

Bonsoir,

Alors ces temps de calculs, c'en est où ?

@ bientôt

LouReeD

Bonsoir,

Ca avance modestement disons que la matrice que j'avais prise pour exemple et qui était solvée en 8 minutes tout rond l'est maintenant en 24,31 secondes !

Tu sais que tu m'auras donné beaucoup de boulot avec ton foutu lien sur le Post précédent ! Cela aura pour avantage que je pourrai fournir une page d'aide plus documentée mais j'ambitionne maintenant de programmer un estimateur de durée réaliste basée sur ce qu'on peut trouver en haut de cet article WikiPédia

Propagation v2.1 te devras beaucoup

Bonjour ,

Ce Post est en lien avec un autre déposé sur maths-forum.com. Il est destiné principalement aux matheux venant de ce forum. Il contient les fichiers qu'il est impossible de déposer dans les Posts de maths-forum.

En plus de ces fichiers je vais tenter d'expliquer un peu mieux le principe de Propagation:

La matrice Excel est convertie en Cubes. Une périphérie isolante (Cubes.Matrix = -1) s'ajoute aux Cubes de la matrice. Ainsi pour une matrice NbX x Nby x NbZ cellules il y a (NbX+2) x (NbY+2) x (NbZ+2) Cubes

Les Cubes sont des Arrays à trois dimensions : Cube(X, Y, Z) et ont trois propriétés définies par un type personnalisé :

  • .Matrix correspond aux valeurs de résistance telles qu'on les retrouve dans la feuille : "Matrice"
  • .Cumulation est la somme résistive du Cube par rapport au point de départ. Une fois que celui-ci a été calculé une première fois on ne revient plus dessus. C'est ce qui permet à l'algorithme d'avancer.
  • .Path stocke les adresses du chemin et ne sert à rien d'autre qu'à permettre à Excel de tracer le chemin en vert, c'est pour cela que je ne l'ai même pas présenté dans le logigramme

L'Array : "UnderStudy" comporte tous les Cubes en cours d'étude. Le premier élément confié à UnderStudy est le point de départ et il est solutionné niveau Cumulation. Viendront s'y ajouter ensuite et en premier lieu les Cubes immédiatement adjacents ou périphériques à ce point. Ces derniers sont dès lors solutionnés niveau Cumulation.

Une fois tous les Cubes autour du point de départ calculés celui-ci est exclu de UnderStudy. Le Cube appartenant à UnderStudy et de résistance minimale au niveau Cumulation devient alors le centre du même calcul que pour le point de départ.

Le calcul prend fin lorsque le Cube d'arrivée a été atteint. S'il ne l'est pas c'est qu'il ne peut pas l'être et le calcul prend fin une fois tous les Cubes de la matrice calculables calculés, le résultat est alors : "Sans solution"

Merci à tous ceux qui auront pris la peine de lire ce Post et un remerciement beaucoup plus appuyé à celui qui saura ou m'aidera à trouver l'équation juste pour l'estimateur de durées. Il figurera avec LouReeD de ce forum dans les remerciements de cette app !

Rechercher des sujets similaires à "propagation trouver court chemin matrice"