Dijkstra: optimisation?
(Pardon pour les accents => clavier qwerty)
Bonjour,
Les sites comme Mappy utiliseraient des algorithmes de recherche basé sur Dijkstra. Mais dans le cas d'une recherche a grande échelle (comme un parcours Madrid - Berlin), Dijkstra ne me parrait plus vraiment adapté, en raison de l'explosion combinatoire qui en resulte.
Connaissez vous les formes d'optimisations utilisees?
a) un systeme informatique TRES puissant?
b) une optimisation au niveau des graphes? Par exemple, creer un graphe de plus haut niveau dont chaque noeud representerait une zone plus ou moins large de la carte reelle... Les arcs liant les noeuds representeraient les autoroutes, ou le meilleurs vecteur de transport?
la premiere recherche se ferait donc sur ce graphe, puis le systeme analyserait les chemins sur la carte reelle concernant le point depart et le point d'arrivee?
c) utilisaton d'une heuristique/fonction d'arret de la recherche a partir d'un noeud? Lancer un Dijkstra "normal", mais en arretant le parcours a partir d'un noeud si il s'éloigne trop de la destination (selon un critere géographique) par rapport à la solution optimale... Cela permettrait de bloquer un parcours qui va dans des direction estimàes "abérantes". L'evaluation (la fonction d'arret de la recherche a partir d'un noeud) devrait etre assez souple pour permettre de petits détours qui font gagner du temps, au final.
d) ....?
En se basant sur la solution b)
En se basant sur cette orientation:
b1) Soit regrouper un ensemble de noeuds en un seul,
b2) soit garder le meme graphe en ne considerant que les types de routes rapides (autoroutes, voies express...) pour les trajets dont les points de depart et d'arrivé sont eloignés d'une certaine distance. Ca elaguerait toutes les petites routes. On aurait donc un meme graphe dont la densité serait variable en fonction de l'éloignement des points de départ et d'arrivée. Il faudrait donc gérer de maniere optimale le probleme d'élagage des arcs, car il n'est pas le meme partout: pres des points de depart et d'arrivee, la totalite du graphe doit etre considerée.
b3) ....?
Dans le cas b1), il s'agirait de construire un graphe de plus haut niveau, et dans le cas b2), d'elaguer le graph existant en fonction de la nature des arcs...
Curieusement, je ne trouve pas de documentation sur cette question. Les seules optimisations concernent l'algorithme de Dijkstra proprement dit, mais le gain de compléxité en temps ne semble pas suffisant (sauf erreur de ma part) pour résoudre le probleme à grande échelle.
Comme si les solutions implementées chez Mappy, ViaMichelin ou Autoroute66 étaient des solutions "maisons" gardées secretes. Il doit pourtant éxister une théorie concernant ce type de problemes ^^
J'ai bien trouvé un rapport de stage d'une equipe des Mines, mais ca reste assez léger, car ils ne travaillent que sur un réseau de bus. Ce n'est donc pas le meme probleme, et une adaptation de Dijkstra suffit amplement.
Des idées, des commentaires, des liens?
Merci!
Répondre avec citation
Envoyé par FrancisSourd
Partager