k proches voisins

Salut,

Quelqu'un me propose une idée ou s'il y a une faute la corrige svp, je cherche pour chaque client ses k voisins dans l'ordre croissant des distances. Voici le code :

Code:

---

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 35 36

for (int s = 0; s < n; s++) { cout << "pour le client " << s << " " << "ses voisins dans l'ordre croissant des distances : " << endl; for (int b = 1; b < n; b++) { for (int w = 0; w < n; w++) if (w != s) //il ne faut pas comparer le client avec lui meme { for (int i = 1; i <= b; i++) if (vect[s][i] != w) // il faut que w n'existe pas dans les voisins déja trouvés , vect stocke pour le client s ts ses voisins possibles for (int m = w + 1; m < n; m++) if (s != m) for (int i = 1; i <= b; i++) if (vect[s][i] != m) if (dis[s][w] < dis[s][m]) { if (dis[s][w] < distance) { voi = w; //voi: variable qui stocke a chaque comparaison en parcourant ts les autres clients le meilleur trouvé distance = dis[s][w]; } } //distance variable initialisé a un trés grand nombre et dis[s][w] distance entre deux clients else if (dis[s][w] > dis[s][m]) { if (dis[s][m] < distance) { voi = m; distance = dis[s][m];   } } vect[s][b] = voi; } cout << vect[s][b] << endl; } }

---

mais voilà ce qu'il maffiche :

Pièce jointe 255878

Je vais peut-être dire une connerie mais... std::stable_sort ? non ? :roll:
Ce code est bien trop compliqué, sans compter qu'on ne connait aucune des variables ni leur type pour que je le lise.

Comme pour @Bousk, code trop compliqué pour ce qu'il a à faire.
Arrêtez d'utiliser ces putains de tableau à la C en C++.
En C++ donc les algorithmes de la STL et pas avec des cochonneries du C, c'est truc qui se règle en quelques lignes.
http://www.cplusplus.com/reference/algorithm/
http://www.cplusplus.com/reference/v...tor/?kw=vector

Salut,

Comme tous les autres, je ne sais pas quel types de données tu envisages de manipuler. Mais, de manière générale, je te dirais que chaque notion qui apparait dans tes besoins (dont nous ne savons absolument rien) devrait apparaitre sous une forme ou une autre dans ton code.

Ainsi, les notions qui correspondent dans tes besoins à des noms ("voisin", "distance","client") devrait être représentés par des types de données que tu pourras manipuler, et celles qui correspondent à des verbes ("trier", calculerDistance, ....) devraient correspondre à des fonctions.

Etant donné que tu semble vouloir calculer la distance qui sépare deux clients, j'en déduis qu'il nous faudra la notion de... position; la distance séparant deux client étant le résultat d'un calcul basé sur la position de chacun de ces client.

Pour faire simple, je vais considérer que la position correspond à l’abscisse et à l'ordonnée d'un rérérentiel à deux dimensions, c'est à dire à une structure proche de

Code:

---

1 2 3 4

struct Position{ double positionX; double positionY; };

---

Comme chaque client devrait pouvoir être identifié de manière unique, et qu'il se trouve forcément à une position donnée, nous pourrions envisager de représenter cette notion sous une forme qui serait sans doute proche de

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

class Client{ public: Client(size_t id, double x, double y):id_{id},pos_{x,y}{} /* il faut pouvoir récupérer l'identifiant */ size_t id() const{ return id_; } /* il faut pouvoir récupérer sa position */ Position const & position() const{ return pos_; } private: size_t id_; Position pos_; };

---

La disance qui sépare deux position peut sans doute être calculée de manière assez simple, sous une forme qui serait sans doute proche de

Code:

---

1 2 3 4 5 6 7 8 9

double claculerDistance(Position const & a, Position const & b){ auto minx = std::min(a.x,b.x); auto miny = std::min(a.y, b.y); auto maxx = std::max(a.x,b.x); auto maxy = std::max(a.y,b.y); auto distx = maxx - minx; auto disty = maxy - minx; return sqrt( distx * distx + disty * disty); }

---

Enfin, la notion de voisin devrait mettre en relation deux identifiants de clients et la distance qui les sépare. Comme nous allons chercher les voisins d'un client donné, nous pourrions sans doute définir cette notion sous une forme proche de

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

class Voisin{ public: Voisin(Client const & c1, Client const & c2): id_{c2.id()}, dist_{calculerDistance(c1.positon(), c2.position()}{} size_t id() const{ return id_; } double distance() const{ return dist_; } private: size_t id_; double dist_; };

---

A partir de là, nous avons les données de base qui vont être manipulées, mais, comme le "voisin d'un client" correspond à ... un autre client, il semble évident que nous devrons disposer... d'une liste de clients car, si nous n'avions qu'un seul client, il n'aurait forcément aucun voisin :P

Le plus simple, pour représenter "cette liste de clients" est (dans l'état actuel des choses) de la représenter sous la forme d'un tableau de client. Ce serait quelque de proche de

Code:

---

1 2 3 4 5 6 7

int main(){ std::vector<Client> clients; /* nous pouvons ajouter un client sous la forme de */ clients.push_back(Client{1,23.555,45.6666}; clients.push_back(Client{2,6.021548,3.1415926}; }

---

(En réalité, nous devrions sans doute créer une abstraction supplémentaire, je serait-ce que pour nous permettre de nous assurer que chaque client créé est identifiable de manière strictement unique ;) )

Et, bien sur, pour chaque client, nous voudrons connaitre la liste de ses voisins. Nous pourrions vouloir obtenir cette liste triée selon deux critères différents : par ordre d'identifiant et par distance.

L'idéal est donc sans doute de créer une abstraction représentant cette notion qui prendrait sans doute la forme de

Code:

---

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 35 36 37 38 39

class ListeVoisi{ public: ListeVoisins(Client const & cli):cli_{cli}{} /* il est toujours sympa de pouvoir récupérer l'identifiant du client   * dont on a la liste de voisins sous les yeux   */ size_t id() const{ return cli_.id(); } /* nous voulons pouvoir ajouter un voisin à la liste */ void ajouteVoisin(Client const &){ /* idéalement, il faudrait s'assurer que chaque voisin est unique */ voisin_.push_back(Voisin{cli_,voisin}); } /* nous souhaitons pouvoir trier la liste en fonction de l'identifiant du voisin */ void parIdentifiant(){ std::stable_sort(voisins_.begin(),voisins_.end(), [](Voisin const & a, Voisin const & b){ return a.id() <b.id(); }); } /* nous souhaitons aussi pouvoir trier la liste en fonction de la distance (du plus proche au plus éloigné */ void parDistance(){ std::stable_sort(voisins_.begin(),voisin_.end(), [](Voisin const & a, Voisin const & b){ return a.distance() <b.distance(); }); } /* nous voulons pouvoir accéder aux voisins : il nous faut un itérateur et les fonctions bebin et end   */ using const_iterator = typename std::vector<Voisin>::const_iterator; const_iterator begin() const{ return voisins_.begin(); } const_iterator end() const{ return voisins_.end(); } private: Client const & cli_; std::vector<Voisin> voisins_; };

---

Et, bien sur, nous souhaitons disposer de la liste de tous les voisins de chaque client (de préférence, triée par client concerné).

Le plus facile est sans doute d'avoir recours à une std::map dont la clé correspond à l'identifiant correspondant au client et dont la valeur correspond à la liste de voisins du client en question. C'est à dire, sous une forme qui serait sans doute proche de

Code:

---

std::map<size_t, ListeVoisins> mapVoisins;

---

(encore une fois, il serait sans doute intéressant de créer une abstraction représentant cette notion, mais bon, on va rester simple ;) ).
Nous pourrions remplire cette map sous une forme qui serait sans doute proche de

Code:

---

1 2 3 4

/* pour chaque client, on crée une liste de voisins vide */ for(auto const & it : clients){ mapVoisin.insert(std::make_pair(it.id(),ListeVoisins{it}); }

---

puis nous pourrions créer les "relations de voisinage" sous une forme qui serait proche de

Code:

---

1 2 3 4 5 6 7 8 9 10

/* pour chaque liste de voisin, on rajoute tous les clients */ for(auto it : mapVoisins){ for(auto const & c : client){ /* sauf qu'un client n'est jamais son propre voisin */ if(c.id()!=it->first){ it->second.ajouteVoisin(c); } } }

---

Une fois que les listes de voisins sont remplies, les traiter très facilement, par exemple, en affichant la liste de tous les voisins triée sur base de la distance pour un client donné, sous une forme proche de

Code:

---

1 2 3 4 5 6 7 8 9 10

auto & it = mapVoisin.find(id); /* si on n'a pas notre client, c'est une erreur de logique qui doit être corrigée */ assert(it!= mapVoisins.end() && "client non trouvé"); /* on trie ses voisins par distance it->second.parDistance(); /* et on les affiche */ std::cout<<"Les voisin de "<<it->first<<" par ordre de distance :\n"; for(auto const & v : it->second){ std::cout<<v.id()<<" distance :"<<v.distance(); }

---

Serait-ce quelque chose dans ce genre là que tu cherches à faire :question:

merci beaucoup Kouala , normallement c ça ce que je cherche :love:
je v testé et voir les resultats , merci autre fois

@koala01 :
Ok pour la structure Position et la classe Client.
Mais les classes Voisin et ListeVoisi me semblent assez lourdes. En plus, il y a un objet ListeVoisi par client. Personnellement, j'aurais concentré le rôle de ces deux classes dans une seule classe ListeClients.

Ce à quoi ressemblerait mon code :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class Point { public: constexpr Point(double x, double y) noexcept : m_x(x), m_y(y) {} //! \remark Optimisé pour trier les distances euclidiennes car pas d'appel à sqrt. constexpr double distanceCarre(Point autre) const noexcept { const double diff_x = autre.m_x - m_x; const double diff_y = autre.m_y - m_y; return diff_x*diff_x + diff_y*diff_y; } // ... private: double m_x, m_y; };

---

Code:

---

1 2 3 4 5 6 7 8 9

class Client { public: Point getPosition() const noexcept {return m_position;} // ... private: Point m_position; // ... };

---

Code:

---

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 35 36 37 38 39 40

class ListeClients { public: const Client& getClient(IdClient idClient) const; std::vector<IdClient> getVoisinsDuPlusProcheAuPlusLoin(IdClient idClient) const; // ... private: double distanceCarre(IdClient idX, IdClient idY) const; std::map<IdClient, const Client*> m_clients; // ... };   double ListeClients::distanceCarre(IdClient idX, IdClient idY) const { //! \todo Mettre le résultat en cache pour optimiser ? const Client& clientX = getClient(idX); const Client& clientY = getClient(idY); const Point positionX = clientX.getPosition(); const Point positionY = clientY.getPosition(); return positionX.distanceCarre(positionY); }   std::vector<IdClient> ListeClients::getVoisinsDuPlusProcheAuPlusLoin(IdClient idClient) const { std::vector<IdClient> result; const size_t nbClients = m_clients.size(); if(nbClients > 0) result.reserve(nbClients-1); for(auto paire_id_client : m_clients) { const IdClient idVoisin = paire_id_client.first; if(idVoisin != idClient) result.push_back(idVoisin); } std::stable_sort(result.begin(), result.end(), [=,idClient](IdClient idX, IdClient idY) { return distanceCarre(idClient, idX) < distanceCarre(idClient, idY); } ); return result; }

---

Citation:

---

Envoyé par Pyramidev

@koala01 :
Ok pour la structure Position et la classe Client.
Mais les classes Voisins et ListeVoisi me semblent assez lourdes. En plus, il y a un objet ListeVoisi par client. Personnellement, j'aurais concentré le rôle de ces deux classes dans une seule classe ListeClients.

---

On eut pu, dans le sens où tous les voisins (d'un client donné) sont ... des clients.

Cependant, cela aurait été en désaccord profond avec le SRP, car une liste de clients se serait retrouvé face à la triple responsabilité :

• maintenir la liste des clients
• maintenir, pour chaque client, la liste de ses voisins
• de maintenir le mapping entre tous les client et leurs voisins respectifs.

En séparant clairement les trois notions dont il est question ici (liste de clients, liste des voisins d'un client particulier, "mapping" entre un client donné et sa liste de voisins), il devient possible de les rendre beaucoup plus indépendantes (même si, en l'espèce, il faudrait sans doute remplacer la référence constante sur le client par "autre chose" au niveau de la liste de voisins), et donc de pouvoir les utilisées séparément (par exemple : ne pas avoir à se coltiner la liste des voisins si tout ce dont on a besoin, c'est de la liste des clients ... ou inversement).

Nous aurions d'ailleurs pu envisager de rendre chaque client responsable de sa liste de voisin, mais nous aurions alors du veiller à ce que l'ajout d'un client au niveau de la liste des clients provoque l'ajout de ce client au niveau de la liste des voisins de tous les autres, responsabilité qui ne semble clairement pas échoir à une "liste de clients".

Bien sur, la séparation des trois notions va sans doute rapidement poser des problèmes de synchronicité, dans le sens où -- comme je viens de le dire -- l'ajout d'un client devrait provoquer l'ajout de ce client dans la liste des voisins de tous les autres en plus de rajouter tous les clients existants comme voisin du nouveau client. Mais il semblerait "logique" que cette responsabilité échoie au final à la notion de "mapping" entre les clients et leurs listes de voisins, quitte à avoir recours à un système de signaux (émis par la liste de clients) et de slot (agissant au niveau de la notion de mapping) afin de s'assurer que la synchronisation se fasse ;)

Et c'est d'autant plus vrai qu'il est désormais très facile de mettre sur pied un système de signaux / slots (guère plus de 150 lignes de code en C++11), sans nécessiter le recours à une bibliothèque externe ;)