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 :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
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
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).

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