- Un contenant les sources du programme que vous avez réalisé
- Un rapport (5 pages maximum au format pdf). Vous expliquerez dans ce rapport comment sont implantées les différentes fonctions, leurs spécifications (ainsi que les spécifications de toutes les fonctions intermédiaires que vous aurez implanté) et comment vous les avez validées. Vous ajouterez aussi dans ce rapport les points qui vous ont paru les plus difficiles à gérer et le temps que vous avez passé sur ce projet (rédaction du rapport compris).
| Groupe | Heure de passage |
|---|---|
| Rotolo - Vial - Sadick | 8h30 |
| Bolbènes - Courtier | 8h40 |
| Santin - Mauriello | 8h50 |
| Combe - Grégoire | 9h00 |
| Potelberg - Dos Santos Pedro | 9h10 |
| Grange - Deffaugt | 9h20 |
| Monachon | 9h30 |
| Segura - Tlemcan | 9h40 |
| El Kbabty - Chareyre | 9h50 |
| Antwan | 10h00 |
| Lurol-Suder - Ouchane | 10h10 |
| Mottet | 10h20 |
-
Pour toute question n'hésitez pas à me contacter par mail.
- Ordonner toutes les arrêtes d'un graphe par ordre de poids croissant
- Prendre dans la liste des arrêtes ordonnées des arrêtes jusqu'à que le graphe de départ soit couvert et que chaque nouvelle arrête ne crée pas de cycle.
- On choisit (C,D) - OK
- On choisit (E,D) - OK
- On choisit (E,C) - Pas OK car il y a un cycle
- On choisit (C,B) - OK
- On choisit (A,B) - OK l'agorithme termine car on a couvert tous les sommets.
1 - Présentation du problème
1.1 - Le problème du voyageur de commerce
En informatique, le problème du voyageur de commerce, ou problème du commis voyageur, est un problème d'optimisation qui, étant donné une liste de villes, et des distances entre toutes les paires de villes, détermine un plus court chemin qui visite chaque ville une et une seule fois et qui termine dans la ville de départ.Malgré la simplicité de son énoncé, il s'agit d'un problème d'optimisation pour lequel on ne connait pas d'algorithme permettant de trouver une solution exacte rapidement (c'est à dire en un temps polynomial en le nombre de villes) dans tous les cas.
1.2 - Traduction mathématique du problème du voyageur de commerce
De manière plus formelle le problème se présente de la manière suivante : on cherche un circuit dans un graphe, dont les arrêtes sont pondérées, qui passe par tous les sommets une fois et une seule (sauf le sommet de départ qui est aussi le sommet d'arrivée). Il faut minimiser le poids total du circuit.Un graphe est un couple (S,A) de sommets et d'arrêtes. Une arrêtes est une partie de AxA. On associe à chaque arrête un poids. Ainsi pour notre problème les sommets sont des villes, et les arrêtes les routes reliant ses villes entre elles (le poids est la distance entre les villes). Comme toutes les villes sont reliées à toutes les villes on peut faire n'importe quel circuit. C'est à dire que pour n villes il y (n-1)! circuit possibles (en partant de la ville 1 on a n-1 choix puis n-2 etc.).
1.3 - Une solution approchée
L'algorithme de Christofides est basé sur un algorithme simple d'approximation de facteur 2 (ce qui signifie qu'il donne une solution qui est au pire deux fois plus longue que la solution optimale) qui utilise la notion d'arbre couvrant de poids minimal. Comme toute tournée a un poids cumulé supérieur à celui de l'arbre couvrant minimal et comme un parcours préfixe de l'arbre passe deux fois par chacun des nœuds internes une tournée qui suit un parcours préfixe a un poids cumulé inférieur au double de la solution minimale au problème du voyageur de commerce. Il reste à convertir ce parcours en un parcours qui passe une fois et une seule par chacun des sommets du graphes. On exploite alors l'inégalité triangulaire : si entre deux sommets le parcours considéré fait passer par un sommet intermédiaire déjà visité, on le saute pour passer directement au premier sommet non encore visité. L'inégalité triangulaire assure alors que le poids total du trajet n'augmente pas ; par conséquent on obtient un circuit hamiltonien dont le poids est inférieur au double de celui du circuit minimal.1.4 - Arbre couvrant de poids minimal
Un arbre couvrant de poids minimal d'un graphe dont les arrêtes sont pondérées est un arbre qui contient tout les sommets du graphe qu'il doit couvrir et tel que la somme du poids de ses arrêtes soit minimal. Un exemple d'arbre couvrant minimal est le suivant (l'arbre est représenté avec les arrêtes en gras):
Ce problème est beaucoup plus simple à résoudre que celui du voyageur de commerce. Un algorithme pour résoudre ce problème fonctionne de la manière suivante:
La première étape consiste à ranger les arrêtes par ordre croissant. Cela donne:
L'éxécution pas à pas de l'algorithme donne:
2 - Structure de données en Ocaml
2.1 - Les graphes pondérés
On représentera les graphes pondérés par des listes de triplets contenant les deux sommets et le poids. Les sommets seront définis comme un type énuméré. Ainsi pour représenter le graphe pris en exemple précédemment:
type sommets_exemple = A | B | C | D | E;;On peut remarquer qu'il n'est pas nécessaire de représenter l'arrête (B,A,9) car implicitement les arrêtes sont symétriques. Attention cependant quand vous éxécutez le programme à bien prendre en compte ce fait (notamment quand vous récupérez les arrêtes une par une pour constituter l'arbre couvrant).type 'a graphe = ('a*'a*int) list;;
let graphe_exemple : sommets_exemple graphe = [(A,B,9);(A,E,10);(B,C,6);(A,C,12);(B,E,11);(C,E,5);(C,D,3);(E,D,4)]
2.2 - Les arbres couvrants
Vous utiliserez un type d'arbres qui sera différent de ceux vus cours pour représenter l'arbre couvrant de poids minimal. Le type des arbres sera donnés par~:type 'a arbre = Noeud of 'a * (('a arbre) list ) | Vide;;Dans l'exemple traité plus haut cela donnera une structure du type (on peut choisir la racine arbitrairement ce qui donne plusieurs choix):
Noeud(C,[Noeud(D,[Noeud(E,[Vide])]); Noeud(B,[Noeud(A,[Vide])]) ]);;Un parcours préfixe de cet arbre donne la liste [C;D;E;B;A] ce qui donne le circuit [C;D;E;B;A;C] qui est un circuit répondant à la question du voyageur de commerce avec pour poids total de 39. Il y a un circuit moins lourd [D;C;B;A;E;D] dont le poids est 36.