Problème du voyageur de commerce
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 |
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.
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.).
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)]
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.