Propagation: Trouver le plus court chemin dans une matrice

Bonjour le forum,

J’ai le plaisir de vous présenter le tout dernier Propagation, sa version 3, voici les principales nouveautés :

• Ajout d’un nouveau module de Pathfinding capable de traiter les grilles contenant des Doubles (en fait l’algorithme de la v2.1 amélioré d’où son nom de code 211).
• Ajout du mode de propagation : Périphérique Sprite qui m’a été inspiré par le A* d’Ausecour très didactique. Je tiens à le remercier ici de l’avoir mis en ligne. C’est sa formule retravaillée et codée en AND plutôt qu’en OR que j’ai réutilisée, vous reconnaitrez le Gosub Calcul, un petit clin d’œil.

• Code interruptible à tout moment avec la touche Echap et indicateur de progression dans la barre d’état.
• Random paramétrable depuis l’Userform.
• Relecture de la feuille uniquement si la grille a été modifiée.
• Performances améliorées.
• Ergonomie et finitions améliorées.
• Code VBA rationalisé et mieux commenté.

Merci pour votre attention, j'attends avec impatience vos retours...

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.

Propagation v2.1 te devras beaucoup

Post supprimé

Retour d'expérience : Optimiser Dijkstra en VBA (Gestion de grilles 3D et performances)

Bonjour à tous,

Après pas mal de travail et d'optimisations, je considère mon projet de Pathfinder comme achevé. En poussant l'outil jusqu'à gérer des grilles 3D de 1 000 au cube (soit 1 milliard de cellules !) sous Excel, je me suis heurté aux limites de performance du VBA.

Pour relever le défi, j'ai implémenté deux variantes distinctes de l'algorithme de Dijkstra. J'avais envie de partager ici les choix techniques et les astuces qui m'ont permis de faire tourner tout cela en arrière-plan sans exploser les temps de calcul.

2. L’algorithme 211 (Traitement par lots avec mCCm, NA et LPA)

Ma seconde approche est un Dijkstra plus conventionnel, adapté au type de données Double et optimisé par des astuces de bas niveau, idéal lorsque le nombre de valeurs de coûts distinctes est limité :

• Le traitement groupé : Plutôt que d'étudier point après point, j'intègre dans une variable mCCm (Même Coût Cumulé Minimal) tous les points partageant le même coût minimal en fin de boucle.
• Les sous-boucles de voisinage :
1. Je calcule le coût des voisins immédiats et les trie par ordre décroissant dans un tableau de taille limitée NA (Nouvellement Atteintes) via un tri de Shell.
2. Si aucun nouveau voisin n'est trouvé, je zappe complètement les étapes suivantes pour gagner du temps.
3. Sinon, j'injecte et fusionne ces points dans un tableau principal LPA (Liste des Points Atteints) maintenu en ordre décroissant.
• La fuite rapide (Exit For) : Je parcours LPA en partant de la fin et je m'arrête dès que les nouveaux voisins ne rivalisent plus avec les premiers éléments, m'évitant de balayer toute l'étendue du tableau.
• Les inconvénients de cet algorithme : Les temps de calcul sont rédhibitoires sur les très grosses grilles ( > 1000 x 1000) et incapable de solutionner efficacement les grilles en 3D

1. L’algorithme 222 (Basé sur un tableau de coûts cumulés)

Pour la seconde approche, j'ai structuré mes données sous la forme d'un tableau de seaux de coûts (que j'ai découvert plus tard correspondre à l'algorithme de Dial de 1969).

• Le principe : Les coûts étant contraints à des entiers (Integer 32 767), je stocke les points dans une variable tableau CCs indexée directement par leur coût cumulé.
• L'optimisation : Au lieu de faire un tri lourd à chaque étape, l'algorithme fait simplement « défiler » les indices de ce tableau vers l'avant jusqu'au prochain seau non vide. L'insertion d'un voisin se fait instantanément, ce qui élimine les surcoûts d'une file de priorité classique en VBA.
• Les limites et inconvénients : Cet algorithme se heurte vite à la limite de mémoire allouée pour un tableau de données de 8 octets. Cela limite le coût maximal du chemin le plus coûteux à environ 134 * 10 ^ 6 (= (2147483647 / 8) / 2). / 2 car la taille du tableau peut être 2 fois supérieure au coût du chemin.

Les performances sont fonction du coût du chemin, de hautes valeurs de random augmentent les temps de calcul.

• Les avantages : cet algorithme est très rapide, permet d’affronter des grilles de très grandes dimensions sans perte de performance significative et est efficace en 3D.

Pour le moment la dernière version de mon pathfinder est disponible sur le premier Post de ce fil.

Bon code à vous !

Bonjour Stéphane1972 !

Deux choses : Lors de l'utilisation du USF en augmentant la taille de la matrice, les colonnes au-dessus de 10, n'ont pas la même largeur !
la deuxième : un très grand merci pour la référence de mon Pseudo ! Cela me fait plaisir ! Si je vous dis que je ne pense pas que ce soit nécessaire vous me répondrez que si ! Alors j'en prend la joie de le voir ! Merci encore.

Bon je ne comprend pas tout dans le code. Sinon comment fait-on pour créer des obstacle sur le chemin afin de forcer un détour ? J'ai réussi en mettant des 999 dans certaines cellules... Peut-être n'ai-je pas vu "l'option".

Bon et beau travail et cette distribution Free !

@ bientôt

LouReeD

Bonjour LouReed,

Je suis heureux que nos chemins se recroisent !

Oui ça Bugge un peu sur la largeur des colonnes je vais devoir me repencher un peu sur la procédure NewMatrix pour l’instant il y a quelque chose qui m’échappe…

C’est vous que je remercie encore pour les raisons que j’ai évoqué dans la page d’aide.

Pour créer des obstacles il faut rentrer un entier négatif par exemple -1

Sinon la page d’aide n’est pas à jour le mode de calcul en arrivée flottante a été supprimé et il faut impérativement spécifier un point d’arrivée sinon bug.

Bonne journée et @+

Stéphane

Juste un petit ColumnWidth avec une valeur de 20 et un RowHeight avec une valeur de 13.

Mais il est vrai qu'il y a sur ma machine un petit temps avant de voir les cellules se mettre en place... Pourtant au niveau de la feuille il n'y a que le masquage de colonnes et lignes non ?

@ bientôt

LouReeD

Oui la procédure NewMatrix est assez décevante je vais essayer de revoir ma copie ! Avez-vous testé de grosses matrices et si oui que pensez-vous des performances du Pathfinder à proprement parler ?

@+

Bonsoir,

je n'ai pas fait de gros tests encore... désolé.

Je pourrais essayer de la comparer au code h2so4

Je vous tiens au courant, restez sur la fréquence !

@ bientôt

LouReeD

Bonsoir et merci d'avance,

Je reste sur la fréquence

Bonjour,

Je tiens d’abord à remercier (bien tardivement…) Sébastien pour le gros travail qu’il a effectué pour l’amélioration de la mise à jour de ma description longue.

Obligé de relativiser sur les performances de mon Pathfinder qui ne sont bonnes qu’à condition que les valeurs dans la grille soient basses (ordre d’idée : étagées de 0 à 250). L’intérêt de ce Pathfinder reste :

• D’être rapide si l’on respecte à peu près cette condition.
• De ne pas « bloquer » quand la taille de la grille augmente.
• De savoir résoudre efficacement les systèmes 3D.

Dans les précédentes versions de Propagation on recherchait par une boucle la case présentant le Coût Cumulé minimal et l’on pouvait alors calculer le coût cumulé de ses cases voisines et établir le lien de parenté. Le nombre de cases grappillées augmentant vite cette boucle se retrouvait en inflation plus ou moins rapide selon le mode Adjacent/Périphérique et 2D/3D. Ceci a pour effet de limiter la taille des grilles calculables dans un temps raisonnable.

Avec la version actuellement en ligne on ne recherche plus de coût cumulé minimal mais on enregistre ces coûts en tant qu’index dans une variable tableau de type liste de points :

Private Type Point2D
    X As Integer
    Y As Integer
End Type

Private Type lp     ' lp comme : Liste de Points
    p2d() As Point2D
    cp As Boolean    ' cp comme : Contient des Points
End Type

Après calcul du voisinage des nœuds courants on progresse dans le coût cumulé jusqu’à atteindre un booléen cp à True et on peut alors entamer une nouvelle itération de la boucle principale avec le nouveau coût cumulé incrémenté. Plus aucune boucle en inflation dans ce système donc un temps de calcul par cellule relativement stable quelles-que soient les dimensions de la grille.

Le fichier suivant (qui ne gère plus les obstacles et que les Bytes) offre la possibilité de tester des grilles de dimensions nettement supérieures à celles prises en charge par une feuille Excel classique.