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
Partager