Problème — Le voyageur de commerce métrique

1. La minoration. Soit $T^{\ast }$ un circuit optimal, de longueur $OPT$. En lui retirant une arête, on obtient un chemin passant par tous les sommets : c'est en particulier un arbre couvrant. Son poids vaut $OPT$ moins la longueur de l'arête retirée, donc $\le OPT$. Comme l'arbre couvrant minimal est le plus léger de tous :

$$\text{poids}(ACM)\le OPT.$$

Vérification : sur $2000$ nuages de points euclidiens de $5$ à $9$ villes, l'optimum étant calculé par énumération de toutes les permutations, l'inégalité n'a été violée aucune fois.

C'est le patron annoncé par le chapitre : on n'a pas calculé l'optimum, on l'a minoré par une quantité qu'on sait calculer — ici l'arbre couvrant minimal du chapitre chap:unir.

2. L'algorithme. On construit l'arbre couvrant minimal, on le parcourt en profondeur, et l'on visite les villes dans l'ordre de première rencontre.

(* Tournee approchee du voyageur de commerce metrique.
   Entrees : n villes, d.(i).(j) une distance verifiant l'inegalite triangulaire.
   Sortie  : une tournee de longueur au plus 2 fois l'optimum.
   Complexite : O(n^2 log n) -- Kruskal sur le graphe complet. *)
let tournee n d =
  let arbre = acm n d in                       (* Kruskal, chapitre 23 *)
  let vu = Array.make n false and ordre = ref [] in
  let rec descendre u =
    vu.(u) <- true;
    ordre := u :: !ordre;                      (* ordre PREFIXE : premiere visite *)
    List.iter (fun v -> if not vu.(v) then descendre v) arbre.(u)
  in
  descendre 0;
  Array.of_list (List.rev !ordre)

La preuve du facteur $2$, en trois pas.

• Un parcours en profondeur qui emprunte chaque arête deux fois — une en descendant, une en remontant — visite toutes les villes et revient au départ. Sa longueur vaut exactement $2\times \text{poids}(ACM)$.
• La tournée rendue est obtenue à partir de ce parcours en sautant les villes déjà visitées : au lieu de $u\to v\to w$, on va directement de $u$ à $w$. L'inégalité triangulaire garantit $d(u,w)\le d(u,v)+d(v,w)$ : chaque saut raccourcit, ou du moins n'allonge pas.
• Donc $\text{longueur}(ALG)\le 2\text{poids}(ACM)\le 2OPT$.

C'est l'inégalité triangulaire qui fait le pas 2, et elle seule.

3. Les mesures, sur $2000$ nuages de points tirés uniformément dans un carré, l'optimum étant calculé exactement :

L'algorithme est bien meilleur que sa garantie : $13\%$ d'écart en moyenne, jamais plus de $47\%$. C'est le sort habituel des approximations, et cela ne diminue en rien l'intérêt de la garantie — celle-ci vaut sur toute instance, y compris celles qu'on n'a pas tirées.

4. Sans l'inégalité triangulaire, tout s'effondre, et pas seulement cette approximation-là. Le pas 2 de la preuve tombe : sauter une ville peut coûter arbitrairement cher. Mais il y a bien pire — on démontre que si $\mathrm{P}\ne \mathrm{NP}$, aucun algorithme polynomial n'est une $\rho$-approximation du voyageur de commerce général, pour aucune constante $\rho$.

L'idée de cette impossibilité mérite d'être esquissée, car elle éclaire ce qu'est une approximation. Étant donné un graphe $G$ à $n$ sommets, posons $d(u,v)=1$ si $\{u,v\}$ est une arête de $G$, et $d(u,v)=\rho n+1$ sinon. Si $G$ a un cycle hamiltonien, l'optimum vaut $n$ ; sinon, il vaut au moins $\rho n+1>\rho n$. Une $\rho$-approximation distinguerait donc les deux cas, et résoudrait le problème du cycle hamiltonien, qui est np-complet.

La morale. L'inégalité triangulaire n'est pas une hypothèse technique : c'est ce qui sépare un problème approchable d'un problème qui ne l'est pas du tout. Une garantie d'approximation dépend autant du problème que de l'algorithme.