Discussion :

[Z20500]

Bonjour,

Je cherche à faire un algorithme qui me remette des villes dans un ordre géographique.
Le problème est le suivant : j'ai des fiches horaires de bus qui parcourent une ligne donnée, mais ne s'arrêtent que dans certains points.
J'ai une fiche horaire par bus, qui ne comprend que les arrêts du bus.
Avec toutes les fiches horaires, je souhaiterais avoir une liste de tous les arrêts de la ligne dans l'ordre :
par exemple, avec :

Bus 1 : Dammartin, Soissons, Anzy
Bus 2 : Soissons, Laon
Bus 3 : Paris, Aulnay, Soissons, Laon

Je souhaite obtenir : Paris, Aulnay, Dammartin, Soissons, Anzy, Laon.
En l'occurrence, il me semble qu'on ne peut pas déduire de manière certaine que Anzy soit avant Laon, ni que Dammartin se trouve après Aulnay. Il faut donc un bus 4 :

Bus 4: Aulnay, Dammartin, Anzy, Laon.

Une petite complexité supplémentaire : je ne reçois pas toutes les fiches horaires en même temps, il faudrait donc une forme de stockage intermédiaire pour que le programme puisse mettre la liste à jour au fur et à mesure. Je suppose donc qu'il faut une deuxième liste qui marque la relation d'ordre :
Après le bus 3, on aurait :

Paris (?,1)
Aulnay (-1,2)
Dammartin (?,1)
Soissons (-1,1)
Anzy (-1,?)
Laon(-2,?)

Dans les parenthèses se trouvent les positions relatives des points qui ont permis de donner l'ordre de chaque point (premier chiffre pour avant, deuxième pour après) L'ordre est certain quand tous les chiffres sont égaux à 1 ou -1.

Est-ce que vous connaissez un type d'algorithme dont je pourrais m'inspirer ? Le programme tournerait sous VBA.
En vous remerciant,
Bon week-end

[Flodelarab]

Bonjour,

il n'y a pas de relation d'ordre dans les espaces à plus d'une dimension.

[souviron34]

bah, en général les lignes ont une direction globale. (ça pourrait par exemple être la moyenne des arctangentes des arrêts)

Suivant cette direction tu as une distance depuis le point initial.

Donc, suivant ton plan initial des lignes (par exemple pour Paris RP c'est à peu près une roue de vélo), tu peux établir, par ligne, une "liste des distances".. par exemple en prenant la projection par rapport à la ligne "moyenne" ...

De là tu peux "joindre" les lignes en cherchant les plus proches voisins (début, fin)

[tbc92]

Bonjour,
Selon ce que tu dis, s'il y a un bus qui passe par V1 puis V2, il semblerait que V1 soit forcément AVANT V2... et donc dans tes données, on a l'assurance que aucun bus ne passera par V2 PUIS V1.
C'est surprenant. Tu confirmes ?

Pour un besoin un peu similaire, (mais avec possibilité d'avoir V1 avant V2 sur une ligne, et V1 après v2 sur une autre ligne), je procède de la façon suivante :
Pour chaque Ville V1, calcul du rang moyen.
Puis tri sur ce rang moyen.

C'est très basique, mais selon les besoins, ça peut suffire.