Labo Algo
Labo Algo
L'algorithme glouton - ou l'algorithme de la meilleure insertion - est une des méthodes classiques pour résoudre le problème du voyageur de commerce. Il s'agit de construire le parcours ville par ville, en insérant dans le parcours la ville qui le rallonge le moins.
A première vue, on ne voit pas pourquoi on ne trouverait pas toujours l'optimum... Et pourtant c'est faux !
On peut démontrer que si un parcours de N-1 villes est optimal, en ajoutant la Nième ville par cette méthode, le parcours obtenu n'est pas optimal !
Voici un contre exemple expliqué par Jazem Halioui.
Mais d'abord, un petit rappel de l'algo glouton :
Sur les N villes du problème, on commence par en relier 3 au hasard pour constituer le chemin initial (c'est un triangle).
Prenons par exemple les villes 1, 2 et 3.
Le triangle les reliant est unique donc c'est le chemin optimal pour ces 3 villes.
Pour les N-3 villes restantes (villes 4 à N), on effectue l'opération suivante :
Etape i : On introduit la ville dans le chemin (ou l'enveloppe) construit à l'etape précédente i-1, en esayant de nous assurer
que le nouveau chemin obtenu allonge le moins le parcours :
Appelons C la ville à insérer. On devra supprimer un seul arc [AB] reliant
deux villes A et B du trajet contruit à l'étape i-1, et le remplacer par les deux arcs [AC] et [BC]
Il faut donc choisir les deux villes A et B appartenant déjà au trajet, telles que la
quantité d(A,C)+d(B,C)-d(B,C) soit minimale.
La ville C étant fixée à l'étape i, et la ville B étant la suivante de A dans le trajet de l'étape i-1, il suffit donc de prendre le minimum du coût en faisant varier la ville A.
En résumé, on obtient ainsi à chaque etape un trajet reliant une ville de
plus que l'étape precedente, (boucle sur N-3 elements)
avec une fonction d'evaluation de minimum a chaque itération dont le coût
est de l'ordre inférieur à N.
(Bien sur plusieurs opitmisations sont envisageables pour améliorer la performance...)
On suppose que l'on part d'un trajet i optimal (en rouge sur le schéma). On ne nous souciera pas des villes non représentées sur le schéma. Pour avoir des calculs simples, j'ai choisi des points tels que :
DE=CD=CE=1 AC=CB=AB=1ABC et CDE sont donc des triangles equilateraux.
Figure 1 : trajet optimal à l'étape i
Figure 2 : trajet obtenu par l'algo glouton
Figure 3 : trajet optimal
En effet : appelons Delta1 la distance rajoutée au schema 2 par rapport au chemin 1
et Delta2 la distance introduite au schema 3 par rapport au 1
Delta 1 = AJ + JC - AC = 1/2 + Racine(3)/2 - 1 = 0.36 Delta 2 = AJ + JB - AC - BC + DC + CE - DE = 1/2 + 1/2 - 1 - 1 + 1 + 1 - 1 = 0
Il est donc clair que Delta2 < Delta1, c'est-à-dire que le chemin de la figure 3 est plus court que celui de la figure 2.
CQFD
Remarque par rapport à l'algorithme 2-opt : Si l'on part du trajet de la figure 2, on ne peut pas non plus obtenir le chemin optimum de la figure 3 par un 2-opt ! Les deux algorithmes sont donc pris en défaut par ce problème.
Par contre, si on effectue ce que j'appelle un "insertion-opt" (c'est à dire qu'on retire une ville i du parcours et on essaye de l'insérer entre la ville j et sa suivante dans le parcours, pour voir si on obtient un trajet plus court)
Donc pour cet exemple, l'algo glouton + insertion-opt pourrait trouver l'optimum. Mais ce ne serait probablement pas le cas pour tous les problèmes !
Vos réactions sont les bienvenues sur le forum du Problème du Voyageur de Commerce (accès direct au fil de discussion concernant cette page)
Ecrit par Jazem Halioui. Reformulé et mis en forme par Alexandre Aupetit.
Labo Algo
Jazem Halioui et Alexandre Aupetit, Janvier 2004 - Mai 2004