1 la complexité de certaines problématiques

Le problème du voyageur de commerce évoqué dans les médias traditionnels

n’est pas rare !
Les algorithmes que nous avons rencontrés jusqu’à présent, comme dans Search
More Trajets, bons en termes de planification ou problèmes centraux de flux
maximum, ont un temps de calcul qui obéit à une fonction polynomiale. L’ampleur
du problème. Par exemple, dans le cas du problème du chemin le plus court, la
taille du problème est donnée par le nombre de sommets et d’arcs dans le graphe
et le nombre de sommets et d’arcs dans le graphe du voyageur de commerce.
Pour mesurer l’efficacité d’un algorithme, on évalue l’ordre de grandeur du nom-
bre d’opérations, c’est-à-dire les opérations de base que les ordinateurs doivent
effectuer (addition, multiplication, affectation, etc.) en fonction des données,
lorsque la taille du problème approche l’infini.

1.1 Évaluer le temps de calcul en fonction de la nature de

l’algorithme et de la quantité de calculsquestion
On considérons 4 algorithmes avec le comportement suivant :
ˆ Temps proportionnel à n: par exemple, l’algorithme de Bellman.
ˆ Temps proportionnel à n2 : comme l’algorithme de Dijkstra.
ˆ Temps proportionnel à n3 .
ˆ Algorithmes exponentiels.
Dans chaque cas, nous supposons que nous résolvons a en un millième (10 –3)
secondes Question n°10.
Qu’arrive-t-il au temps de calcul lorsque la taille du problème est multipliée par
10, 100 ou 1 000, donc 100, 1 000 ou 10 000 ?dans le tableau suivant les temps
sont en secondes par 10, le temps est également multiplié.
taille- 10 100 1000 10000
algo en n 10−3 10−2 10−1 1
algo en n2 10−3 10−1 10 1000
algo en n2 10−3 1 1000 1000000
algo en en 10−3 1039
On atteint donc la taille 10, 000 (taille multipliée par 1, 000) en 1 seconde
(10−3 × 103 ).

Pour l’algorithme en n2 , lorsque la taille du problème est multipliée par 10,

le temps de calcul est multiplié par 102 .

Pour l’algorithme en n3 , lorsque la taille du problème est multipliée par 10,

le temps est multiplié par 103 . Donc si la taille est multipliée par 100, le temps
sera multiplié par 1003 = 106 , soit 1 million ! Dix mille secondes équivalent à
11,5 jours !

e100
Pour l’algorithme en en , le temps est multiplié par e10 = e90 , qui est de
l’ordre de 1039 , un 1 suivi de 39 zéros !

1
 Le problème du voyageur de commerce entre dans la catégorie des problèmes
qui ne nous intéressent pas.

Il n’existe actuellement aucun algorithme permettant une augmentation raisonnable

du temps de calcul, c’est-à-dire des algorithmes polynomiaux pour cette taille
de problème.

Lorsque la taille du problème devient importante (peut-être des centaines de

villes, selon les données), on se contente de petits problèmes ou on abandonne
l’idée de chercher la meilleure solution.

Les enjeux économiques étaient si importants qu’au début du troisième

millénaire, le Clay Institute a été fondé. Ce dernier a proposé un prix de 1
million de dollars pour quiconque trouverait un bon algorithme pour résoudre
des problèmes comme celui du voyageur de commerce.

Pour relever ce défi, nous employons une méthode d’approximation, également

appelée heuristique , qui nous permet de trouver rapidement une solution que
nous espérons ne pas être trop éloignée de la solution optimale.

2 Méthodes pour résoudre le problème du voyageur

de
Pour résoudre le problème du voyageur de commerce Il existe de nombreuses
heuristiques pour résoudre le problème du voyageur de commerce.

2.1 Heuristique du voisin le plus proche

En principe, cette méthode consiste à partir de n’importe quelle ville et à se
diriger vers la ville la plus proche non encore visitée. On continue ainsi jusqu’à
ce que toutes les villes soient visitées, puis on revient à la ville de départ.
Exemple :
Si nous partons de a et que la ville la plus proche est b, alors nous visitons
successivement c, d, e, puis retournons à a.
Le chemin obtenu est : a → b → c → d → e → a.

Longueur totale : 5 + 10 + 5 + 8 + 10 = 38.

Cette heuristique très simple peut toutefois produire des résultats arbi-
trairement mauvais. Par exemple, si la longueur de l’arête (a, e) est égale à
un nombre M arbitrairement grand, l’heuristique donnera toujours le chemin
a → b → c → d → e → a, de longueur 28 + M , au lieu d’un tour optimal de
longueur 39 (a → b → c → e → d → a), si (a, e) > 11.

2.2 Heuristique du tri des arêtes

En principe, cette méthode consiste à trier les arêtes par longueur croissante,
puis à parcourir la liste triée en ajoutant les arêtes une par une si elles respectent
les deux contraintes suivantes :

2
 ˆ Elles ne forment pas de cycle prématuré (avant de couvrir toutes les villes).

ˆ Un sommet n’a pas plus de 2 arêtes adjacentes (pas de bifurcation).

Étapes :
1. Trier les arêtes par ordre de longueur croissante.
2. Prendre la première arête non sélectionnée de la liste triée.

3. Ajouter cette arête si elle respecte les contraintes mentionnées.

4. Répéter jusqu’à ce que toutes les villes soient couvertes.
Exemple :
On commence par (a, b) de longueur 5, puis (c, d) de longueur 5, puis (c, e)
de longueur 7.
On ne peut pas prendre (e, d) de longueur 8, car cela créerait une sous-boucle
(c → e → d → c). On sélectionne donc (a, d) de longueur 9, puis (b, e) de
longueur 14.
Le tour obtenu est a → b → e → c → d → a, de longueur totale 40.
Avantage : Contrairement à l’heuristique du voisin le plus proche, cette
méthode est moins sensible à des arêtes particulièrement longues, car elles sont
sélectionnées en dernier.

2.3 Évaluation des performances heuristiques

Pour évaluer les performances d’une heuristique, on compare la solution obtenue
à la solution optimale (si connue) :
Longueur heuristique
Performance relative =
Longueur optimale
Par exemple, si la longueur optimale est 38 et la solution heuristique donne
40, la performance est :
40
≈ 1.05 (soit 5% au-dessus).
38

2.3.1 Exemple : Résolution avec heuristiques

On commence par (a, b) de longueur 5, puis (c, d) de longueur également 5, et
ensuite (c, e) de longueur 7.
Contraintes : On ne peut pas prendre (e, d) de longueur 8, car cela créerait
une sous-boucle (c → e → d → c). À la place, on sélectionne (a, d) de longueur
9, puis (b, e) de longueur 14.
Ainsi, on obtient un tour de longueur totale :

a→b→e→c→d→a avec une longueur de 40.

3
2.3.2 Comparaison avec l’heuristique du voisin le plus proche
Contrairement à l’heuristique du voisin le plus proche, si la longueur de l’arête
(a, e) augmente jusqu’à M , les nouvelles arêtes (a, e) n’ont aucune chance d’être
conservées. Les arêtes sont vérifiées dans l’ordre croissant, ce qui conduit à un
tour :

b → e → c → d → a.

2.3.3 Évaluation des performances heuristiques

Nous venons de voir que l’heuristique du voisin le plus proche peut produire
des résultats très éloignés de la solution optimale. Pour évaluer la performance
d’une heuristique, on compare la solution trouvée à la solution optimale.
Méthode : On évalue la performance relative :
Longueur heuristique
Performance relative =
Longueur optimale
Exemple :
ˆ La longueur des 5 côtés les plus courts est au moins 34.
ˆ L’heuristique 2 donne un tour de longueur 40. La différence est donc :

40 − 34
≈ 17%.
34
ˆ En réalité, la durée optimale du tour est 38. Deux solutions optimales
existent : a → b → c → d → e → a et a → b → d → c → e → a, données
par l’heuristique du voisin le plus proche.

2.4 Graphe euclidien et performances garanties

Lorsque le graphe est euclidien, l’inégalité triangulaire est vérifiée :

c < a + b, b < a + c, a < b + c.

Ainsi, la longueur du trajet fournie par l’heuristique est, dans tous les cas :

Inférieure à 2 × la meilleure tournée.

Actuellement, l’heuristique la plus célèbre pour le problème euclidien garan-
tit que la durée est inférieure ou égale à 1, 5 fois la durée optimale. Sa perfor-
mance est donc qualifiée de :

Performance garantie : 1.5.

2.5 Travaux récents

La problématique du voyageur de commerce a généré beaucoup de travaux de
recherche. Par exemple, la solution optimale au problème des 15, 112 villes en
Allemagne a été calculée en 2001 à l’aide de méthodes mathématiques complexes
et de calculs parallèles sur un parc d’ordinateurs.