Discussion :

[MrPchoun]

Bonjour à tous, à toutes, la forme ?

Alors voilà, j'ai un petit problème.. Je bosse en ce moment sur les graphes et sur les recherches de meilleur chemin. De tels algorithmes imposent très souvent de tenir une liste rangée ( en l'occurrence, une map ) de points, de telle sorte que le premier point de la dite liste soit celui qui satisfait le plus possible telle ou telle exigence.

Dans mon exemple, j'utilise une map de <points,char>, et je voudrais que le premier élément de la liste soit celui dont la clé ( le point ) est le plus proche du point d'arrivée.

En fait j'y suis déjà arrivé, le problème vient quand deux points sont équidistants ( me sortez pas vos histoire d'équidistant avec le dragon, je vois déjà venir les fans de kaamelott ) équidistants, disais-je, du point d'arrivée. En fait, lorsqu'un nouveau point est ajouté à la liste et qu'il est aussi loin du point d'arrivée que ne l'est déjà un autre point de la liste, le nouveau point remplace le précédent, dans sa position dans la map ( ce qui ne me dérange pas ) et dans sa clé/valeur ( ce qui me dérange beaucoup plus ! ). Voyez plutôt :

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
#include <SFML/Graphics.hpp>
#include <map>
#include <iostream>
#include <cmath>
 
/* Que ceci n'effraie pas certains : un sf::Vector2i est exactement la même chose qu'un std::pair<int,int>, à ceci près que ses deux "pairs" sont accessibles par des .x et .y, au lieu de .first et .second */
typedef sf::Vector2i Point;
 
Point start(5,6), goal(16,6);
 
// Le comparateur de map..
class comp 
{
public:
    bool operator()(const Point X,const Point Y) 
    { 
        // si X est sctrictement plus proche de goal que ne l'est Y, on renvoie TRUE. Sinon, on renvoie FALSE.
        return sqrtf((goal.x-X.x)*(goal.x-X.x)+(goal.y-X.y)*(goal.y-X.y)) < sqrtf((goal.x-Y.x)*(goal.x-Y.x)+(goal.y-Y.y)*(goal.y-Y.y));
    }
};
 
int main()
{
    std::map<Point,char,comp> map;
 
    Point a(5,7), b(10,3), c(15,5), d(17,5);
 
    map[d]='d';
    map[a]='a';
    map[c]='c';
    map[b]='b';
 
    map.erase(map.begin()->first);
 
    std::cout<<"point le plus proche : "<<map.begin()->second;
 
    return 0;
}

Ici, c est aussi loin de goal que d. Problème : lorsque j'ajoute c à la map, après d donc, il remplace d par c. Conséquence : lorsque je supprime c, le premier élément n'est plus d mais b. Comment faire pour que tel ne soit pas le cas ? J'ai bien essayé de remplacer < par <= dans le comparateur mais il semblerait que ne soit pas la bonne solution..

Des idées ?

Mr Pchoun !

[Invité]

salut,

je reproduis pas le probleme avec

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
41
42
#include <map>
#include <iostream>
#include <cmath>
 
/* Que ceci n'effraie pas certains : un sf::Vector2i est exactement la même chose qu'un std::pair<int,int>, à ceci près que ses deux "pairs" sont accessibles par des .x et .y, au lieu de .first et .second */
class Point{
	public:
	int x;
	int y;
  Point(int ax, int ay):x(ax),y(ay){};
};
 
Point start(5,6), goal(16,6);
 
// Le comparateur de map..
class comp 
{
public:
    bool operator()(const Point X,const Point Y) 
    { 
        // si X est sctrictement plus proche de goal que ne l'est Y, on renvoie TRUE. Sinon, on renvoie FALSE.
        return sqrtf((goal.x-X.x)*(goal.x-X.x)+(goal.y-X.y)*(goal.y-X.y)) < sqrtf((goal.x-Y.x)*(goal.x-Y.x)+(goal.y-Y.y)*(goal.y-Y.y));
    }
};
 
int main()
{
    std::map<Point,char,comp> map;
 
    Point a(5,7), b(10,3), c(15,5), d(17,5);
 
    map[d]='d';
    map[a]='a';
    map[c]='c';
    map[b]='b';
 
    map.erase(map.begin()->first);
 	std::cout<<"map size: " <<map.size()<<std::endl;
    std::cout<<"point le plus proche : "<<map.begin()->second<<std::endl;
 
    return 0;
}

(idem d est le premier elem et ma map contient 4 elements)

En revanche, Je subodore que dans ton cas, l elem d est remplacé par l elem c (idem ta map ne contient que trois elements et non 4).
Dans l'idée, je connais pas l'algorithme mais j'intuite que si (X,Y)==false, on tente (Y,X)==false, si c'est le cas, X==Y et donc on ignore (ou remplace) X par Y. De fait, il suffit de dire que
operator(X,Y):
si d(X,goal)<d(Y,goal) return true
sinon si d(X,goal)==d(Y,goal) return X.x<Y.x;
d() etant loperateur distance sqrtf( etc.. )

[MrPchoun]

Bonjour galerien69, tu es de Lyon ? J'y habite aussi

Pourrais tu me dire ce que tu as en sortie, avec ton code ? Moi j'obtiens 2 pour la taille de la map, et le meilleur point est b. Ce qu'il faudrait, c'est que la taille de la map soit ramenée à 3, et que le meilleur point soit d.

Je ne suis pas sûr que ta solution soit la bonne : Il ne s'agit pas d'ignorer un point s'il est égal à un autre. Je viens en revanche d'utiliser l'opérateur <=, au lieu de <. Verdict : le meilleur point est d, c n'est plus placé avant lui. Cela ne me dérange pas. La taille de la map, après ajout des quatres points, est de 4. Aucun problème. En revanche, quand il s'agit de supprimer le meilleur point ( le premier, donc), c'est le drame, il est perdu.

Voici l'erreur : malloc: *** error for object 0x7fff5fbff350: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug

Problème de désallocation mémoire ? Mon avis, c'est qu'il utilise aussi l'opérateur de comparaison lors de la suppression d'un élément : il supprime l'élément dont le point est à telle distance de goal. Du coup il sait pas quoi faire quand il y a deux éléments.. Je me trompe ?

Je pense néanmoins que la piste du <= est à approfondir, qu'en penses tu ? Ai-je été plus clair dans ce deuxième message ?

Merci de ton soutien dans cette épreuve difficile

MrPchoun

[koala01]

Salut,

Tu viens de te heurter de plein fouet à une des restriction de la classe std::map: les clé sont forcément uniques.

Dés lors, il y a deux solutions:

1. Soit tu modifies ta logique pour t'assurer que la comparaison assure une "unicité référentielle"
2. Soit tu choisi une autre collection pour maintenir tes différents éléments

La première solution ne sera possible que si tu as la certitude qu'un point donné (par exemple : x= 4, y= 5) ne peut exister qu'une et une seule fois, mais pourrait ressembler à quelque chose comme

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
class comp 
{
public:
    bool operator()(const Point X,const Point Y) 
    { 
        //vérifions d'abord si X est strictement plus proche que Y
        bool nearest=sqrtf((goal.x-X.x)*(goal.x-X.x)+(goal.y-X.y)*(goal.y-X.y)) < 
                     sqrtf((goal.x-Y.x)*(goal.x-Y.x)+(goal.y-Y.y)*(goal.y-Y.y));
       if(nearest)
           return true;
       // vérifion ensuite si Y est strictement plus proche que X
       bool farther=sqrtf((goal.x-X.x)*(goal.x-X.x)+(goal.y-X.y)*(goal.y-X.y)) > 
                    sqrtf((goal.x-Y.x)*(goal.x-Y.x)+(goal.y-Y.y)*(goal.y-Y.y));
       if(farther)
           return false;
       /*si on arrive ici (que X n'est pas plus proche que Y et que Y n'est pas
        * plus proche que X), X et Y sont "équidistants"...
        * on peut estimer que celui dont le membre x aura la valeur la plus proche de goal.x
        * est le plus proche et que si cette différence est égale (on est alors
        * dans un cadre proche de X.x = 4, X.x = 5, Y.x=4 Y.y=-5), alors
        * c'est celui don la valeur de y a la plus petit distance par rapport à 
        * la valeur de goal.x
        */
        return (X.x - goal.x) < (Y.x - goal.x) ||
               ( (x.x - goal.x)==(Y.x - goal.x) && (X.y-goal.y < Y.y - goal.y));
    }
};

Évidemment, cela ne fonctionnera comme je te l'ai dit plus haut que si tu a la certitude qu'il n'y aura jamais qu'un et un seul point pour une coordonnée particulière.

Si tu es dans une situation dans laquelle il est possible qu'un seul et meme point (par exemple x=4, y=5) soit utilisé pour différents caractères, il faudra choisir une collection plus souple comme std::multimap par exemple

[MrPchoun]

Bonjour koala01,

Eh bien effectivement, ton code me donne les bons résultats. Si je ne m'abuse, c'est la traduction de la solution de galerien69. Je ne comprends pas que ça marche en fait, même si je suis ravi que ça avance un peu

Je comprends un bout de mon erreur, tout de même : ce qui n'allait pas, c'est que si (X,Y)==false, Y n'était pas forcément plus proche de goal que X, il pouvait aussi être à la même distance de goal que X.

Pour moi, le problème n'était pas le comparateur, mais plutôt la manière dont la map supprime ses élements. Je vais reprendre tout ça à plat, merci à vous deux !

Edit : Aucun danger, il n'y aura jamais deux clés identiques dans l'utilisation que je ferai de cette map. C'est pour ça que je n'avais pas pensé à imaginer ce cas là.

MrPchoun

[koala01]

Bonjour koala01,

Eh bien effectivement, ton code me donne les bons résultats. Si je ne m'abuse, c'est la traduction de la solution de galerien69. Je ne comprends pas que ça marche en fait, même si je suis ravi que ça avance un peu

En fait, ce n'est rien d'autre que de la géométrie appliquée.

Tu te souviens sans doute de ton cours de base qui dit que le plus court chemin entre deux point est toujours la ligne droite.

Et, tu l'auras sans doute remarqué, si on dispose de deux point (Pt1 et Pt2), et que l'on fait en sorte de tracer une ligne horizontale depuis l'un des points et verticale depuis l'autre, elle finiront, fatalement, par se croiser à angle droit en un troisième point (mettons Pt3).

Les coordonnées de ce troisième point correspondent, pour l'abscisse, à l'abscisse du point au départ duquel tu as tracé la ligne verticale et pour l'ordonnée à l'ordonnée du point au départ duquel tu as tracé la ligne horizontale

autrement dit Pt3.x est égal à Pt1.x et Pt3.y est égal à Pt2.y

Tu te retrouveras donc avec un triangle rectangle dont le coté [Pt1, Pt2] correspond à l'hypoténuse et dont les cotés [Pt1, Pt3] et [Pt2, Pt3] correspondent aux deux coté de l'angle droit.

Comme ce sont deux cotés du triangle (et en plus de l'angle droit), il est facile d'en calculer la longueur (nommons les L1 et L2), qui correspond à la valeur absolue de Pt1.y - Pt3.y pour le premier(L1) et à la valeur absolue de Pt2.x - Pt3.x pour le deuxième coté (L2).

Il n'y a donc "plus qu'à" appliquer le théorème de Pythagore qui dit que, dans tout triangle rectangle, le carré de l’hypoténuse est égal à la somme des carrés des deux autre cotés.

Autrement dit, la taille du coté [pt1, pt2](nommons la L3) est égal à la racine carrée de la somme du carré de L1 et du carré de L2.

En C++, on peut donc calculer cette distance sous la forme de

Code :

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

L3 = sqrt( (L1*L1) + (L2*L2));

Seulement, voilà...

Etant donné que l'un des points est fixe, dans l'espace (c'est le point que tu as nommé goal), cette distance correspond au rayon d'un cercle que tu pourrais tracer autour du point fixe et dont tous les points se retrouveraient à cette distance.

Mon code commence donc par vérifier si la distance entre le premier point fourni en paramètre et le point central (nommons la D1) est plus petite que la distance entre le deuxième point fourni en paramètre et le point central (nommons la D2).

Si c'est le cas, on n'a aucun problème: le foncteur peut renvoyer true sans se poser de question.

Mais si ce n'est pas le cas, il y a encore deux solutions à envisager:

1. le fait que D1 peut etre plus grand que D2 d'une part
2. Le fait que D1 peut etre égale à D2 d'autre part

(pour rappel si a n'est pas plus petit que b, alors c'est que a est plus grand ou égal à b)

Dans le premier cas, il n'y a pas de problème non plus D1 n'est, définitivement pas plus petite que D2 (normal: elle est plus grande ), et le foncteur peut donc renvoyer false sans se poser plus de question.

Par contre, si D1 n'est pas plus petit que D2 et que D1 n'est pas plus grand que D2, c'est que D1 est... égal à D2, et là, il faut commencer à réfléchir un tout petit peu.

En effet, si l'on considère que le point central est à la coordonnée 0,0, il y a quatre points qui peuvent se trouver à la même distance de ce point tout en se trouvant à une distance identique en terme d'abscisse et d'ordonnée.

Ce sont respectivement les point se trouvant au coordonnées (x,y), (-x,y), (-x,-y) et (x, -y).

On va donc "simplement" se donner l'occasion de "prioriser" les points les uns par rapport aux autres.

Je viens de dire que si l'on considère le point central comme étant le point (0,0). Mais il y a très peu de chances que ce soit le cas.

Par contre, si on soustrait la valeur de l'abscisse du point central aux valeurs des abscisse des deux points à comparer, cela correspondra à nous donner une valeur signée correspondant à la distance horizontale du point par rapport à notre point central, autrement dit, à un abscisse relatif par rapport à notre point centrale.

Et, bien sur, si l'on fait pareil avec l'ordonnée, nous obtiendrons l'ordonnée relative par rapport à notre point central.

Cela signifie que les quatre valeurs possibles sont x et -x pour l'abscisse et y et - y pour l'ordonnée.

On commence donc par vérifier si l'abscisse relatif du premier point est plus petit que l'abscisse relatif du deuxième point.

C'est ce qui correspond, dans mon code, à (X.x - goal.x) < (Y.x - goal.x)Comme cette expression est suivie d'un OU logique, si le résultat est vrai, l'autre expression ne sera pas évaluée, car on peut d'office renvoyer vrai.

Par contre, si cette expression n'est pas vraie, le second opérande du OU logique sera évalué (car il peut lui aussi renvoyer vrai) et qui correspond dans mon code à ( (x.x - goal.x)==(Y.x - goal.x) && (X.y-goal.y < Y.y - goal.y)).
Tu remarqueras qu'il y a deux expressions séparée par un ET logique dans cet opérande.

Le ET logique a la particularité de ne renvoyer "vrai" QUE si les deux expressions sont vraies.

La première va vérifier que l'abscisse relatif du premier point est bien égal à celui du deuxième point.

Si ce n'est pas le cas, on va donc renvoyer "faux" et tout le monde sera content.

Par contre, si l'abscisse relatif du premier point est égal à celui du second, il faudra évaluer la dernière expression, qui remportera la décision.

Cette expression vérifiera si l'ordonnée relative du premier point est plus petite que celle du deuxième.

Si c'est le cas, la valeur renvoyée sera true (autrement dit "on peut effectivement considérer que le premier point et plus petit que le second"), et, sinon, la valeur renvoyée sera false (autrement dit "on ne peut pas considérer que le premier point est plus petit que le second").

Ainsi, si on obtient des abscisse relatifs de 3 et -3 et des ordonnées relatives de 4 et -4 (tiens, au fait, tu as remarqué 3+4=5, enfin, si tu appliques Pythagore ) le point (-3,-4) sera considéré comme étant plus petit que le point (-3,4) qui sera lui-même considéré comme plus petit que le point (3,-4) qui sera lui meme considéré comme plus petit que le point (3, 4) et nous aurons donc la certitude, pour autant qu'il n'y ait jamais deux points représentant exactement les même coordonnées (en valeur réelle), seront définitivement considérés comme différents.

Je comprends un bout de mon erreur, tout de même : ce qui n'allait pas, c'est que si (X,Y)==false, Y n'était pas forcément plus proche de goal que X, il pouvait aussi être à la même distance de goal que X.

Exactement.

Il faut toujours veiller à ce que tes comparateurs "simples" (comprend: plus petit, plus grand, égal) renvoient un état unique : true si c'est vérifié, false si ca ne l'est pas.

Seulement, lorsque tu décide de comparer plusieurs valeurs, il y a toujours un moment (lorsque les premières valeurs respectives sont égale) où l'on pourrait croire que c'est faux alors que c'est vrai

Pour moi, le problème n'était pas le comparateur, mais plutôt la manière dont la map supprime ses élements. Je vais reprendre tout ça à plat, merci à vous deux !

La map ne supprime pas des éléments, la map remplace des éléments.
Le problème, c'est que la map compare les clés par équivalence, et non par égalité.

Elle se base en effet sur le principe que si a n'est pas plus petit que b et que b n'est pas plus petit que a, alors, c'est que a est équivalent à b.

Si tu te trompes dans la logique du comparateur qui est sensé ne renvoyer vrai que si (et seulement si) la première clé est plus petite que la seconde, tout le chateau de carte s'écroule

Edit : Aucun danger, il n'y aura jamais deux clés identiques dans l'utilisation que je ferai de cette map. C'est pour ça que je n'avais pas pensé à imaginer ce cas là.

Pas de problème pour moi...

Mais ce qui t'a trompé, c'est que tu as une belle quantité de point qui peuvent être à une abscisse identique, bien qu'étant à une ordonnée différente, et qu'il fallait prendre ce "cas particulier" (si l'on peut s'exprimer ainsi) en compte

[MrPchoun]

Salut koala,

J'ai pris une feuille, un stylo, et j'ai fini par comprendre tout ce que tu as écris

Si j'ai bien compris :

- Lorsque la distance X-goal et Y-goal est la même, on est obligé de calculer de façon arbitraire quel point doit être considéré comme plus proche ( ici, tu le fais en comparant les abscisses relatives, et si elles sont égales, les ordonnées relatives ).
- D'une façon plus générale, si les clés des deux éléments à comparer ne donnent pas assez d'information pour distinguer les deux éléments, on est obligé de prendre d'autres paramètres en compte ? Par exemple, pour une map<int,char>, si je mets dans mon comparateur quelque chose du genre :

Si premierÉlément == deuxièmeÉlément
   renvoyer true

ou même

Si premierÉlément == deuxièmeÉlément
   renvoyer false

Ça ne sera pas bon..

En revanche, si je mets quelque chose dans ce gout là :

Si premierÉlément == deuxième Élément
   Si il fait beau dehors
       renvoyer true
   Sinon
       renvoyer false

Là ce sera bon ?

En fait j'avoue que j'ai un peu du mal avec les comparateurs de map, pour moi c'est un peu magique. J'ai une question subsidiaire : comment ça se passe dans la map, quand on ajoute un élément ? l'élément ajouté est-il comparé à chaque élément de la map ou juste à un point particulier de la map ?

Merci encore de ta précieuse explication, c'est cool de prendre du temps pour les autres comme ça =)

MrPchoun

[koala01]

Salut koala,

J'ai pris une feuille, un stylo, et j'ai fini par comprendre tout ce que tu as écris

Si j'ai bien compris :

- Lorsque la distance X-goal et Y-goal est la même, on est obligé de calculer de façon arbitraire quel point doit être considéré comme plus proche ( ici, tu le fais en comparant les abscisses relatives, et si elles sont égales, les ordonnées relatives ).
- D'une façon plus générale, si les clés des deux éléments à comparer ne donnent pas assez d'information pour distinguer les deux éléments, on est obligé de prendre d'autres paramètres en compte ?

C'est bien ca.

Par exemple, pour une map<int,char>, si je mets dans mon comparateur qqch du genre :

Si premierÉlément == deuxièmeÉlément
   renvoyer true

ou même

Si premierÉlément == deuxièmeÉlément
   renvoyer false

Ça ne sera pas bon..

Jusqu'ici, c'est bon, mais

En revanche, si je mets quelque chose dans ce gout là :

Si premierÉlément == deuxième Élément
   Si il fait beau dehors
       renvoyer true
   Sinon
       renvoyer false

Là ce sera bon ?

non, car le comparateur doit renvoyer une réponse qui puisse être assimilée à "est plus petit que"

En fait j'avoue que j'ai un peu du mal avec les comparateurs de map, pour moi c'est un peu magique. J'ai une question subsidiaire : comment ça se passe dans la map, quand on ajoute un élément ? l'élément ajouté est-il comparé à chaque élément de la map ou juste à un point particulier de la map ?

En fait, la map utilise ce que l'on appelle un "arbre binaire", ce qui permet d'effectuer les comparaison de manière dite "dichotomique".

C'est à dire que, chaque fois que l'on se rend compte que l'on n'est pas sur l'élément recherché, on écarte la moitié des possibilités restantes.

Cela permet d'effectuer une recherche avec une complexité en O(log(n)) ou n est le nombre d'éléments contenus dans la map.

Ainsi, il ne te faudrait que 8 comparaisons pour sélectionner un élément parmi 255, 16 comparaisons pour en sélectionner un parmi 65535 et 32 pour en sélectionner un parmi 4 294 967 295.

L'idée est que chaque élément peut etre "relié" à deux autres éléments : un qui sera considéré comme "plus petit" que l'élément actuel et l'autre qui sera considéré comme "plus grand" que l'élément actuel.

Si l'on doit ajouter un élément (ou si on recherche un élément) qui est plus petit que l'élément actuel, on va voir du coté "plus petit", et si on doit ajouter (ou si on recherche) un élément qui est plus grand que l'élément actuel, on va voir du coté "plus grand", et ainsi de suite jusqu'à ce qu'on arrive soit sur l'élément recherché, soit sur une branche qui n'est reliée à aucun élément.

En cas d'ajout, il y a ensuite une étape d'équilibrage qui aura pour objectif de s'assurer que la différence entre la "profondeur" (comprends: le nombre d'élément que tu peux parcourir au départ d'une branche) de la branche de gauche de l'élément et celle de la branche de droite de l'élément n'est pas supérieure à un, afin d'éviter de transformer l'arbre binaire en liste chainée (en cas d'insertion d'éléments déjà fortement triés)

Lors de la sélection d'un élément, il suffit de disposer de la possibilité de savoir si un élément est plus petit que l'autre.

En effet, si l'élément recherché est plus petit que l'élément actuel, on peut aller dans la branche "plus petit", et si l'élément actuel est plus petit que l'élément recherché, on peut aller dans la branche "plus grand".

Enfin, si l'élément recherché n'est pas plus petit que l'élément actuel, et que l'élément actuel n'est pas plus petit que l'élément recherché, on considère que l'élément actuel est l'élément recherché. C'est ce qu'on appelle une équivalence, car, si la manière de comparer les éléments n'est pas suffisamment précise, on peut en arriver à se trouver dans une situation dans laquelle deux éléments pourtant différents seraient considérés par l'algorithme comme identiques.

C'est ce qui se passe lorsque ta logique est simplement fausse (par exemple, en ne comparant que l'abscisse, sans prendre en compte le fait que deux éléments comportant le même abscisse ne sont peut etre pas sur la même ordonnée) ou lorsque ta logique n'est pas assez restrictive (par exemple, lorsque tu te contente de calculer la distance entre deux points)

Nota: je me suis rendu compte que j'ai un peu simplifié le nombre de possibilités de points équidistant dans mon intervention précédente, car, tout en gardant des valeurs de 3 (-3) et 4 (-4), il y a aussi tous les points pour lesquels 4(-4) serait l'abscisse et 3(-3) serait l'ordonnée

Merci encore de ta précieuse explication, c'est cool de prendre du temps pour les autres comme ça =)

De rien, même un merci fait toujours plaisir