Discussion :

[sophielow]

Bonjour

SVP aidez moi
je veux appliquer l'algorithme du plus proche voisin et je veux savoir comment utiliser la fonction "nearestNeighbor" pour mon cas.
supposons qu'on a la matrice de distances symétrique

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

d=[0 3 5 7 1;3 0 4 2 5;5 4 0 6 1;7 2 6 0 7;1 5 1 7 0]

on va commencer par le premier noeud représenté par la première ligne et on détermine le noeud le plus proche qui est dans notre cas le noeud 5 ; puis à l'étape suivante on commence par le noeud 5 (ligne 5) et on cherche la distance la plus proche pour le noeud 5 sans revenir aux noeuds choisis précédemment qui est dans notre cas 3 et ainsi de suite jusqu'à obtenir un vecteur ligne qui est dans notre cas : 1-5-3-2-4

[Antoane]

Bonjour,

Une méthode "sans trop réfléchir" de faire le classement serait exactement comme on le ferait à la main :
- avec une boucle for k=1:[nombre de nœuds]-1, on peut créer un vecteur (noté par exemple sortedNodes) contenant les indices des nœuds rangés dans l'ordre de parcours;
- sortedNodes(1) est initialisé à 1, puisque c'est celui choisi comme point de départ ;
- à chaque itération on cherche le nœud sortedNodes(k+1) le plus proche du nœud sortedNodes(k) ;
- pour éviter de repasser deux fois sur le même nœud, il suffit de mettre sa distance aux autres comme valant "inf".

Il existe sans doute des méthodes plus intelligentes, voire une fonction dédiée, mais je ne vois pas.

[sophielow]

Merci beaucoup pour votre réponse, j'ai commence à suivre ces étapes juste j'ai rencontré un petit problème, veuillez SVP m'aidez à le résoudre.

En fait, j'ai pu avoir une matrice triée par ordre croissant des distances et puis avoir les indices, cette matrice des indices est par exemple comme suit:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
ind=[1     2     5     6     8     7     4     3
     2     6     1     5     7     3     8     4
     3     7     2     6     1     5     8     4
     4     8     5     1     6     2     7     3
     5     6     1     2     8     4     7     3
     6     2     5     1     7     3     8     4
     7     3     2     1     6     5     8     4
     8     4     1     5     2     6     7     3

obtenue en utilisant: la fonction

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

[v, ind]=sort (d,2)

Par suite je pourrai avoir comme résultat la 2 eme colonne, mais on doit pas avoir un noeud répété, exemple ici on a le 5 eme élément "noeud 6" est déjà répété, dans ce cas on doit le remplacer par le 5eme élément de la colonne suivante qui est ici " noeud1" et si cet élément est répété aussi, on passe à prendre le 5ème élément de la colonne suivante et ainsi de suite. SVP je veux savoir comment peut on faire ce remplacement des éléments sachant que le résultat que je cherche par cet exemple en faisant exécution à la main est le vecteur: [2 6 7 8 1 5 3 4]


Merci beaucoup d'avance

[Antoane]

Bonjour,

Utiliser la 2e colonne de cette matrice ind n'est pas correct. Comme tu l'as noté, cela ne peut pas fonctionner puisque certains noeuds y peuvent y être cités plusieurs fois, ou aucune.
Le k^ième élément de la 2e colonne de cette matrice ind est le noeud le plus proche du noeud n°k. L'ordre des éléments n'est donc intéressant que si tu cherchais à lister :
- quel est le noeud le plus proche du premier ;
- puis quel est le noeud le plus proche du second ;
- puis quel est le noeud le plus proche du troisième...
Il n'y a pas la notion de parcours en allant au plus court dont tu parlais au début.


Je ne sais pas si mon premier message n'étais pas clair ou si tu as choisis d'aller dans une autre direction, mais ce n'est pas ce que je conseillais.

[sophielow]

Merci beaucoup pour votre réponse

D'après l'exemple de matrice que j'ai noté, les noeuds sont sur les lignes, on a fait un tri par ordre croissant des distances, la matrice ind indique les indices; on va pas considérer la première colonne vu que ca représente les "0" du diagonale, donc on doit considérer la 2 eme colonne. On a par exemple le noeud le plus proche du noeud 1 est le noeud 2, le noeud le plus proche du noeud 2 est le noeud 6 et ainsi de suite, mais on cas dé répétition de noeud le plus proche la solution sera non réalisable comme c'est le cas du noeud 5 où on a trouvé le noeud 6 le plus proche qui est déjà répété. Dans ce cas, on doit considérer l'élément associé au noeud 5 (ligne 5) mais dans la colonne suivante qui est ici 1 donc on choisi 1 tant que ce noeud n'est pas choisi précédemment avec les 4 premiers noeuds.

Je souhaite que mon idée est claire, juste j'ai voulu savoir comment faire le remplissage du vecteur résultat par l'élément du colonne suivante en cas de répétition.

[Antoane]

Bonjour,
Avec un peu de délai : ce que je proposais :

Une méthode "sans trop réfléchir" de faire le classement serait exactement comme on le ferait à la main :
- avec une boucle for k=1:[nombre de nœuds]-1, on peut créer un vecteur (noté par exemple sortedNodes) contenant les indices des nœuds rangés dans l'ordre de parcours;
- sortedNodes(1) est initialisé à 1, puisque c'est celui choisi comme point de départ ;
- à chaque itération on cherche le nœud sortedNodes(k+1) le plus proche du nœud sortedNodes(k) ;
- pour éviter de repasser deux fois sur le même nœud, il suffit de mettre sa distance aux autres comme valant "inf".

se coderait:

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
 
clear 
d=[0 3 5 7 1;3 0 4 2 5;5 4 0 6 1;7 2 6 0 7;1 5 1 7 0]
 
d_mod = d ; % copy the input matrix so that it can be modified.
sortedNodes = nan * d(1,:) ; % initialise output vector to default values
sortedNodes(1) = 1 ; % the first node to be visited is node n°1
for k=1:length(sortedNodes)-1 % for each folowing node
    currentDistances = d_mod(sortedNodes(k),:) ; % vector of the distances between the current node and the others
    currentDistances(sortedNodes(k)) = inf ; % make sure that the closest node to the current one is not the current node itself
    [~, index] = min(currentDistances) ;
    sortedNodes(k+1) = index ; % save in sortedNodes the index of the next node to visit
    d_mod(:,sortedNodes(k)) = inf ; % set all the distances between the next node 
end
 
sortedNodes % output vector

Je ne suis pas sûr qu'il y ait une méthode simple de répondre au problème (ou en tout cas, je ne vois pas de telle méthode) en passant par la fonction "sort".

[sophielow]

Merci beaucoup Antoane

[sophielow]

Bonjour Antoane

Je veux développer l'idée un peu et je veux chercher le plus proche voisin pour un nombre T=4 de matrices (cellmatrix). J'ai appliqué le code que vous avez proposé sur chaque matrice indépendamment en effectuant

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
d_mod = d{t} ; % copy the input matrix so that it can be modified.
sortedNodes = nan * d{t}(1,:) ; % initialise output vector to default values
sortedNodes(1) = 1 ; % the first node to be visited is node n°1
for k=1:length(sortedNodes)-1 % for each folowing node
    currentDistances = d_mod(sortedNodes(k),:) ; % vector of the distances between the current node and the others
    currentDistances(sortedNodes(k)) = inf ; % make sure that the closest node to the current one is not the current node itself
    [~, index] = min(currentDistances) ;
    sortedNodes(k+1) = index ; % save in sortedNodes the index of the next node to visit
    d_mod(:,sortedNodes(k)) = inf ; % set all the distances between the next node 
end
 
sortedNodes % output vector

Puis, et pour avoir tous les vecteurs ensemble dont chacun est associé à une matrice, J'ai ajouté une boucle for en faisant quelques modifications, mais je trouve toujours des erreurs.
SVP Antoane, si possible aidez moi pour avoir la solution voulu

Merci infiniment

[Antoane]

Bonjour,

- Exécute le programme ligne à ligne pour voir ce qui fonctionne et si les variables prennent les valeurs attendues ;
- Lis et comprend les messages d'erreur renvoyés par matlab, ils sont généralement relativement clairs et instructifs.