Dans ce cas une solution sous-optimale si le secteur ne correspond pas
exactement c'est de suivre un facteur ou mieux un éboueur.
Mieux pour l'efficacité (ils passent par toute habitation même si la
poubelle n'est pas dehors), mais pour les odeurs, un facteur c'est sans
doute plus agréable à suivre ;-).
Et tu fais une fois la tournée pour voir et une deuxième pour pratiquer.
Ou tu demandes s'ils veulent pendre une trace GPS. Comme la Poste veut
tout vendre, ils vont sûrement être d'accord pour que le préposé aux
postes charge sa besace d'un enregistreur GPS.
Jean-Yvon
Le 11/01/2017 à 17:14, Julien Coupey - [email protected] a écrit :
Salut
Les problèmes de tournées consistent à passer par tous les nœuds d'un
certain graphe (avec éventuellement des contraintes additionnelles).
La nature du problème du postier chinois est différente puisqu'il
s'agit de visiter tous les arcs d'un graphe, donc malheureusement la
réponse à ta question est non. ;-)
Concrètement, si le sens de visite des chemins n'a pas d'importance et
s'il n'y a pas à tenir compte de sens uniques (par exemple à pied),
alors le graphe est non orienté et il existe des méthodes
réalistes/efficaces en temps de calcul pour trouver la solution optimale.
Par contre, si tu dois tenir compte des sens uniques et/ou si le sens
de visite a de l'importance (par exemple tu veux passer dans les rues
une fois dans chaque sens), alors là le problème se complique nettement !
À +
Julien
_______________________________________________
Talk-fr mailing list
[email protected]
https://lists.openstreetmap.org/listinfo/talk-fr
