Discussion :

[ReiVon]

Bonjour,

Je travaille actuellement sur une petite application de recherche d'itinéraire.
J'aurais plusieurs petites questions à vous poser si cela ne vous dérange pas.

J'ai fait pas mal de recherche et apparemment dijkstra est le meilleur choix à faire pour une recherche optimale. Les performances sont moindres qu'un A* mais le résultat sera toujours correcte. Est-ce que sur ce point j'ai bien raison ?
J'ai lu des choses sur une "heuristique admissible" pour le A*, notamment pour les distances l'heuristique à choisir serait la distance à vol d'oiseau entre le point de départ et le point d'arrivé. Est-ce qu'une heuristique admissible garantie réellement une solution optimale ? ou il y a toujours des risques d'avoir des approximations ? ...


Concernant la recherche du chemin le plus court, j'ai bien pu réaliser un petit programme pour gérer cela (avec dijkstra), cependant je souhaite maintenant implémenter une recherche du chemin le plus "rapide". Au niveau de mes données j'ai donc des distances et un nombre de km/h sur mes arcs séparant mes sommets. La dessus je bloque un peu.
J'ai pensé réalisé l'algo sur le fait suivant : je calcul le temps de parcours de mon arc en minutes. Moins j'ai de minutes, mieux c'est. Cela m'impose donc de transformer légèrement mes données en prenant en compte la distance et la vitesse.

Ma question est simple : est ce réellement la meilleure manière de faire ? y a t'il une solution particulière pour ce problème ?

Une dernière petite question, j'ai sur mon parcours des "obstacles" ou tous les véhicules ne peuvent pas forcément passer (prenons l'exemple d'un tunnel d'une certaine hauteur). Dois je effectuer un pré-traitement pour ignorer ces arcs où un véhicule trop grand ne peut pas passer, ou dois je les ignorer au moment où je les rencontre ? Comment les interpréter dans l'algorithme de dijkstra ? A la base je pensais y mettre le plus grand nombre possible et le supprimer de mes arcs de recherche. Est-ce bien la meilleure solution ?

Désolé si les questions parraissent basiques / stupides. Je découvre les algorithme et je m'y interresse grandement !
Je vous remercie tous d'avance pour votre lecture ou votre aide .
ReiVon.

[Furikawari]

Bonjour,

Je travaille actuellement sur une petite application de recherche d'itinéraire.
J'aurais plusieurs petites questions à vous poser si cela ne vous dérange pas.

J'ai fait pas mal de recherche et apparemment dijkstra est le meilleur choix à faire pour une recherche optimale. Les performances sont moindres qu'un A* mais le résultat sera toujours correcte. Est-ce que sur ce point j'ai bien raison ?
J'ai lu des choses sur une "heuristique admissible" pour le A*, notamment pour les distances l'heuristique à choisir serait la distance à vol d'oiseau entre le point de départ et le point d'arrivé. Est-ce qu'une heuristique admissible garantie réellement une solution optimale ? ou il y a toujours des risques d'avoir des approximations ? ...

Pour Dijsktra, la réponse oui (+lent mais 100% optimal).

Le principe d'une heuristique c'est justement que tu n'as pas de garantie de toujours avoir la solution optimale. Une bonne heuristique te donnera de bons résultats dans la majorité des cas. c'est tout ce qu'on peut réellement dire (en général).

Concernant la recherche du chemin le plus court, j'ai bien pu réaliser un petit programme pour gérer cela (avec dijkstra), cependant je souhaite maintenant implémenter une recherche du chemin le plus "rapide". Au niveau de mes données j'ai donc des distances et un nombre de km/h sur mes arcs séparant mes sommets. La dessus je bloque un peu.
J'ai pensé réalisé l'algo sur le fait suivant : je calcul le temps de parcours de mon arc en minutes. Moins j'ai de minutes, mieux c'est. Cela m'impose donc de transformer légèrement mes données en prenant en compte la distance et la vitesse.

Ma question est simple : est ce réellement la meilleure manière de faire ? y a t'il une solution particulière pour ce problème ?

C'est la bonne approche. Tu mets un poids sur tes arcs.

Une dernière petite question, j'ai sur mon parcours des "obstacles" ou tous les véhicules ne peuvent pas forcément passer (prenons l'exemple d'un tunnel d'une certaine hauteur). Dois je effectuer un pré-traitement pour ignorer ces arcs où un véhicule trop grand ne peut pas passer, ou dois je les ignorer au moment où je les rencontre ? Comment les interpréter dans l'algorithme de dijkstra ? A la base je pensais y mettre le plus grand nombre possible et le supprimer de mes arcs de recherche. Est-ce bien la meilleure solution ?

Désolé si les questions parraissent basiques / stupides. Je découvre les algorithme et je m'y interresse grandement !
Je vous remercie tous d'avance pour votre lecture ou votre aide .
ReiVon.

Le plus simple est probablement de modifier dynamiquement leur poids en leur mettant une valeur arbitrairement grande. Cependant dans le cas où il n'y aurait aps de chemin, ces arcs pourraient alors être empruntés. A gérer.

[ReiVon]

Bonjour,

Merci pour ces réponses, elles me confortent dans mes idées.

Pour la dernière question je vois que ce n'est pas forcément si simple que cela ...
En espérant avoir d'autres réponses !

Merci encore !
ReiVon

[SpiceGuid]

"plus rapide" ou "plus court", du point de vue de l'algo qui cherche à minimiser le coût total (somme des poids de chacun des arcs) je te confirme que c'est du pareil au même.

[bafman]

Le plus simple est probablement de modifier dynamiquement leur poids en leur mettant une valeur arbitrairement grande. Cependant dans le cas où il n'y aurait aps de chemin, ces arcs pourraient alors être empruntés. A gérer.

Attention à cette solution.
En effet, si tu veut te rendre d'un point A à un point B et qu'il existe un point de passage obligatoire par le tunnel, l'algo finira par trouver un chemin par la. En effet, le chemin n'est pas impraticable, il est juste beaucoup plus cher.

Le plus simple est finalement d'avoir un contexte permettant de savoir ce qui est en train de recherche un chemin (voiture, camion), et d'avoir une methode sur tes arcs qui retourne la "passabilité" de cet arc en fonction du contexte... Comme ça, tu est sûr de pouvoir adapter le comportement de l'algo en fonction de tes besoins.

[ReiVon]

Bonjour,

Merci pour ce complément. Effectivement cela peut poser problème.
Je vous tiendrais au courant de mes évolutions.

Si d'autres personnes ont des idées, qu'elles n'hésitent pas !

[buggen25]

Il faut utliser l'alogorithme de dijkstra, c'est le plus simple
je pense que tu possède une class arc du type

Code :

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

1
2
3
4
5
6
7
8
9
10
 
Class Arc
{
        double m_fDistance;
        double m_fVitesse;
        vector <Obstacle*> m_listeObstacles;
        Sommet * pDepart,
        Sommet * pDest;
....
}

Je pense qu'il faut ajouter a l'arc une liste d'obstacle dont tu doit definir les contraintes qu'ils imposent (concevoir la classe en somme). Un obstacle va diminuer la vitesse par une deceleration GAMMA a un instant t ou a un intervalle Delta_t , donc on doit le prendre en compte

[laoshu]

Si tu es curieux, tu pourrais aller voir le Travelling salesman problem, qui n'est pas tout à fait pareil, mais qui est intéressant (http://en.wikipedia.org/wiki/Traveling_salesman_problem , à la différence que pour ce problème, cela inclus aussi de passer un certain nombre de "villes" et de trouver un chemin pour retourner ensuite à la ville d'origine. Le TSP a été étudié de toutes les façons possibles en mathématique/informatique (algos génétiques, échantillonage probabilistes, etc.) Il y a même des livres qui ont été écrits sur ce problèmes (ex: http://books.google.com/books?hl=en&...MgzQc50jLwf6rE ). Le problème est NP difficile.

Pour ton problème, tu pourrais aussi considérer de garder certains résultats pré-calculés dans une BD ou fichier pour accélérer le traitement, considérer un algorithme qui pourrait te générer une solution meilleure de façon incrémentale peut-être en fonction du temps que tu lui aloue, utiliser un algorithme plus rapide, mais qui ne garanti pas nécessairement une solution optimale. Tout cela dépend de la taille de ton problème, etc. Je fais seulement te donner quelques idées!

Bonne journée.

[ReiVon]

Merci pour ces liens intéressants et ces conseils.
Je ne vais pas hésiter à consulter tout cela !

Concernant la recherche du chemin, je suis "malheureusement" contraint à trouver la solution optimale car cela est bien le but. Sinon je me serais plus tourné vers une solution comme A*.

@buggen25 : effectivement c'est ce vers quoi je suis parti pour le moment et qui me paraît le plus logique / efficace.

[Alp]

Si tu es curieux, tu pourrais aller voir le Travelling salesman problem, qui n'est pas tout à fait pareil, mais qui est intéressant (http://en.wikipedia.org/wiki/Traveling_salesman_problem , à la différence que pour ce problème, cela inclus aussi de passer un certain nombre de "villes" et de trouver un chemin pour retourner ensuite à la ville d'origine. Le TSP a été étudié de toutes les façons possibles en mathématique/informatique (algos génétiques, échantillonage probabilistes, etc.) Il y a même des livres qui ont été écrits sur ce problèmes (ex: http://books.google.com/books?hl=en&...MgzQc50jLwf6rE ). Le problème est NP difficile.

Pour ton problème, tu pourrais aussi considérer de garder certains résultats pré-calculés dans une BD ou fichier pour accélérer le traitement, considérer un algorithme qui pourrait te générer une solution meilleure de façon incrémentale peut-être en fonction du temps que tu lui aloue, utiliser un algorithme plus rapide, mais qui ne garanti pas nécessairement une solution optimale. Tout cela dépend de la taille de ton problème, etc. Je fais seulement te donner quelques idées!

Bonne journée.

Au passage, on a 2 articles sur la résolution de ce problème... Avec des méthodes d'approximation.
http://khayyam.developpez.com/articl...rce/genetique/
http://khayyam.developpez.com/articl...es-de-fourmis/