Djikstra par étapes

[guillaumcn]

Bonjour,

J'ai un graphe non orienté, complet (chaque sommet est relié à tous les autres) et pondéré (les liaisons entre les sommets ont un coup).

Existe t-il un algorithme ou solution qui permette de trouver le chemin le PLUS COURT passant par TOUS les sommets ?

J'ai bien évidemment pensé à faire toutes les combinaisons/enchainements de sommets possible et calculer à chaque fois leurs longueurs. Mais si je me retrouve avec un graphe de 50 sommets et donc 50 * 49 * 48 * 47 * 46 * 45 * 44 * 43 ... combinaisons possibles, l'ordinateur risque d'un peu galérer...

Merci d'avance pour votre aide.

[Ben314]

Salut,
J'y connait que dalle donc je pense pas t'être d'un grand secours, mais juste pour y réfléchir "dans le bon sens", est ce que :
- Tu cherche un "trajet circulaire" (i.e. cyclique) ?
- Tu as un point de départ et d'arrivé fixé par l'énoncé ?
- Autre option ?

[Pseuda]

Bonjour,

En effet l'algorithme de Djikstra, qui cherche le plus court chemin pour aller d'un sommet à un autre du graphe, ne passe pas nécessairement par tous les sommets (il cherche plutôt par passer a priori par le moins de sommets possibles, mais pas obligatoirement).

En effet l'ordinateur risque de galérer à faire tous les chemins : 50! ...

[guillaumcn]

Le chemin doit passer par tous les sommets (sans répétitions). Je sais pas ce que tu entends par circulaire mais le chemin a un sommet de départ et un sommet d'arrivée (qui sont connus).

En gros, il me faut un chemin eulérien, mais le plus court possible.

[nodgim]

Il s'agit donc plutôt du problème dit du " voyageur de commerce " qui doit se rendre dans toutes les villes d'une zone donnée en faisant le moins de kilomètres possibles.

[guillaumcn]

En effet c'est bien ce problème la. A la seule différence que mon point d'entrée est différent de mon arrivée...

Il semblerait qu'il n'existe pas de solutions sauf le système d’énumérer toutes les solutions possible : qui prendrait 2 millénaires à résoudre à partir de 20 points selon wikipédia

[pascal16]

Si on veut passer par toutes les arêtes d'un graphe, la recherche d'une chaîne Euclidienne est simple.
Si on veut passer par tous les sommet, la recherche d'une chaîne Hamiltonienne est compliquée, il n'y a pas de méthode globale, mais des encadrement sont possibles.

Dans le cas d'un graphe complet, ça m'étonne qu'il n'y ai pas de solution.
Pourquoi ne pas d'abord commencer par regarder les 2 arêtes de poids le plus faible de chaque sommet postuler qu'il y a un chemin qui utilise ces arêtes. Ca donne au moins un minimum.

[Ben314]

Dans le cas d'un graphe complet, ça m'étonne qu'il n'y ai pas de solution.

Perso, ça m'étonnerais beaucoup qu'il y en ait vu que dans le problème du voyageur de commerce, ça ne me semble pas poser de soucis de rendre le graphe complet s'il ne l'est pas au départ : il suffit de créer des arrêtes entre les points non reliés entre eux et de mettre dessus un poids égal à 10^100 histoire d'assurer que l'algo. ne choisira jamais ces arrêtes là.
Et comme le problème du voyageur de commerce reste non résolu en temps polynomial. . .

De plus, si comme dans ton cas tu as une ville de départ et d'arrivé imposée, c'est à dire que tu cherche réellement un "chemin" et pas un "cycle", c'est encore plus la m... sur le plan théorique du fait que ça disymétrise le problème

[pascal16]

un encadrement :
pour chaque sommet, je fais la somme des deux arêtes de poids le plus faible
je fais la somme, je divise par 2, j'ai un minorant.

pour à algo qui donne un majorant :
Je pars d'un sommet, je me rend au sommet adjacent qui n'a pas déjà été visité et dont l'arête a le poids le plus faible. Le fait que la graphe soit complet (ou complété) dit que c'est toujours possible et qu'on va faire tous les sommets.

Pas mieux pour ce soir