Structures de données optimales pour conception d'un graphe pour faire un GPS [Résolu]

[alexgille]

Bonjour,

je suis étudiant et j'ai pour projet de concevoir une application qui doit reprendre plus ou moins les fonctionnalités d'un GPS: calcule du chemin le plus avantageux selon plusieurs critères tels que la vitesse, la distance ou le prix de déplacement.

J'utilise un graphe basé sur une liste de successeurs mais je ne sais pas quel serait la structure de données optimale à utiliser pour mettre en liens les villes, les moyens de transports et les différents coûts.

Pour l'instant j'utilise ceci :

Classe Node
UUID id
String nom

Classe Edge
UUID id
Node from
Node to
int weight (ici représente la distance entre les deux villes)
Transport t (transport qui emprunte l'arc)

Seulement avec cette structure de données on a autant d'arc entre deux même villes que de moyens de transport reliant ces deux villes..

Quelle serait la structure de donnée optimale pour répondre à mes besoins?

Merci beaucoup.

[Richard_35]

Bonjour Alexgille,

Envoyé par Alexgille

Seulement avec cette structure de données on a autant d'arc entre deux même villes que de moyens de transport reliant ces deux villes..
Quelle serait la structure de donnée optimale pour répondre à mes besoins?

==> il faut isoler le couple constitué des deux villes.

Sans trop comprendre les détails, j'ai supposé que, actuellement, tu as :

Node ---0,n---[associer]---1,1--- Edge (via UUID).

ce qui donne :

Node(UUID, nom, ...) ;
Edge(#UUID, Node from, Node to, int weight, Transport t, ...).

Si, donc, j'ai bien compris, en isolant le couple constitué des deux villes, cela donnerait :

Node ---0,n---[associer]---1,1--- From_To ;
From_To ---0,n---[associer]---1,1--- Edge.

ce qui donnerait :

Node(UUID, nom, ...) ;
From_To(Id_FromTo, #UUID, Node from, Node to, ...) ;
Edge(#Id_FromTo, int weight, Transport t, ...).

[alexgille]

Ta réponse est niquel! Merci

Toutefois, cette structure de données est-elle compatible avec un algorithme de type dijkstra sur un graphe orienté?

Le graphe n'est pas vraiment orienté vu que pour toutes paires de villes (A,B) il existe les arcs A-B et B-A.

Merci pour tes réponses.

[Richard_35]

Bonjour Alexgille,

Envoyé par Alexgille

cette structure de données est-elle compatible avec un algorithme de type dijkstra sur un graphe orienté?

==> ?... je ne sais pas si le smiley "parle" de lui-même... dans la négative, je ne connais pas cet algorithme.

Cette modélisation est, simplement, une application des règles de gestion que tu as énoncées dans ton premier post.

Envoyé par Alexgille

Le graphe n'est pas vraiment orienté vu que pour toutes paires de villes (A,B) il existe les arcs A-B et B-A.

==> si ton souci est d'interdire B-A si A-B existe, alors la solution consisterait à créer un trigger qui, donc, interdit {Node from, Node to} si {Node to, Node from} avec les mêmes valeurs existe déjà.

[alexgille]

Merci beaucoup pour ces réponses

Tu penses que dans le forum Algorithmique quelqu'un pourrait m'aider?

[alexgille]

Envoyé par Richard_35

Si, donc, j'ai bien compris, en isolant le couple constitué des deux villes, cela donnerait :

Node ---0,n---[associer]---1,1--- From_To ;
From_To ---0,n---[associer]---1,1--- Edge.

ce qui donnerait :

Node(UUID, nom, ...) ;
From_To(Id_FromTo, #UUID, Node from, Node to, ...) ;
Edge(#Id_FromTo, int weight, Transport t, ...).

Seulement si tu fais ça, on a évité d'avoir un arc pour l'aller et un pour le retour mais pas d'avoir autant d'arc entre deux villes que de moyens de transports ..

Quel serait selon toi la meilleur structure de donnée pour un graphe ..?

[Richard_35]

Bonsoir Alexgille,

Envoyé par Alexgille

Tu penses que dans le forum Algorithmique quelqu'un pourrait m'aider?

==> je ne sais pas trop. A priori, je dirais "non".

Tu as besoin d'un graphe orienté : OK. Ce graphe est donc composé de points ayant des attributs particuliers. Il faut donc vérifier si, à partir de la structure de données que tu sembles avoir validée, tu possèdes toutes les données nécessaires à la détermination des attributs de ces points.

Si j'ai bien tout compris, bien entendu...

[alexgille]

Envoyé par Richard_35

A priori, je dirais "non".

L'algorithme de dijkstra permet de trouver le plus court chemin entre deux noeuds du graphe.
Il se sert pour cela d'une liste de noeuds, ce qui veut dire qu'il faut pouvoir ressortir la liste exhaustive des noeuds simplement, dans notre cas pas de problèmes.
Il se sert aussi de la liste des successeurs de chaque noeuds ainsi que le poids de l'arc qui relie les noeuds entre eux. Donc il faut pouvoir accéder au poids d'un arc en identifiant l'arc par l'attribut "to" qu'il contient.
Le poids d'un arc est unique et équivaut à la distance entre les villes.
Afin de déterminer le chemin le moins chère ou le plus rapide, on calcule le poids en fonction des caractéristiques d'un véhicule et de la distance.

Le tout à implémenter en Java :/

[Richard_35]

Bonjour Alexgille,

Envoyé par Alexgille

liste des successeurs de chaque noeuds

==> as-tu cette information avec le MCD défini ?

Envoyé par Alexgille

ainsi que le poids de l'arc qui relie les noeuds entre eux. Donc il faut pouvoir accéder au poids d'un arc en identifiant l'arc par l'attribut "to" qu'il contient.
Le poids d'un arc est unique et équivaut à la distance entre les villes.

==> compte tenu du MCD défini, l'information semble trouvable, non ?

Envoyé par Alexgille

en fonction des caractéristiques d'un véhicule

==> information non disponible.

Envoyé par Alexgille

Le tout à implémenter en Java :/

==> je n'ai aucune compétence Java, mais le forum idoine sera à ta disposition.

[souviron34]

Envoyé par alexgille

Tu penses que dans le forum Algorithmique quelqu'un pourrait m'aider?

Tout dépend..

Ne pas confondre analyse et implémentation..



Dans ton analyse, tu dois identifier les objets, leurs propriétés, et leurs relations.

Ensuite, dans l'implémentation, tu dois fabriquer ces structures et ces liens avec le langage choisi.

Enfin, si tu as besoin d'un algorithme particulier (ici Djiskra), cet algoithme est ça : un algorithme. Il s'applique de manière générique. A toi soit de le programmer en fonction du langage que tu utilises, soit de récupérer une fonction qui le fait dans un certain langage et de lui fournir les bons paramètres ..

Bref, beaucoup de flou dans ce qui est la conception d'un logiciel et/ou d'une fonctionalité...

[alexgille]

Envoyé par souviron34

Ne pas confondre analyse et implémentation..

Oui, je sais, et c'est pour ça que je demande quelle structure de donnée je pourrais implémenter en Java.

Le fait est que j'ai déjà implémenté une partie de la structure de donnée mais qu'en milieux de chemin j'ai remarqué que ça commençait à devenir un vrai plat de pattes avec l'obligation de dupliquer certaines valeurs, ce qui est à éviter en informatique.

C'était pour perfectionner et apprendre à mieux concevoir mon programme.

Merci pour les réponses