[Algorithme] Correspondance de points
Bonjour à tous,
Je suis à la recherche d'un algorithme (normal vous me direz vu où l'on se trouve dans le forum ...). Je vous explique ce que je cherche :
Soit deux ensembles E1 et E2. La taille de ces ensembles pouvant être différente. Les éléments de E1 et E2 étant des points (une valeur X et une valeur Y).
Ce que je cherche à faire c'est, dans la mesure du possible pour tous les éléments de E1, trouver l'élément de E2 le plus proche (pour le calcul de la distance on pourra simplifier par distance(), peut importe ma méthode). Sachant que un élément de E2 ne peut être associé qu'à 0 ou 1 élément de E1.
Pour le moment je fais ça :
Bon ... c'est l'algo que j'utilise (après évidemment je ne l'ai pas implémenté tel quel ... mais le principe est le même derrière).
Code : Sélectionner tout - Visualiser dans une fenêtre à part
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34// Calcul des distances Pour tout e1 élément de E1 faire Pour tout e2 élément de E2 faire dist[e1,e2] = distance(e1,e2) Fin pour Fin pour associe = 0 // Traitement de la matrice Tant que (associe < size(E1) && associe < size(E2)) faire valeur = MAX e1c = NULL e2c = NULL // Recherche de la valeur minimum dans notre table de distance Pour tout e1 de E1 faire Pour tout e2 de E2 faire si dist[e1,e2] < valeur alors valeur = dist[e1,e2] e1c = e1 e2c = e2 Fin si Fin pour Fin pour Traitement(e1c,e2c) // Suppression des distances correspondantes à e2c Pour tout e1 élement de E1 faire dist[e1,e2c] = MAX Fin pour // Suppression des distances correspondantes à e1c Pour tout e2 élément de E2 faire dist[e1c,e2] = MAX Fin pour incrémente associe Fin tant que
Que pouvez-vous me proposer de plus disons ... performant et peut-être même plus intelligent.
Je dis intelligent car, admettons la matrice de distance suivante :
---------E11-|--E12--|--E13--|-E14
E21-|--- 3 ---|---2---|---12--|--1
E22-|--- 7 ---|---7---|---8 --|--8
E23-|--- 9 ---|---4---|---4 --|--5
E24-|--- 7 ---|---11--|---11--|--3
E25-|--- 6 ---|---8---|---12--|--4
E26-|---10---|---3---|---9 --|--1
L'algorithme que je donne va donner les appels suivants :
Traitement(E14,E21)
Traitement(E12,E26)
Traitement(E13,E23)
Traitement(E11,E25)
Alors qu'une réorganisation des éléments dans les ensembles aurait donnée un autre résultat (ceci à cause des valeurs égales en fait).
Donc : comment améliorer cet algorithme ? Tant en terme de performance que d'un point de vue ... précision si je puis dire.
Concernant la performance, sachez juste que, la manière dont j'ai codé l'algorithme, distance n'est qu'un simple tableau à une dimension ... Je le parcours avec seulement une boucle for (pour la recherche du minimum).
Voilà, j'espère avoir été plus ou moins clair. Si vous avez besoin de plus d'informations, surtout N'HESITEZ PAS à me le dire ... Je détaillerai plus ou je ré-expliquerai les choses différemment ou je ne sais quoi
Merci de m'avoir lu et de votre éventuelle réponse
Bonne journée
Répondre avec citation
)
Partager