Probleme – Le voyageur de commerce : quatre niveaux d'élagage

1. L'exhaustif. On fixe la ville $0$ comme départ — cela divise déjà par $n$ le nombre de tournées, puisqu'une tournée circulaire peut être lue depuis n'importe laquelle de ses villes. Restent $(n-1)!$ ordres.

(* Longueur de la tournée minimale partant de 0. Précondition : d est une
   matrice n x n de distances positives, n >= 2. Complexité : O(n!). *)
let tsp d =
  let n = Array.length d in
  let vu = Array.make n false in
  let best = ref max_int in
  vu.(0) <- true;
  let rec explorer k courant longueur =
    if k = n then begin
      let total = longueur + d.(courant).(0) in
      if total < !best then best := total
    end else
      for s = 1 to n - 1 do
        if not vu.(s) then begin
          vu.(s) <- true;
          explorer (k + 1) s (longueur + d.(courant).(s));
          vu.(s) <- false
        end
      done
  in explorer 1 0 0; !best

2. L'abandon des branches trop longues. Les distances étant positives, la longueur d'une tournée partielle ne peut que croître : dès qu'elle atteint le record, la branche est perdue. Il suffit de garder le for sous condition :

end else if longueur < !best then
  for s = 1 to n - 1 do (* ... *) done

3. Le record amorcé et le minorant. Deux idées de plus.

Amorcer : au lieu de partir de max_int, calculer d'abord une tournée par le glouton du plus proche voisin (chapitre chap:gloutons) et en faire le record initial. L'élagage mord alors dès la première branche.

Minorer : soit $m_s$ la plus courte arête incidente au sommet $s$. Une tournée partielle finissant en $u$ avec $R$ villes restantes devra emprunter au moins une arête depuis $u$ et au moins une depuis chaque ville de $R$ : sa longueur finale vaut donc au moins $\ell +m_u+{\sum }_{s\in R}{m}_s$. Si ce minorant atteint le record, la branche est morte.

(* mini_incident.(s) = plus courte arête incidente à s, calculée une fois. *)
let coupe =
  let reste = ref mini_incident.(courant) in
  for s = 1 to n - 1 do if not vu.(s) then reste := !reste + mini_incident.(s) done;
  longueur + !reste >= !best

Le minorant doit être optimiste, c'est-à-dire ne jamais dépasser la vraie longueur restante : sinon on couperait une branche contenant l'optimum et l'on rendrait un résultat faux, sans le savoir. Ici l'argument est immédiat — on compte, pour chaque ville restante, moins que ce qu'elle coûtera.

La mesure, sur $9$ villes du plan (donc $8!=40320$ tournées). Les quatre programmes rendent la même tournée optimale, de longueur $3414$.

Trois enseignements, et le deuxième est une surprise.

D'abord, le glouton du plus proche voisin donne $4362$, soit $27,8\%$ de plus que l'optimum : vite calculé, franchement mauvais. C'est le chapitre chap:gloutons en un chiffre.

Ensuite, amorcer le record n'a rien apporté — ligne (c), identique à (b). L'exploration en profondeur trouve elle-même une bonne tournée dès sa première descente, et le record du glouton ne la précède pas d'assez pour couper quoi que ce soit. Une amélioration plausible peut ne rien donner ; c'est la mesure qui le dit, pas l'intuition.

Enfin, le minorant apporte à lui seul un facteur $13$ de plus. Il coupe non pas quand la branche est déjà perdue, mais quand elle est condamnée — bien plus haut dans l'arbre. C'est précisément la différence entre le retour sur trace et la séparation et évaluation, que le chapitre chap:probabilistes traite pour elle-même.

4. Et pour $n=30$ ? $29!$ vaut $8,8\cdot 10^{30}$ : aucun élagage constant n'y suffira. Il faut soit un minorant bien plus serré — l'arbre couvrant minimal des villes restantes, ou la relaxation continue —, soit renoncer à l'exactitude. Le problème est np-difficile (chapitre chap:decidabilite) : c'est le cas de figure annoncé à la fin de ce chapitre, et les trois issues y sont nommées.