Le 11/01/2017 à 17:14, Julien Coupey 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
C'est dommage, et mon usage potentiel (passer partout, à vélo ou en
voiture pour prendre des photos) rentre dans le cas des situations qui
sont plus compliquées. (gestion des sens unique, gros gros malus sur les
demi-tour, etc..)
Stf
_______________________________________________
Talk-fr mailing list
Talk-fr@openstreetmap.org
https://lists.openstreetmap.org/listinfo/talk-fr
