Discussion :

[akuSaia]

Bonjour,

Je vais essayer d'être aussi concis et exhaustif que possible :

La situation :
Je suis actuellement en stage de recherche et au cours de la procédure d'échantillonnage d'arbres, moi et mon équipe avons conclu que je devais procéder à un échantillonnage systématique de ma population.
Mais encore ? --> Je dispose d'un fichier excel avec environ 720 arbres référencés comportant 1)-un numéro 2)-coordonée GPS X 3)-coordonée GPS Y (donc coordonné spatiale quoi ) attention, il n'y a pas de logique spatiale dans les numéros (le numéro 2 peut être environné de numéro 5XX , 270 etc ...).
La procédure d'échantillonnage systématique se décrit comme suis :
-calculer la longueur d'un "chemin" hypothétique partant d'un point et passant par tous les autres puis revenir. Théoriquement, ce chemin doit être le plus COURT possible.
-l'échantillonnage se fait ensuite en choisissant le point de départ du chemin au hasard (utilisation d'une table de nombre aléatoire), on suit ensuite le chemin précédemment trouver et on procède à un choix "systématique" des arbres selon la logique suivante : la distance totale du chemin est divisé par la taille de l'échantillon (nombre d'arbres), mettons le chemin fais 100 km, on veut 20 arbres --> la distance d1=5km. On part donc d'une point aléatoire, on suit le chemin, et tous les 5km, on sélectionne l'arbre le plus proche sur le chemin.

Cela permet d'avoir un échantillon relativement aléatoire mais surtout répartie spatialement.

Je dispose de plus, d'un fichier excel comportant un tableau avec pour chaque point, sa distance le séparant des autres points.


Mon problème --> :
M'ayant un peu documenter sur la question, l'histoire du chemin le plus court, sur 720 points, ça m'a l'air un trop gros poisson pour moi à première vu (cf wikipédia anglais avec Shortest Pathways ou The Travelling Salesman Problem) qui se résolve à grand coup d'algorithme, qui sont compréhensible pour la plupart mais surpasse de loin ce que je suis capable de faire sans aide et dans un délai raisonnable sur VB.
Il me faudrait donc créer une macro pour
-calculer un chemin potable, c'est à dire, court sans être forcément LE plus court en utilisant PAR EXEMPLE, le point le plus proche pour bouger de sommet en sommet (théoriquement ce n'est pas la meilleur solution mais ça reste une solution pas mauvaise non plus), en partant d'un point donné par l'utilisateur (qui sera choisit avec la table des nombres aléatoires)
-il faudra conserver l'ordre de passage sur chaque point, puis, en partant du point de départ, effectuer l'échantillonnage systématique (le nombre d'arbre à sélectionner est 54 (55 - le point de départ)), tous les "x" km en sélectionnant le point le plus proche et en le mettant dans une liste.

Niveau algorithme, j'ai trouvé deux trois trucs qui peuvent être intéressant
-l'algorithme des colonies de fourmis (http://fr.wikipedia.org/wiki/Algorit...ies_de_fourmis)
J'ai déjà vu ce truc en cours, je comprends pas trop mal le concept mais de là à coder ça ..
-l'algorithme de Djikstra (http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra)

Du coup ce que je vous demande en gros c'est :
-quel solution semble la plus envisageable dans ce cas, sachant que la contrainte temporel est forte (une autre façon de dire que je suis pressé ^^, car il faut que je récolte les échantillons avant Noel !), c'est à dire quelle méthode/algorithme utilisé ?
-une fois déterminé l'algorithme/la méthode, je vais m'atteler au codage de la bestiole mais n'ayant pas un niveau de ouf je vais sûrement revenir vous voir pour poser des petites questions sur le code. Je n'ai pas codé en VBA depuis un moment (j'ai eu un cours qui du duré ...2 mois dessus) et du coup j'ai plein de trou et de soucis, du style : comment crée la liste des sommets traversés pour garder la trace de l'ordre des points sur le chemin etc ...

Voilà, je crois avoir tout dit, j'espère que vous pourrez m'aider sur ce truc !
A noter que malgré l'urgence de la situation qui fait que je ne cracherais pas sur un code tout fait, je ne vous demande pas ici de me faire tout le boulot mais de m'orienter vers une solution pas trop mauvaise et faisable par un presque débutant de VB, et ensuite m'aider lors de la rédaction sur certains détails du code / syntaxes.

Merci d'avance !

PS : je suis sous excel sur MAC, version 14.2.3

Akusaia

[Jean-Philippe André]

Salut,

Dijkstra est la solution la plus "facile" à utiliser, d'autant plus qu'il existe un grand nombre de ressources en VBa disponibles sur le net

Il faudra de toute façon bien comprendre l'algorithme, car le codage sera simple une fois cette étape franchie.

Restera à voir si les temps de calculs/réponses seront cohérents avec tes contraintes par ailleurs

[akuSaia]

Dac, je vais donc partir sur ça.

Juste au cas où, hier j'avais peut être trouvé un moyen pas trop mauvais en utilisant le tableau des distances entre chaque point :
-une fois rentré le numéro d'identification d'un point on applique une fonction Min sur la ligne correspondante --> plus petite distance.
-en utilisant la fonction Research sur cette même ligne et sur la valeur précédente (ya pas de doublon sur une ligne) on renvoie le numéro d'identification du point le plus prêt.
-on met ce point dans un ensemble pour garder la trace des points traverser.
-on continue en partant du point trouver préalablement en checkant cette fois si le nouveau point n'appartient pas à l'ensemble des points déjà traverser.

Par contre le chemin ne revient pas au point de départ, mais c'est facile d'ajouter au point finale la distance qui le sépare du point initiale.

Mais j'avoue m'être poser une question stupide : en utilisant les fonctions de la feuille de calcul, Min et Research c'est super easy, après, repasser sur VBA ... comment on fait pour coder Min(B3:B700) sur VBA par exemple ?

En faite, en y réfléchissant, Dijkstra c'est pas le bon truc, car il calcul le plus court chemin entre deux points sur un ensemble de noeud, dans mon cas il faudrait rajouter la contrainte : "en passant par tous les points". Je viens juste de comprendre la différence entre "Le chemin le plus court" et le "problème du marchand itinérant" . Le second doit se taper tous les points, alors que le premier ne s'intéresse qu'au chemin entre deux points, sans la contrainte de passer par tous les noeuds ... je vais tester la version "point le plus proche".


Merci en tout cas de m'aider sur ça ^^

Aku

[mercatog]

Regardes ce lien et les liens qui s'y trouvent, un début de piste

http://www.developpez.net/forums/d11...sieurs-villes/

Bien sur pour ton cas de figure, plusieurs choses à simplifier.

[akuSaia]

Ah ouai bien ! Merci !
Ayant les coordonnées (x,y) pour chaque point et le tableau des distances entre les points, je peux théoriquement assez facilement faire tourner ton programme.

Par contre, il faut que je regarde deux trois trucs
-est-il possible de mettre TOUS les point en Input
-que je modifie la taille du tableau des Input, vu que j'ai 700 points au lieu d'une dizaine de ville, à moins que ce soit auto ... ? Ca à l'air !

Merci beaucoup ,je fais travailler sur ça aujourd'hui,si je m'y mets bien je devrais pouvoir faire une test dans la journée.

EDIT : premier soucis : Erreur de Compilation Projet ou bibliothèque introuvable.
Sachant que je suis sous mac, j'imagine que certains trucs vont poser soucis ... Sachant que la carte ne l'intéresse pas spécialement, comment puis-je subtilement lui demander de ne rien faire à ce niveau ?

Merci beaucoup en tout cas mercatog !

Akusaia

EDIT2 : ton programme marche sans modif. Je lance avec mes trucs du coup.
PS : est-il grave si au lieu de nom de ville j'ai des numéro de point ? je veux dire s'il cherche un string alors que c'est un nombre ... je rajoute une lettre dedans ?
EDIT3 : j'ai testé en mettant les numéro en format texte ... Marche pas, cette fois il me met "Nombre de villes insuffisants, minimum4".
EDIT4 : le prob viendrais de la fonction Private Function Lst() As String qui me renvoie "Projet ou Bibliothèque introuvable" . Il me sélectionne l'objet "Mid" dans le code ... source du problème ?
EDIT5 : ok j'ai capito le truc, c'est la façon dont Input est déterminé qui doit être changer, car il n'y a plus sélection une par une des villes mais la colonne Input est juste la copie de la troisième colonne de Data dans mon cas. Je taf sur ça !

[mercatog]

Oh là là là
Du calme du calme.

Le fichier tel n'est pas destiné à ton problème particulier. C'était pour vous montrer l'algorithme 2-opt (lien par exemple).

Alors, ne transposes pas de sitôt ton problème au fichier donné en lien d'autant plus qu'ils n'ont pas le même objectif.

Je te propose de voir le code, de l'étudier et après, tu fera ton propre programme se basant sur ce que tu as appris.