TD 5 : cycles et voyageur de commerce

Exercice 1

1. Une première version naïve consiste à utiliser un algorithme de type force brute. On part d'un sommet, puis on essaie chacun des $n-1$ sommets suivants possibles, et ainsi de suite. Cela nous donne $n!$ possibilités, soit une complexité factorielle. Pour mettre en œuvre cet algorithme, il faut un moyen de générer les permutations : l'algorithme de Heap itératif est utilisable.

// Pour la version itérative, on simule le processus récursif en mémorisant les indices de boucle dans un tableau compteur.
// compteur[k] représente, dans cette simulation, l'indice courant dans la boucle de Heap(k,A).

Heap_iteratif(n : entier, A : tableau) :

    compteur := tableau de n entiers, initialisés à 0

    écrire A

    // i indique le niveau de la boucle en cours d'incrémentation
    i := 0;

    Tant que i < n :

        Si  compteur[i] < i :
            Si i est pair :
                échanger A[0] et A[i]
            Sinon :
                échanger A[compteur[i]], A[i]
            Fin Si
            écrire A

            compteur[i] += 1 // on incrémente l'indice de boucle après avoir effectué une itération
            i := 0 // on retourne au cas de base de la version récursive

        Sinon :
            // la boucle de niveau i est terminée, on peut donc réinitialiser l'indice et retourner au niveau supérieur
            compteur[i] := 0
            i += 1

        Fin Si

    Fin Tant que

2. On peut appliquer la programmation dynamique pour diminuer la complexité. L'idée est de considérer les sous-ensembles de sommets : pour chaque sous-ensemble $S$ et chaque sommet $v$ de $S$, on détermine s'il existe une chaîne couvrant exactement les sommets de $S$ et se terminant en $v$, à partir des résultats obtenus pour $S \setminus \{v\}$. La complexité devient $O(n^2 \, 2^n)$.

Exercice 2

Nous pouvons utiliser le cours et le théorème de Dirac pour le montrer.

Théorème de Dirac : un graphe simple à $n$ sommets (avec $n \geq 3$) dont chaque sommet est au moins de degré $\dfrac{n}{2}$ est hamiltonien.

Pour rappel, un graphe complet est un graphe simple dont tous les sommets sont adjacents deux à deux. Chaque sommet a donc un degré $n-1 \geq n/2$ dès que $n \geq 2$. Ainsi, tout graphe complet à au moins 3 sommets est hamiltonien.

Exercice 3

Comme dans l'exercice 1, où nous avons distingué deux méthodes pour déterminer si un graphe est hamiltonien, nous pouvons distinguer deux méthodes exactes pour résoudre le problème du voyageur de commerce. Dans un premier temps, nous pouvons utiliser un pseudo-code naïf. Cet algorithme a une complexité en $O(n!)$ ; plus précisément, il n'y a que $(n-1)!/2$ tournées distinctes (départ fixé, coûts symétriques) si l'on pense à ne pas recalculer ce que l'on a déjà calculé. On admet qu'il existe une fonction permutation permettant de fournir la permutation suivante d'un vecteur s'il en existe une, et zéro si elles ont toutes déjà été données.

Entrée : N vecteur des villes 1..n-1 (la ville 0 est le point de départ)
         et une fonction de coût c(i,j)
Sortie : coût minimal et tournée correspondante
cout_min = +∞
meilleure = aucune
tant que permutation(N) != 0
    poids = 0
    k = 0
    pour i allant de 0 à n-2
        poids += c(k, N[i])
        k = N[i]
    poids += c(k, 0)
    si poids < cout_min
        cout_min = poids
        meilleure = copie de N
retourner cout_min et meilleure

Un autre algorithme pouvant être mis en place est un algorithme de programmation dynamique (algorithme de Held-Karp). Pour comprendre comment cela est possible, il faut écrire l'équation de récurrence qui permet de choisir une ville. Soit un ensemble de villes à visiter $C$. On note $chemin(C,j)$ le coût minimal d'un chemin partant de la ville de départ $x$, traversant toutes les villes de $C$ et se terminant par la ville $j \in C$. On a :

$$chemin(C,j)=\min\{chemin(C\backslash\{j\},k)+c(k,j) \; \text{avec} \; k \in C \backslash \{j\}\}, \qquad chemin(\{j\},j) = c(x,j)$$

À partir de cela, en notant $N$ l'ensemble des villes privé du point de départ $x$, le coût optimal du problème vaut :

$$solution = \min_{j \in N}\{chemin(N,j)+c(j,x)\}$$

L'équation récursive peut être utilisée pour construire les valeurs $chemin(C,j)$ pour tous les $C\subseteq N$ et $j \in C$, en parcourant les ensembles à deux éléments, puis les ensembles à trois éléments, etc., jusqu'à obtenir l'ensemble $N$. Nous pouvons ensuite calculer $solution$. Enfin, on reconstruit la tournée à rebours, en trouvant une ville $v_{n-1}$ telle que $chemin(N,v_{n-1})+c(v_{n-1},x)=solution$, puis une ville $v_{n-2}$, etc.

Entrée : un ensemble de villes V, un point de départ v et un tableau c(i,j)
         donnant le coût pour aller de la ville i à la ville j
Sortie : les prédécesseurs permettant de reconstruire un chemin de coût minimal
Data[] = +∞
Path[]
pour tout w dans V \ {v}
  Data({w},w) = c(v,w)
  Path({w},w) = v
pour tout i allant de 2 à n-1
  pour tout S inclus dans V \ {v} tel que |S| = i
    pour tout w dans S
      pour tout u dans S \ {w}
        z = Data(S\{w},u) + c(u,w)
        si z < Data(S,w)
          Data(S,w) = z
          Path(S,w) = u
retourner Path

La complexité de cet algorithme est en $O(n^2 \, 2^n)$.

Exercice 4

On se place dans le cas où les coûts vérifient l'inégalité triangulaire (par exemple des distances) : $c(u,v)\leq c(u,w)+c(w,v)$.

Entrée : G=(V,E) un graphe complet et c(i,j) une fonction donnant le coût entre les villes i et j
Sortie : un cycle hamiltonien de coût au plus deux fois l'optimum
Choisir un sommet r dans V comme ville initiale
Construire un arbre couvrant minimal T de G (algorithme de Prim depuis r, ou de Kruskal)
Retourner le cycle hamiltonien H qui visite les sommets dans l'ordre préfixe d'un parcours en profondeur de T depuis r

On veut maintenant prouver que l'algorithme est un algorithme d'approximation de facteur 2. On note $C^\ast$ la tournée optimale et $H$ la tournée renvoyée. On cherche donc à montrer que $c(H)\leq2 c(C^\ast)$.

• Soit $T$ l'arbre couvrant minimal. En retirant une arête de $C^\ast$, on obtient une chaîne qui couvre tous les sommets, donc un arbre couvrant : $c(T)\leq c(C^\ast)$.
• Soit $P$ le parcours complet de $T$ (chaque arête parcourue à l'aller et au retour) : $c(P)=2c(T)$.
• $H$ s'obtient à partir de $P$ en sautant les sommets déjà visités. Grâce à l'inégalité triangulaire, remplacer un détour $u \rightarrow w \rightarrow v$ par l'arête $u \rightarrow v$ n'augmente pas le coût (facilement mis en évidence avec un arbre à 3 sommets).

Ainsi $c(H)\leq c(P) = 2c(T) \leq 2 c(C^\ast)$. L'algorithme est donc un algorithme d'approximation de facteur 2.