exercice algorithme glouton : Le Problème du Voyageur de Commerce (TSP)

Le problème du voyageur de commerce (TSP - Travelling Salesperson Problem) est un problème classique d'optimisation combinatoire. Un voyageur doit visiter un ensemble de villes, en passant une fois par chaque ville, et revenir à la ville de départ. Le but est de minimiser la distance totale parcourue.

Ce problème est NP-complet, ce qui signifie qu'il n'existe pas de solution exacte efficace pour tous les cas. Par conséquent, on utilise souvent des heuristiques, comme les algorithmes gloutons, pour trouver une solution approximative.

Partie 1 : Représentation et Compréhension

1. Représentation :
   On représente le problème avec un graphe complet où :
   • Chaque ville correspond à un nœud.
   • Chaque distance entre deux villes correspond à une arête pondérée.

   Exemple : Considérez les 6 villes suivantes avec la matrice de distances donnée :

   \[ \begin{array}{c|cccccc} \text{De/Vers} & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline 1 & - & 3 & 10 & 11 & 7 & 25 \\ 2 & - & - & 6 & 12 & 8 & 26 \\ 3 & - & - & - & 9 & 4 & 20 \\ 4 & - & - & - & - & 5 & 15 \\ 5 & - & - & - & - & - & 18 \\ \end{array} \]

   Question : Représentez ce problème sous la forme d'un graphe.

Partie 2 : Algorithme Glouton

2. Règle gloutonne :
   Un algorithme glouton pour résoudre le TSP fonctionne en choisissant à chaque étape :
   • L'arête disponible de poids minimal,
   • Tout en respectant les deux contraintes :
     1. Ne pas former de cycle prématuré avant d'avoir inclus toutes les villes.
     2. Ne pas dépasser 2 arêtes incidentes par nœud.

   Question : Appliquez cet algorithme pour le graphe donné et indiquez :

   • Les étapes de construction du circuit.
   • La longueur totale du circuit obtenu.
3. Analyse de l'algorithme :

   Question : Que se passe-t-il si le graphe est incomplet (c'est-à-dire qu'il n'y a pas de chemins directs entre certaines villes) ? Expliquez avec un exemple.

Partie 3 : Optimisation

4. Utilisation de la distance euclidienne :
   Supposons que les distances suivent la condition triangulaire (matrice euclidienne) : \[ \text{distance}(i, j) \leq \text{distance}(i, k) + \text{distance}(k, j). \]

   Question : Prouvez qu’il peut être avantageux de repasser par une ville déjà visitée dans certains cas.

5. Heuristique basée sur un arbre couvrant minimal :
   Une approche heuristique pour résoudre le TSP consiste à :
   • Construire un arbre couvrant minimal (MST) pour les villes.
   • Utiliser cet arbre pour approximer le circuit.

   Question : Implémentez cette méthode sur l'exemple donné. Calculez la longueur totale et comparez-la avec celle de l'algorithme glouton.

Partie 4 : Variantes

6. Matrice non symétrique :
   Dans certains cas, les distances ne sont pas symétriques (ex. : distance de \( i \) à \( j \) différente de celle de \( j \) à \( i \)).

   Question : Proposez une version modifiée de l'algorithme glouton pour gérer ce cas.

7. Graphes orientés :
   Un graphe est dit Hamiltonien s'il existe un chemin qui passe exactement une fois par chaque nœud.

   Question : Donnez un algorithme pour vérifier si un graphe donné a un chemin Hamiltonien.