Discussion: k proches voisins

  1. #1
    Candidat au Club
    Femme Profil pro
    optimisation
    Inscrit en
    mars 2017
    Messages
    13
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France

    Informations professionnelles :
    Activité : optimisation

    Informations forums :
    Inscription : mars 2017
    Messages : 13
    Points : 4
    Points
    4

    Par défaut 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 : 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
    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 :

    Nom : z.png
Affichages : 91
Taille : 7,5 Ko

  2. #2
    Rédacteur/Modérateur

    Homme Profil pro
    Network game programmer
    Inscrit en
    juin 2010
    Messages
    4 354
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 30
    Localisation : Royaume-Uni

    Informations professionnelles :
    Activité : Network game programmer

    Informations forums :
    Inscription : juin 2010
    Messages : 4 354
    Points : 17 058
    Points
    17 058

    Par défaut

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

  3. #3
    Expert éminent
    Homme Profil pro
    Développeur informatique
    Inscrit en
    février 2005
    Messages
    4 226
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Conseil

    Informations forums :
    Inscription : février 2005
    Messages : 4 226
    Points : 9 141
    Points
    9 141

    Par défaut

    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

  4. #4
    Expert éminent sénior
    Avatar de koala01
    Homme Profil pro
    Consultant informatique
    Inscrit en
    octobre 2004
    Messages
    10 457
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : Belgique

    Informations professionnelles :
    Activité : Consultant informatique

    Informations forums :
    Inscription : octobre 2004
    Messages : 10 457
    Points : 22 639
    Points
    22 639

    Par défaut

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

    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : 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
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

  5. #5
    Candidat au Club
    Femme Profil pro
    optimisation
    Inscrit en
    mars 2017
    Messages
    13
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France

    Informations professionnelles :
    Activité : optimisation

    Informations forums :
    Inscription : mars 2017
    Messages : 13
    Points : 4
    Points
    4

    Par défaut

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

  6. #6
    Membre expérimenté
    Avatar de Pyramidev
    Homme Profil pro
    Développeur
    Inscrit en
    avril 2016
    Messages
    365
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Développeur

    Informations forums :
    Inscription : avril 2016
    Messages : 365
    Points : 1 596
    Points
    1 596

    Par défaut

    @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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    class Client
    {
    public:
    	Point getPosition() const noexcept {return m_position;}
    	// ...
    private:
    	Point m_position;
    	// ...
    };
    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
    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;
    }

  7. #7
    Expert éminent sénior
    Avatar de koala01
    Homme Profil pro
    Consultant informatique
    Inscrit en
    octobre 2004
    Messages
    10 457
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : Belgique

    Informations professionnelles :
    Activité : Consultant informatique

    Informations forums :
    Inscription : octobre 2004
    Messages : 10 457
    Points : 22 639
    Points
    22 639

    Par défaut

    Citation Envoyé par Pyramidev Voir le message
    @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
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Algorithme KD-Tree de recherche du plus proche voisin .
    Par mobi_bil dans le forum Général Algorithmique
    Réponses: 1
    Dernier message: 11/05/2014, 11h54
  2. méthode des k plus proche voisin en matlab
    Par koukitta dans le forum Images
    Réponses: 4
    Dernier message: 15/05/2009, 17h47
  3. Plus proche voisin dans un kd-tree
    Par koni33 dans le forum Général Algorithmique
    Réponses: 2
    Dernier message: 11/05/2009, 15h10
  4. Réponses: 34
    Dernier message: 26/06/2008, 17h46
  5. Réponses: 3
    Dernier message: 12/04/2007, 09h32

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo