Bonjour,
j'ai 14 et un peu de mal avec l'anglais, j'essaye de resoudre le probleme 'Closest pair of points problem' dans la metrique L1
j'ai trouvé un algorithme qui s'execute en temps raisonable sur wikipedia: https://en.wikipedia.org/wiki/Closes...points_problem mais je ne comprends pas comment cet algorithme marche et pourquoi il marche.
Merci de m'éclairer
"Brute force", il calcule la distance entre toutes(2) les paires de points possibles et retient la plus petite.Envoyé par degre2
grand P est le tableau(array) des coordonnées des points P[a1, a2, a3, ..., an] (en C, float[a1, a2, a3, ..., an]; )
length(P) est le nombre de points (la longueur du tableau)
(2) Les deux boucles for et surtout leurs limites sont le truc permettant de ne pas calculer dist(i,j) et dist(j,i) ... un petit casse tête que je te laisse déchiffrer.
La vectorielle donne dist(i,j) = la racine carrée de la somme des carrés des différences de toutes les composantes
https://www.maxicours.com/se/cours/v...e-distance-ab/ vrai aussi dans un espace à n dimensions ... à 14 ans !
Biname
Dernière modification par Biname ; 14/08/2020 à 07h08.
remarque que comme la fonction racine carrée est croissante, on peut s'en dispenser et chercher la paire de points dont le carré de la distance est le plus petit.
Alors c'était peut etre pas clair mais je dois manipuler une grande quantité de points et l'algorithme brute force est trop long, en fait je cherche a comprendre l'algorithme ci-dessous, dans la section planar case:
Sort points according to their x-coordinates
Trier les points par rapport à leur coordonnés x
Split the set of points into two equal-sized subsets by a vertical line x=xmid.
Couper le groupe en 2 selon une ligne vertical x=xmediane
Solve the problem recursively in the left and right subsets. This yields the left-side and right-side minimum distances dLmin and dRmin, respectively.
Comment suis-je sensé résoudre ce proble récursivement ?
Find the minimal distance dLRmin among the set of pairs of points in which one point lies on the left of the dividing vertical and the other point lies to the right.
Comment ?
The final answer is the minimum among dLmin, dRmin, and dLRmin.
bonjour,
je reconnais que ce n'est très explicite.
la deuxième étape me semble être d'appliquer la méthode brute à chaque moitié, ce qui est bien plus court ( en temps ) que la moitié du temps pour l'appliquer à l'ensemble.
la dernière étape est moins claire.
je suppose qu'on commence par trier les points à gauche les plus près de la médiane soit avec d < min(dLmin;dRmin)
ensuite on ne regarde que les distance entre le groupe gardé à gauche et celui à droite.
( sous toute réserve ).
Bonjour,
Il ne s'agit absolument pas d'appliquer brute force aux deux moitiés mais d'appliquer récursivement l'algorithme aux deux moitiés, comme indiqué, mais cela je suppose que vous l'aviez compris.
Le point clé est le point 4, puisque la connaissance de MinL et MinR permet de définir des valeurs à exclure facilement ...
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Correction, en C : float monTableau [P][N]; P le nombre de points et N la dimension
https://www.programiz.com/c-programm...nsional-arrays
Pour le premier algorithme, le nombre de distances à calculer et comparer est (P-1) + (P-2) + ... + 1 = P*(P-1)/2
Comme le fait remarquer Minushabens, il est inutile de calculer la racine carrée.
En utilisant un compilateur raisonnablement optimisé, une paire se calcule en moins de 50 cycles d'horloge, soit Cys = 50 (si j'osais, je dirais même 20 : increment_i, get_float, float*float = moins de 10 cycles ... et maintenant même moins de N * 10 cycles ... sauf erreur)
Le nombre total de cycles est donc N * Cys * P * (P - 1) / 2 : la ressource est, pour un coeur est égale à la fréquence du processeur
Pour N = 2, P = 10000 et Cys = 20 et f=3GHz on a t = 2 * 10000 * 99999 * 20/(2*3e9) = 4e9/6e9 = 0.666 secondes pour C/C++
Un processeur effectue une opération en virgule flottante par cycle ... dingue et bien plus pour une carte vidéo.
Sauf erreurSSSSSSSSSS
P.S. remplacer la coordonnée par son carré ferait gagner du temps
Dernière modification par Biname ; 14/08/2020 à 16h22.
Doc avec exemples, gépatoulu :
https://www.geeksforgeeks.org/closes...uer-algorithm/
