[PVC] christofides : couplages

**lechewal** · 22/10/2006, 21h13

Bonjour,

dans le cadre de la résolution du problème de voyageur de commerce
avec l'algorithme de christofidès, je ne saisi pas bien la partie de
l'algorithme où il faut réaliser les couplages de cout minimum sur
les sommets de dégrés impairs.

j'ai mon arbre recouvrant minimum et ma liste des sommets de degré
impair..
J'ai donc aussi les aretes du graphe (A), et la liste de sommets (V) donc je peux chercher sur G' =(V,A)
Mais trouver des couplages ne s'apparente pas à trouver un arbre donc prim ou kruskall non apliquable..

j'aurai bien une idée d'algo très naïf mais bon..;

merci
a+

**borisd** · 24/10/2006, 14h15

Bonjour,
je n'ai pas de réponse précise, mais vu que personne ne répond, j'y vais quand même...
Je sais que pour calculer des couplages maximums il suffit de rechercher successivement des chaines alternées. Pour un couplage parfait de coût min, apparemment Edmonds a proposé un algo en 1965; il y en a eu de plus efficaces par la suite.
Voici des références sur des sujets approchants :
Le premier ne traite apparemment que de la recherche d'un couplage parfait
http://www-math.mit.edu/~goemans/18434/edmonds.pdf
A première vue, celui-ci compare différents algos en expliquant celui de Edmonds mais sans le donner explicitement. Peut-être que dans la biblio tu trouveras ton bonheur...
http://www2.isye.gatech.edu/~wcook/papers/IJOCmat.pdf

**FrancisSourd** · 24/10/2006, 19h15

Il y a une description dans le livre de Diestel. Il s'agit bien d'un couplage (matching) dans un graphe quelconque (les couplages dans les graphes bipartis sont souvent enseignés, ce qui n'est pas le cas des couplages dans les graphes quelconques).

http://www.math.uni-hamburg.de/home/...ory/index.html

**lechewal** · 24/10/2006, 19h40

a priori, il y aurait l'algo d'edmonds, en n3

mais en selectionnant les arretes minimum et en ameliorant par 2-opt, on doit pouvoir obtenir une solution bonne, voir optimale ?

**FrancisSourd** · 25/10/2006, 09h41

Envoyé par lechewal

en ameliorant par 2-opt, on doit pouvoir obtenir une solution bonne, voir optimale ?

Bonne oui mais pas optimale à tout coup. D'une manière pratique, l'algorithme de Christofides (qui a une garantie de performance 3/2) ne se comporte pas mieux, dans la plupart des cas, que des algorithmes sans garantie (plus proche voisin) ou avec garantie 2 (basé sur l'arbre couvrant sans le couplage). En revanche, la recherche locale (2-opt et raffinements) donne de très bons résultats.

**lechewal** · 25/10/2006, 22h34

Une question relative au 2-opt précisément..

Je connais l'algo, mais sur un cycle hamiltonien déjà créé, lequel on améliore.

Seulement, il semblerait qu'ici, il faille effectué l'algo sur les couplages !?

**borisd** · 26/10/2006, 01h11

Un couplage non optimal te donnera simplement un cycle eulérien moins bon, améliorable par 2-opt tout comme celui obtenu avec un couplage optimal.
Je pense qu'il est inutile d'essayer d'améliorer seulement les couplages (amélioration très locale) pour ensuite effectuer une amélioration plus globale sur tout le cycle, qui a de grandes chances de défaire les améliorations précédentes.

**lechewal** · 02/11/2006, 11h31

mh, j'ai vraiment du mal a faire mon 2-opt sur une liste d'arcs.. Faire les modifs en même temps, c'est pas aisé..

**borisd** · 02/11/2006, 11h46

Je ne suis pas sûr d'avoir compris ton problème : n'est-il pas possible, si tu as deux arcs (i,j) et (k,l) dans ta liste, de les remplacer par (i,l) et (j,k) s'ils existent ?