Hello,

Je suis occupé à convertir un code c++ en c. Heureusement, ce code est très peu "c++ specific" ( → code complet)

Là où je coince, c'est ici (pas sur les typedef ni sur make_pair(), ça c'est réglé) :

// Creating a shortcut for int, int pair type
typedef pair<int, int> Pair;
 
// Creating a shortcut for pair<int, pair<int, int>> type
typedef pair<double, pair<int, int>> pPair;

set<pPair> openList;

openList.insert(make_pair (0.0, make_pair (i, j)));

while (!openList.empty())
{
    pPair p = *openList.begin();

    // Remove this vertex from the open list
    openList.erase(openList.begin());

C'est le set qui m'enquiquine. D'après ceci, dans openList, les éléments sont uniques (pas de souci) et triés.... mais sur quoi ?

Pour (les méthodes ?) .erase, .empty et .begin, je comprends, sauf l'écriture p=*openList.begin(): cela veut-il simplement dire que le contenu de la première position de openList est copié dans p ?

Je comprends bien le .insert, la pierre d'achoppement est, comme je l'ai écrit, sur quoi faut-il trier ?

D'avance merci pour vos lumières,

Edgar;

-
Edité par edgarjacobs 19 mai 2018 à 22:16:37

On comprend mieux en lisant la documentation de C++

<<

Sets are containers that store unique elements following a specific order. (...) Internally, the elements in a <tt>set</tt> are always sorted following a specific strict weak ordering criterion indicated by its internal comparison object (of type <tt>Compare</tt>).

>>

C'est "set" de Pair, reste à trouver quel est le critère de comparaison pour ces bêtes là

http://www.cplusplus.com/reference/utility/pair/operators/

ordre lexicographique : on regarde la première partie de la paire, puis la seconde si ce n'est pas suffisant.

----

ce que j'en comprends, en gros, c'est que l'algorithme commence par mettre un triplet <float,int,int> = {0.0, i, j} dans un conteneur, puis effectue une boucle

tant qu'il en reste {
    prendre le plus petit triplet (dans l'ordre lexico)
    faire des trucs avec, éventuellement en remettre
}

-
Edité par michelbillaud 19 mai 2018 à 17:26:58

Salut,

La définition complete de std::set ressemble à

template <typename ValueType, typename comp=std::less<ValueType>>
class set{
    /* ... */
};

et la fonction std::less ressemble à quelque chose comme

template <typename ValueType>
bool less(ValueType first, ValueType second){
    return first < second;
}

Autrement dit, quelque soit le type des élément que std::set pourra contenir, il s'attendra à (par défaut) ce qu'il existe un opérateur de comparaison bool operator < (type a, type b), mais tu restes tout à fait libre de fournir une fonction personnalisée qui permettra la comparaison de deux valeurs.

Il y a donc trois solutions:

• Soit tu travaille sur des types primitif (char, short, int, long, long long, float, double, ou long double, ou les versions unsigned des types qui les supportent), pour lesquels l'opérateur < est frocément défini
• soit tu travaille sur un type personnalisé pour lequel l'opérateur < est défini
• soit tu travaille avec un type personnalisé et une fonction ou un foncteur qui permet la comparaison.

Par exemple, tu pourrais parfaitement avoir une structure proche de

struct MyStruct{
    int id;
    std::string name;
};

et disposer de deux foncteurs particuliers proche de

struct lessById{
    bool operator()(MyStruct const & a, MyStruct const & b) const{
        return a.id < b.id;
    }
};
struct lessByName{
    bool operator()(MyStruct const & a, MyStruct const & b) const{
        return a.name < b.name;
    }
}

et, si tu définis openList sous la forme de

std::set<MyStruct, lessById> openList;

les élément de openList seront trié par ordre croissant en fonction de la valeur de id alors que si tu le défini sous la forme de

std::set<MyStruct, lessByName> openList;

les élément de openList seront triés par ordre croissant en fonction de la valeur de name.  Et, si, enfin, tu as un opérateur < disponible pour MyStruct, qui pourrait prendre la forme de

bool operator <(MyStruct const & a, MyStruct const & b){
    return a.name < b.name ||
           (a.name == b.name && a.id < b.id);
}

alors, tu pourrais tout aussi bien avoir déclaré openList sous la forme de

std::set<MyStruct> openList;

dont les éléments seraient triés par ordre croissant d'abord sur la valeur de name puis sur la valeur de id. C'est à dire que, si tu as des éléments de type MyStruct qui ressemblent à

MyStruct a;
a.id = 1;
a.name = "ZZZ";
MyStruct b;
b.id = 2;
b.name = "YYY";
MyStruct c;
c.id = 3;
c.name = "XXX" 

Le premier cas te les triera dans l'ordre a < b < c, alors que le deuxième cas te les triera dans l'ordre c < b < a et que le troisième cas permet d'avoir des éléments ressemblant à

MyStruct a;
a.id = 1;
a.name = "AAA";
MyStruct b;
b.id = 2;
b.name = "AAA";
MyStruct c;
c.id = 3;
c.name = "AAA" 

qui seraient triés dans l'ordre a < b < c (parce que le nom est le même, donc l'id entre en ligne de compte)

openList est défini comme étant

std::set<pPair> openList;
/* qui correspond à  */
std::set<std::pair<double, std::pair<int, int>> openList;

Il se fait que l'opérateur < pour la structure std::pair est défini sous la forme de

template <typename A, typename B>
bool operator <(pair<A, B> const & a, pair<A, B> const & b){
    return a.first < b.first ||
           (a.first == b.first && a.second < b.second);
}

Cela signifie que, pour ton alias Pair, il sera défini sous la forme de

template <>
bool operator <(pair<int, int> const & a, pair<int, int> const & b){
    return a.first < b.first ||
           (a.first == b.first && a.second < b.second);
}

et que pour ton alias pPair, il sera défini sous la forme de

template <>
bool operator <(pair<double,pair<int, int>> const & a, pair<double, pair<int, int>> const & b){
    return a.first < b.first ||
           (a.first == b.first && a.second < b.second);
}

Si bien que le tri final commencera par comparer les double entre eux.  Si ils sont égaux, il comparera le premier int de chaque élément, et la décision finale, si le premier int est également égal, reviendra au deuxième int.

En gros, c'est comme si tu avais créé une structure proche de

struct MaStruct{
    double d;
    int x;
    int y;
};

avec un opérateur de comparaison défini sous la forme de

bool operator < (MaStruct const & a, MaStruct const & b){
    return a.d < b.d ||
           (a.d == b.d && a.x < b.x) ||
           (a.d == b.d && a.x < b.x && a.y < b.y); 
}

Re,-

Merci à vous deux pour vos (longues et larges) explications. J'appliquerai cela ce week-end et vous tiens au courant.

Edgar;

-
Edité par edgarjacobs 19 mai 2018 à 21:54:04

koala01 a écrit:

avec un opérateur de comparaison défini sous la forme de

bool operator < (MaStruct const & a, MaStruct const & b){
    return a.d < b.d ||
           (a.d == b.d && a.x < b.x) ||
           (a.d == b.d && a.x < b.x && a.y < b.y);
}

Il me semble que la dernière ligne devrait être

(a.d == b.d && a.x == b.x && a.y < b.y); 

C'est toujours chiant à écrire ces tests :-)

Ceci dit, on est en C, et on ne peut pas surcharger operator<, ni passer des références.

Donc on va passer des adresses. Si on a vraiment besoin d'une collection ordonnée, c'est peut-être plus judicieux d'employer une fonction à la compareTo de Java, qui retourne un nombre négatif, nul ou positif selon que le premier est inférieur, égal ou supérieur

int compareStruct(struct MyStruct *s1,
                  struct MyStruct *s2) {
   double dd = s1->d - s2->d;
   if (dd < 0.0) return -1;
   if (dd > 0.0) return 1;

   int d = s1->x - s2->x;
   if (d != 0) return d;

   return s1->y - s2->y;
}

ou alors

return    s1.d < s2.d   ? -1
       :  s1.d > s2.d   ?  1
       :  s1->x < s2->x ? -1
       :  s1->x > s2->x ?  1
       :  s1->y < s2->y ? -1
       :  s1->y > s2->y ?  1
       :                   0;

avec sa jolie régularité.

PS: j'ai regardé le code fourni pour A* : c'est du C déguisé en C++ (printf !) et mal programmé. Le type a répété le même code 8 fois, parce qu'il y a 8 directions....   Heureusement c'est pas un labyrinthe 3D, avec 26 déplacements possibles....

Déjà, quand je vois ça :

if (row == dest.first && col == dest.second)
        return (true);
    else
        return (false);

ou

if (isValid (i, j+1) == true) {
 ....
}

j'ai une poussée de boutons.

En plus il raconte des trucs approximatifs :

• sa closed list n'est pas une table de hachage, c'est une bête table 2D de marques.
• en utilisant un tas de fibonacci, l'extraction du minimum, qui se fait autant de fois que l'insertion, ça va pas être en temps élémentaire,

-
Edité par michelbillaud 20 mai 2018 à 19:02:17

michelbillaud a écrit:

koala01 a écrit:

avec un opérateur de comparaison défini sous la forme de

bool operator < (MaStruct const & a, MaStruct const & b){
    return a.d < b.d ||
           (a.d == b.d && a.x < b.x) ||
           (a.d == b.d && a.x < b.x && a.y < b.y);
}

Il me semble que la dernière ligne devrait être

(a.d == b.d && a.x == b.x && a.y < b.y); 

C'est toujours chiant à écrire ces tests :-)

Je l'ai repéré, mais merci. Tu fus plus rapide.

michelbillaud a écrit:

PS: j'ai regardé le code fourni pour A* : c'est du C déguisé en C++ (printf !) et mal programmé. Le type a répété le même code 8 fois, parce qu'il y a 8 directions....   Heureusement c'est pas un labyrinthe 3D, avec 26 déplacements possibles....

Déjà, quand je vois ça :

if (row == dest.first && col == dest.second)
        return (true);
    else
        return (false);

ou

if (isValid (i, j+1) == true) {
 ....
}

j'ai une poussée de boutons.

En plus il raconte des trucs approximatifs :

• sa closed list n'est pas une table de hachage, c'est une bête table 2D de marques.
• en utilisant un tas de fibonacci, l'extraction du minimum, qui se fait autant de fois que l'insertion, ça va pas être en temps élémentaire,

Tout à fait d'accord avec toi, mais dans un premier temps cela me suffira. J'ai un code fonctionnel, maintenant je vais passer à travers pour le rendre plus simple / plus propre (et peut-être plus rapide, mais ce n'est pas ma priorité). Il est certain que le coup des 8 blocs pour les 8 directions 

Sorti par mon code (je lui interdis d'exploiter les diagonales):  https://hebergeur-images.com/up/673142f5ec822bed4b6f3d3a85eb4660.png

-
Edité par edgarjacobs 21 mai 2018 à 0:31:11

Ça serait sympa de visualiser aussi les cases qui ont été mises dans l'openlist.

Ça donne une idée de la surface explorée. Normalement, un fuseau autour du chemin trouvé, + des égarements dans des impasses ou partant dans de mauvaises directions.

michelbillaud a écrit:

Ça serait sympa de visualiser aussi les cases qui ont été mises dans l'openlist.

Ça donne une idée de la surface explorée. Normalement, un fuseau autour du chemin trouvé, + des égarements dans des impasses ou partant dans de mauvaises directions.

-
Edité par edgarjacobs 21 mai 2018 à 14:53:53

C'est très joli. Mais effectivement, ça a l'air de passer à beaucoup d'endroits pour trouver une solution.  Il y a peut être beaucoup d'impasses, ceci dit. C'est difficile à voir.

michelbillaud a écrit:

Il me semble que la dernière ligne devrait être

(a.d == b.d && a.x == b.x && a.y < b.y); 

edgarjacobs a écrit:

Je l'ai repéré, mais merci. Tu fus plus rapide.

J'ai effectivement été un peu trop rapide pour écrire ce code (ou, je pourrais faire valoir la fatigue peut-être ??? )

Je ne le modifie pas dans mon intervention originelle pour assumer mes erreurs, mais vous avez tout à fait raison