#include "pppp.h" // // PPPP - Paire de Points les Plus Proches // // Chacun des trois algorithmes doit renvoyer le couple {i,j} d' ** // indices ** des deux points les plus proches. Voir pppp.h pour // une description plus fine. Pour pppp_divide(), c'est la partie // récursive pppp_rec() que vous devez programmer. // // -> la structure "point" est définie dans "tools.h" // -> la structure "couple" est définie dans "pppp.h" // // // Extensions/optimisations à tester (une fois que vous avez bien // avancé): // // Pour pppp_rec(): // // . Pour la recherche du min dans Sy, au lieu de mettre "j <= i+7", // utilisez "Sy[j].y - Sy[i].y < delta", ce qui va générer moins de // tests. Optimisez encore le test avec "Sy[j].y < d" en posant d = // delta + Sy[i].y. // // . L'algorithme du cours suppose qu'il n'y a qu'un seul point // d'abscisse x*, l'abscisse du médian. Contournez ce problème pour // qu'il fonctionne sans cette hypothèse. Pour cela, il faut (1) // utiliser le même test de comparaison en x pour le tri de Vx[] et // le remplissage de Ay[] afin de garantir |Ax| = |Ay|; et (2) que // ce test de comparaison en x soit un ordre total, c'est-à-dire ne // donne 0 que si (x,y) = (x',y'), et pas seulement si x = x'. // // Pour pppp_random(): // // . Il est possible de maintenir l'indice du dernier échec, disons tf // (initialisée à -1), de sorte que les instructions 3b et 3c // doivent être exécutée seulement si t>tf. Faire attention, lors // d'un échec, de bien chercher le point q le plus proche dans le // voisinage, sinon il y aura des échecs plusieurs fois au même // indice. // // . Optimisez le nombre de cellules voisines en passant de 25 à 21 // cellules à explorez. Comparez. // // NB. Pour comparer plusieurs versions, ajouter une autre fonction à // pppp.c, disons pppp_random_v2(), et mettez à jour pppp.h et // tsp_main.c en ajoutant une ligne. couple pppp_naive(point* V,int n){ couple result = {-1,-1}; ; ; ; return result; } // Fonction de comparaison des ordonnées pour qsort(): // renvoie -1 si y(A)y(B) et 0 sinon. int fcmp_y(const void *A, const void *B) { ; ; ; return 0; } // Fonction de comparaison pour des abscisses qsort(): // renvoie -1 si x(A)x(B) et 0 sinon. int fcmp_x(const void *A, const void *B) { ; ; ; return 0; } // paire de points pour pppp_rec() typedef struct{ point P1,P2; } ppoints; // Cette fonction doit, comme dans l'algorithme du cours, renvoyer la // paire de points les plus proche pris dans l'ensemble Vx[] (type // "ppoints"), et non pas les indices des points les plus proches // (type "couple"). La récurrence est plus simple ainsi. C'est // pppp_divide() déjà programmée qui se chargera de retrouver les // indices dans V[] des deux points en question. // // Point de vigilance. Le choix du médian, celui de rang ceil(n/2), // est important pour que la séparation en A et B donne deux ensembles // d'au moins 2 points. Il se trouve aussi que ceil(n/2) = // floor((n+1)/2) = (int)(n+1)/2. Les points ayant des indices // commençant à 0, il faut donc prendre le bon indice. // ppoints pppp_rec(point* Vx,point* Vy,int n){ ppoints Q = {Vx[0],Vx[0]}; ; ; ; return Q; } couple pppp_divide(point* V,int n){ // Vx[] = V[] trié selon x point *Vx = malloc(n*sizeof(*Vx)); memcpy(Vx,V,n*sizeof(*V)); qsort(Vx,n,sizeof(point),fcmp_x); // Vy[] = V[] trié selon y point *Vy = malloc(n*sizeof(*Vy)); memcpy(Vy,V,n*sizeof(*V)); qsort(Vy,n,sizeof(point),fcmp_y); // Q = {P1,P2} = paire de points les plus proches ppoints Q = pppp_rec(Vx,Vy,n); free(Vx); free(Vy); // cherche dans V[] les indices des deux points de Q couple result = {-1,-1}; for(int i=0; i N définit pour tout couple d'entiers (i,j) un entier // unique. Il faut i,j >= 0. Il correspond à la somme des longueurs // des diagonales montantes de la forme (t,0) -> (0,t), partant de // (0,0), et jusqu'à atteindre le point (i,j) sans le compter. La // longueur de la diagonale est le nombre de points quelle // contient. Cf. le TD. // // | | | | | | // 4 .-.-.-.-.-.- // | | | | | | // 3 o-.-.-.-.-.- // |\| | | | | // 2 o-o-.-.-.-.- // |\|\| | | | // j = 1 o-o-o-X-.-.- Ex: map(i,j) = map(3,1) = (#o) = 11 // |\|\|\|\| | // 0 o-o-o-o-o-.- // 0 1 2 3 4 5 // i // int map(int i,int j){ ; ; ; return 0; } // Point de vigilance. Attention à ce que les cellules voisines // tombent dans le premier quadrant (i,j >= 0), sinon map(i,j) ne // marchera pas. couple pppp_random(point* V,int n){ couple result = {-1,-1}; ; ; ; return result; }