Bonjour à tous, 

J’espère être dans le bon forum :

Alors j'ai un petit projet perso mais je ne sais pas comment le commencer... 

Je me remets doucement au VTT, et pas loin de chez moi il y a une chouette foret (ok super quel rapport avec l'info ?) sauf que bah comme toute foret il y plein de chemins et je cherche à optimiser mon parcours : 

 

(l'image est de dimension [6374x2557] ouvrez la dans un nouvel onglet pour plus de "confort visuel")

Je cherche le chemin le plus long entre un point de départ et d'arrivé définis qui me permet de passer par TOUS les segments au moins une fois. 

En gros je veux parcourir la distance la plus grande tous en passant par le plus grand nombre de chemins différents (d'ou la variante du problème du voyageur de commerce...)

Alors bien sûr je ne vous demande pas de résoudre le problème mais de m'aider, de me donner quelques pistes de résolutions, etc. 

Merci à vous ! 

Edit : en me baladant sur Wikipedia il s'agit plus du problème du postier chinois je pense... 

-
Edité par JahMall 10 mai 2016 à 18:41:12

Sur ton problème, tu peux de mémoire avoir une solution exacte en temps poolynomiale, car c'est une version bien plus simple du voyageur de commerce (en fait, ce n'est même plus un voyageur de commerce). La raison est simple : tu as la connaissance que pour 3 villes données. Si elles sont reliées ensembles, si tu prends deux arêtes, la troisième est forcément inférieur ou égale à la somme des deux premières.

Bonjour,

le problème tel que tu le poses n'a pas vraiment de solutions … tu peux rendre le chemin arbitrairement long en faisant des aller/retours sur un chemin ou en parcourant un cycle un nombre arbitraire de fois.

Salut picodev, oui mais si je dis qu'il faut que je passe le moins de fois possible par le même segment ça réduit le problème et augmente les solutions non ?

Ce qui te ramène plus ou moins au problème du postier chinois