Calcul durée algorithme problème du plus court chemin

Discutez d'informatique ici !
Steph3112
Messages: 4
Enregistré le: 10 Oct 2020, 22:12

Calcul durée algorithme problème du plus court chemin

par Steph3112 » 14 Oct 2020, 13:21

Bonjour de la part d'un nouveau sur votre forum,

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 :pleur4: )

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



Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6468
Enregistré le: 22 Nov 2007, 14:00

Re: Calcul durée algorithme problème du plus court chemin

par fatal_error » 15 Oct 2020, 13:54

slt,

tu devrais faire une instance mettons 10x10 ou tu bidouilles ta grille pour que ton algorithme doivent explorer toutes les possibilités pour trouver le meilleur chemin
tu fais la même en 20x20
et tu compares le temps mis
vu que nombre de cellules passes de 100 à 400, tu peux voir quel est le rapport en temps
est-ce que c'est *4 (linéaire O(n) (j'y crois pas trop :D)), *16 (quadratique(O(n^2)), peut-être c'est O(nlogn)
une fois que t'as hinté, compare ensuite avec mettons 40x40 pour voir si ta formule tient le coup

fais gaffe eventuellement au temps d'initilisation de ton runtime je sais pas comment excel se comporte
la vie est une fête :)

Steph3112
Messages: 4
Enregistré le: 10 Oct 2020, 22:12

Re: Calcul durée algorithme problème du plus court chemin

par Steph3112 » 15 Oct 2020, 15:23

Merci beaucoup pour ta réponse fatal_error.

Je ne suis pas sûr d'avoir encore bien tout compris mais voilà matière à réflexion. La forme linéaire est exclue, quadratique peut-être mais plus certainement O(nlogn).

Il me reste encore beaucoup de chemin à parcourir avant de trouver l'équation avec mes variables d'entrée qui renverrait un résultat qui concorderait aussi avec mon report : "Forme". Aussi le sujet reste ouvert.

Cordialement,

 

Retourner vers ϟ Informatique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 1 invité

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite