L'objectif de l'exercice est de coder une commande tps.exe qui prend un entier n en argument sur la ligne de commande pour générer aléatoirement un nuage de n points dans le plan euclidien. Ces n points P[0], P[1], ... numérotés de 0 à n-1 forme un graphe ( une clique ) pondéré par la distance euclidienne. Le poids de l'arête ij est simplement égal à la distance entre les points P[i] et P[j]. La commande utilisera l'algorithme de Kruskal pour déterminer un arbre couvrant minimal dont on peut tirer une 2-approximation de la tournée optimale en considerant le cycle des sommets obtenu par un parcours en profondeur à partir d'une racine. Le répertoire de l'examen contient un makefile et une source tsp.c qui pourront être modifiés de façon marginale. Les fichiers de définitions graphe.h, nuage.h, et kruskal.h sont imposés et ne seront pas modifiés. Les sources nuage.c et graphe.c devront être complétés. La gestion des ensembles sera codé dans les fichiers disjoint.c, disjoint.h. ======================================================================== 1. Nuage de points. ======================================================================== [a] Compléter la procédure void initnuage( int n ) pour générer un nuage de n points aléatoires dans le pavé unité i.e. les coordonnées des points sont dans l'intrervalle [0,1]. [ insérerer le code ] [b] Compléter la procédure void initcircle( int n ) pour générer un nuage de n points aléatoires sur le cercle de unité. [ insérerer le code ] ======================================================================== 2. Graphe ======================================================================== Quel choix a été fait pour représenter les graphes ? [ reponse ] ======================================================================== 2. Arbre couvrant minimal ======================================================================== Implanter l'algorithme de Kruskal pour déterminer un arbre couvrant minimal d'un nuage de point. Les opérations sur la structure d'ensembles disjoints seront codés dans les fichiers disjoint.c et disjoint.h. Le retour de la fonction : graphe kruskal( void ) est un arbre, donc un graphe d'ordre nbpoints. [ ne pas insérer de code ] [ compléter le fichier kruskal.c en l'adaptant à l'expérience numérique ] ======================================================================== 3. Cycle ======================================================================== [a] Compléter la fonction coutCycle( cycle c ) qui calcule le coût d'un cycle. [ insérer le code ] [b] Donner les cycles correspondants aux differents parcours en profondeur à partir du sommet 0 pour le graphe : 0 -- 1 / \ 2 3 -- 4 \ 5 [ réponse ] [b] Compléter la procédure cycle parcours( graphe g ) qui retourne un cycle de sommets du graphe visités à partir du sommet 0 au cours d'un parcours en profondeur. On pourra supposer le graphe connexe. [ insérer le code ] ======================================================================== 3. Mise en oeuvre ======================================================================== [ a ] Comment tester le bon fonctionnement de tsp.exe ? [ décrire la méthode ] [ b ] Quels sont les coûts des tournées pour n=10, 100, 1000. n 10 100 1000 X(n) [ compléter le tableau ] [ b ] Préciser les temps de calcul pour 4 valeurs pertinentes n . . . . T(n) [ compléter le tableau ] [ d ] Estimer le temps de calcul en fonction de n. [ expliquer ] ======================================================================== 4. Amélioration locale ======================================================================== ------A C ----- \ / \/ /\ / \ -------D B ----- [ a ] Une tournée ....AB....CD... dont les segments AB et CD se coupent peut être améliorée. Faire un schéma explicatif. [ expliquer ] [ b ] Ecrire la fonction int correction( cycle s ) pour détecter et réaliser les améliorations locales. Il s'agit de modifier la tournée tant qu'il est possible de faire une amélioration locale. [ insérer le code ] [ c ] Quels sont les coûts des tournées pour n=10, 100, 1000 après corrections. n 10 100 1000 C(n) [ compléter le tableau ] [ d ] Préciser le nombre d'itérations requis pour les corrections. n 10 100 1000 I(n) [ compléter le tableau ] ======================================================================== 4. Graphique ======================================================================== Faire une représentation graphique tour.png des fonctions : n -> X( n ) tournée de base n -> C( n ) tournée modifiée en faisant varier n par pas de 10 de 1 à 1000. [ insérer les commandes utilisées, idéalement un script bash ! ] [ ne pas effacer le fichier tour.png ]