Et je commence par une grande tartine…
Je suis à l'origine d'un Pathfinder sur Excel c’est-à-dire d'un algorithme capable de traiter du problème du plus court chemin et que j'ai nommé : "Propagation". Je suis fier d'être parvenu à solutionner tout seul ce casse-tête logique avec mon petit niveau d'études et en mathématiques mais il y a un point où je crains d'être dépassé et c'est là que je sollicite votre aide. Si mon sujet vous intéresse vous pourrez retrouver cette application sur le site https://excel-pratique.com et des fichiers complémentaires détaillés tout en bas de ce Post.
Sur des matrices de grandes dimensions le calcul peut vite prendre beaucoup de temps aussi j'ai ajouté un indicateur de durée estimée pour le moment totalement insatisfaisant. (d'autant plus qu'il n'est pas à jour et prétendait donner les valeurs que l'on retrouvait sur une version beaucoup plus lente de mon app)
Sans en être sûr je pense que mon algorithme a des points communs avec celui de Dijkstra https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra. Ainsi j'espère pouvoir utiliser une des deux formules donnant la durée de l'article Wikipédia pour mon indicateur de durée. Mon problème est de savoir si mathématiquement ça peut tenir la route de comparer cet algorithme au mien et si oui comment y extrapoler mon nombre de sommets et d'arcs en fonction des dimensions X,Y et Z de mes matrices et du mode de propagation.
Le mode de propagation peut être soit :
- "Adjacent" dans ce cas seuls les 4 carrés adjacents d'un carré central d'une matrice 2D peuvent entrer dans le chemin de propagation (6 cubes correspondant à chacune des faces du cube central pour les matrices 3D)
- "Périphérique" dans ce cas les 8 carrés périphériques d'un carré central d'une matrice 2D peuvent entrer dans le chemin de propagation (26 cubes autour du cube central pour les matrices 3D)
Sur mon classeur Excel "Chrono.xlsx" j'ai effectué cinq reports chacun sur une feuille distincte:
- Les quatre premiers sont des relevés temps sur des matrices carrées et cubiques allant de taille croissante (Feuille "2DA" pour 2D Adjacent, "2DP" pour 2D Périphérique, "3DA", "3DP")
- Sur le cinquième j'utilise une matrice 2D de 90 000 cellules, fais varier la forme (de carrée à très allongée) et ai pu constater une grande incidence de cette forme sur les temps de calcul (Feuille "Forme"). On y constate que le minima est obtenu pour une forme intermédiaire. L'examen des deux courbes correspondant aux deux modes de propagation est assez intéressant.
Propagation gère les matrices bidimensionnelles et tridimensionnelles de la même façon. Dans le logigramme fourni sur le site Excel-Pratique je parle de Cubes mais le même logigramme exactement s'applique au matrices 2D il suffit de lire Carré à la place de Cube et savoir qu'il n'y a plus que 4 cellules adjacentes pour le mode adjacent et 8 pour le périphérique.
Mon problème est donc de trouver une équation fondée mathématiquement qui me permettrait de prévoir la durée du calcul et qui coïnciderait de près avec ce que j'ai pu constater sur mes reports. Les variables d'entrées sont les dimensions X,Y et Z de ma matrice ainsi que le mode de propagation.
Trouverai-je un amateur pour résoudre ou m'aider à résoudre ce casse-tête un peu trop compliqué pour moi à ce jour ? Ce sujet risque de lui réclamer un certain temps… puisse-t-il lui procurer autant de plaisir que j'en ai eu à écrire cette app.
Un grand merci d'avance à celui, celle ou ceux qui voudront bien prendre le temps d'étudier ce sujet. Je suis bien entendu entièrement disponible pour tout complément d'information mais rappelez-vous que mon niveau en math est disons… limité ! (et tend malheureusement vers zéro
)Voici les fichiers que vous trouverez dans mon Post Excel-Pratique https://forum.excel-pratique.com/applications/propagation-trouver-le-plus-court-chemin-dans-une-matrice-146209#p907208
- "Propagation v2.1béta.xlsm", l'application au centre de ce sujet.
- "Chrono.xlsx", mes reports temps sur 4 échantillons sur des matrices randomisées vierges de cellules isolantes.
- "Aide de Propagation.pdf" la feuille d'aide imprimée de Propagation (Que je dois finaliser et sur laquelle je dois ajouter une rubrique : "Remerciements" où figurera en bonne place celui qui me trouvera ou me permettra de trouver l'équation objet de ce Post)
- "Logigramme Propagation.pdf"
Note : Propagation est et restera toujours un freeware open source
)), *16 (quadratique(O(n^2)), peut-être c'est O(nlogn)