Pour le coup, je pense qu'ils disposent déjà d'un moteur de trajet plus générique que celui que je pourrais proposer.
Mais je lis ici http://www.navit-project.org/?page=readme
qu'ils utilisent l'algorithme de Dijkstra en partant de la destination.
Cet algo permet de calculer les chemins optimum dans un graphe orienté quelconque.
L'algorithme de Sedgewick-Vitter est une optimisation pour les repères cartésiens.
Il dérive de Dijkstra, en partant du point de départ, mais introduit une heuristique qui est la distance à vol d'oiseau (d'où la restriction aux graphes cartésiens) pour rejoindre le point d'arrivée.
Ceci réduit le faisceau d'exploration des noeuds dans le graphe puisque l'optimum est découvert plus tôt.
La complexité de cet algorithme était meilleure que celle de Dijkstra.
Nous l'avions amélioré en introduisant des obstacles pour modifier dynamiquement le graphe et en pondérant le coût de traversée des arrêtes grâce une fonction de cout. Elle interrogeait les données sur la circulation.
J'avoue m'être trop écarté du domaine pour savoir si d'autres algorithmes ont émergé et sont utilisés à l'heure actuelle par l'industrie.
Par contre, tu as indirectement répondu à la question plus haut.
OSM pourrait peut-être aussi se baser sur les travaux de Navit pour proposer cette fonctionnalité.
[^] # Re: Petite reflexion
Posté par nomorepost . En réponse au journal OpenStreetMap dans le Monde. Évalué à 5.
Pour le coup, je pense qu'ils disposent déjà d'un moteur de trajet plus générique que celui que je pourrais proposer.
Mais je lis ici
http://www.navit-project.org/?page=readme
qu'ils utilisent l'algorithme de Dijkstra en partant de la destination.
Cet algo permet de calculer les chemins optimum dans un graphe orienté quelconque.
L'algorithme de Sedgewick-Vitter est une optimisation pour les repères cartésiens.
Il dérive de Dijkstra, en partant du point de départ, mais introduit une heuristique qui est la distance à vol d'oiseau (d'où la restriction aux graphes cartésiens) pour rejoindre le point d'arrivée.
Ceci réduit le faisceau d'exploration des noeuds dans le graphe puisque l'optimum est découvert plus tôt.
La complexité de cet algorithme était meilleure que celle de Dijkstra.
Nous l'avions amélioré en introduisant des obstacles pour modifier dynamiquement le graphe et en pondérant le coût de traversée des arrêtes grâce une fonction de cout. Elle interrogeait les données sur la circulation.
J'avoue m'être trop écarté du domaine pour savoir si d'autres algorithmes ont émergé et sont utilisés à l'heure actuelle par l'industrie.
Par contre, tu as indirectement répondu à la question plus haut.
OSM pourrait peut-être aussi se baser sur les travaux de Navit pour proposer cette fonctionnalité.