Optimisation de trajet

**raph14** · 28/07/2016, 11h16

Bonjour,

Depuis quelque temps je me casse la tête sur un problème d'optimisation de trajet. Ce n'est pas le problème classique où il faut relier une seule fois les nœuds entre eux. Mais il faut passer par tous les chemins proposés, et bien sûr, optimiser le trajet.
Par exemple, une balayeuse de rue doit nettoyer toutes les rues d'un quartier. Le problème n'est pas tant qu'elle passe par toutes les intersections, comme c'est le cas dans quasiment tous les problèmes d'optimisation de trajet, mais qu'elle passe par toutes les rues. Quel est le chemin pour le plus rapide?

La grande majorité des algorithme ne concerne que les nœuds, le mien les chemins qui doivent être empruntés. Est ce que quelqu'un saurait répondre à cette question? Ou encore quel(le) théorie/algorithme je devrais regarder?

Merci d'avance
Raphaël

**Flodelarab** · 28/07/2016, 12h09

Bonjour

Les nœuds deviennent les arêtes et les arêtes, les nœuds.

Pour être plus clair, il me semble qu'on peut construire un graphe dont les nœuds sont les rues et les arêtes sont les carrefours.
Et tous les algorithmes qui traitent les nœuds deviennent alors pertinents pour ton utilisation.

N'est-ce pas ?

**Flodelarab** · 28/07/2016, 12h26

Autre réponse:
Sais-tu ce qu'est un cycle eulérien ?
Sais-tu ce qu'est un cycle hamiltonien ?
Cherches-tu à résoudre le problème du postier chinois ?

Invité · 28/07/2016, 12h32

Bonjour,
je me suis déjà posé la question sur le chemin le plus court, mais jamais en ces terme et je ne suis pas sur d'en être capable! mais il est évidant qu'il s'agit ici plus d'un calcule de surface que de distance. un peut comme pour définir le parcourt du ciseau pour réduire les chutes de tissu en couture!

je pense qu'il faut délimiter les figues géomatique de chaque bloc de bâtiments et analyser comment ils s'enchevêtrent fastoche...!

en gros ce que tu veux c'est pouvoir dessiner une étoile sans jamais lever le stylo!

**Menhir** · 28/07/2016, 12h51

rdurupt a raison, ce n'est pas un problème de distance puisqu'il faut passer dans toutes les rues et que leur longueurs sont connues.
Le problème est d'éviter de passer deux fois dans les mêmes rues (ou de le faire le moins souvent possible.
Pour ça, la méthode brute serait d'établir une liste de toutes les tronçons de rues en indiquant avec quelles tronçons il communique à chaque extrémité.
Tu prends ensuite un point de départ et tu teste toutes les possibilités, en vérifiant les redondances pour interrompre chaque recherche, et en ne gardant à chaque fois que celle qui est passée par moins de tronçons que celle retenue jusque là.