Graphe - Cycle et voyageur de commerce

Exercice 1

1. Une première version naïve serait d'utiliser un algortihme de type brute force. On part des $n$ sommets et à chaque itération on appelle l'algorithme sur les $n-1$ arêtes possibles etc. Cela nous donne $n!$ possibilités, soit la pire complexité possible. Pour résoudre 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 tenter de diminuer la complexité. L'idée est de décomposer le graphe en des sous ensemble de sommet, pour chaque sous ensemble $S$ on vérifie pour chaque sommet $u$ de chaque sous ensemble s'il existe une chaine couvrant les sommets de $S$ et se terminant en $v$

Exercice 2

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

Théorème de Dirac : Un graphe à $n$ sommets (avec $n>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 à donc un degrés de $n-1 > n/2$ pour $n>3$. Ainsi tout graphe complet est hamiltonien.

Exercice 3

Comme dans l'exercice 1 nous avons discriminé deux méthodes pour déterminer si un cycle est hamiltonien nous pouvons aussi discriminer deux méthodes exactes pour résoudre le problème du voyageur de commerce. Dans un premier temps nous pouvons utilser un pseudo code naïf. Cet algorithme à une complexité de O(n!), plus précisément (n-1)!/2 si on pense à ne pas recalculer ce que l'on a déjà calculé. On admet qu'il existe une fonction permutation permettant de fournir une permuttation d'un vecteur si il en existe une, zéro si elle ont toutes déjà été donnée.

Entrée : N vecteur de villes de taille n et une liste de coûts c(i,j)
Sortie : Liste de villes et coût total
Cout=0 //Cout total du chemin
ordre_permutation=0 //permet de retrouver le numéro de permutation pour retrouver la permutation
pour i allant de 0 à n
  tant que permutation(N)!=0
    poids_chemin_courant=0
    k=0
    pour i allant de 0 à n
      poids_chemin_courant=c(k,N[i])
      k=N[i]
    poid_chemin_courant+=c(k,0)
    cout=min(cout,poids_chemin_courant)
    ordre_permutation+=1;
retourner cout et ordre_permutation

Un autre algorithme pouvant être mis en place est un algorithme de programmation dynamique, pour comprendre comment cela est possible il faut réecrire l'équation de récurrence qui nous permet de choisir une ville. Soit un ensemble de ville à visiter $C$. On note $chemin(C,i)$ le chemin optimisé traversant toutes les villes de $C$ se terminant par la ville $i$ et que nous voulons trouver la meilleur ville $j$ suivante nous devons trouver

\begin{equation} chemin(C,j)=\min\{chemin(C\backslash\{j\},k)+c(k,j) \; \text{avec} \; k \in C\}\end{equation}

A partir de cela nous pouvons remarquer une autre conséquence de la construction du problème en effet le coût optimal pour résoudre le problème consiste désormais à trouver la valeur de, notant $N$ l'ensemble des villes privées du point de départ

\begin{equation}solution = \min\{chemin(N,j)+c(j,x)\}\end{equation}

A partir de ces valeurs l'équation récursive peut être utilisée pour construire les valeurs $chemin(N,j)$ pour tous les $C\subseteq N$ et $j \in S$, en parcourant l'ensemble à deux éléments, puis des ensemble à trois éléments etc jusqu'à obtenir un ensemble à $n$ éléments. Nous pouvons ensuite calculer $solution$ grâce à ce procédé. Ensuite nous pouvons dérouler l'algorithme en trouvant une ville $v_{n-1}$ telle que $chemin(N,v_{n-1})+c(v_{n-1})=solution$, puis identifier une ville $v_{n-2}$ etc

Entrée : Un ensemble de ville V, un point de départ v et un tableau c(i,j) permettant de donner le coup de la ville i à j
Sortie : Un chemin de coût minimal
Data[]=infty
Path[]
pour tout w dans V
  Data({w},w)=c(v,w)
  P({w},w)=v
pour tout i allant de 2 à n
  pour tout S inclus dans V tel que |S|=i
    pour tout w dans S
      pour tout u dans S
        z=Data(S\{w},u)+c(u,w)
        si z<Data(S,w)
          D(S,w)=z
          Path(S,w)=u
retourner Path

La complexité de ce problème est en O(n^2 2^n)

Exercice 4

On se place dans le cas où les coûts sont des déplacements et donc $c(u,v)=c(u,w)+c(w,v)$

Entrée : G=(V,E) un graphe complet et c(i,j) une fonction donnant le coup entre les villes i et j
Sortie : un chemin de coût minimal
Choisir un sommet r dans V comme ville initiale
Construire un arbre couvrant minimal T dans G à partir de r via l'algorithme de Krustal
Retourner le cycle hamiltonien H qui visite les sommets dans l'ordre trouvé par l'algorithme de Krustal

On veut maintenant prouver que l'algorithme est un algorithme d'approximation de facteur 2. On note $C^\ast$ la tournée optimale et $C$ la tournée courante. On cherche donc à montrer que $c(C)\leq2 c(C^\ast)$. Soit $T$ l'arbre couvrant minimal, on a $c(T)\leq c(C^\ast)$ (puisque C est construit avec l'algorithme de Krustal, C privé de l'arète qui forme le cycle est un arbre). Si l'on note $P$ la liste formé par le parcours de $T$ on obtient $c(P)=2c(T)$ car chaque arête est visitée deux fois. On remarque que l'on peut supprimer un sommet de $P$ (facilement mis en évidence avec un arbre à 3 sommets). Ainsi $c(P)\leq 2c(C^\ast)$ et donc $c(C)\leq c(P) \leq 2 c(C^\ast)$. L'algorithme est donc un algorithme d'approximation de facteur 2.