Salut
 
Que connaisez-vous comme algorithme de recherche de plus court chemin.
Je connais Dijkstra, qui permet de prendre le parcours le plus rapide sur un reseau de bus par exemple
 
Maintenant, toujours sur mon reseau de bus, je recherche un algo qui choisirait un trajet avec le MINIMUM de changements, (pour les handicapés par expl...) : qu'est-ce que vous connaissez ?
 
Sinon, vous connaissez d'aures algo susceptibles de m'interesser ?
Merci de votre aide

http://www.mappy.com

 
   t'es pas sérieux là au moins...

 
ban

bon en meme temps s'il sait pas ce qu'est un algo, il peut pas avoir compris la question

 
euh... c'est très gros tout de même...    

J'ai un cours sur les parcours de graphes chez moi, je regarderai ce soir si je l'ai pas jeté

Bin dans ce cas, on s'abstient de répondre, non ?

je sais pas de qui il est le multi mais en tout cas y me fait bien délirer !!!

j'essaye de résoudre un topic
je ne vais pas me contenter de poster dans blabla, faut que je participe !
mais je vous avais bien dit que je connaissais rien en prog !

 
bon c qui le propriétaire de ce multi à la con?

tu le demandes encore?

 
Si c'est pour continuer à poster n'importe quoi tu vas finir pas ne plus pouvoir poster du tout

 
tu reprends le même graphe et tu fout 1 comme poids à chaque ligne, quelque soit la distance parcourue. Et tu refais un Dijkstra.
 
Si tu veux distance + nb de changements en mème temps, tu donne une distance en plus comme pénalité à chaque changement, mais t'as pas fini de te battre pour la choisir, car il n'y a pas de solution unique.
 
edit : saloperie de clavier espiguouin + ortho
 
edit2 : pourquoi dans la catégorie ADA ?¿?¿?

 
Je pense que tu peux facilement réutiliser Dijkstra pour résoudre ton problème, en l'arrangeant un peu. La première idée qui me vient à l'esprit serait d'affecter, au fur et à mesure que l'algorithme progresse, un surcoût aux arcs correspondants à des changements de lignes. Ainsi celà éliminerait les parcours optimales avec beaucoup changements, le réglage qualitatif se faisant au niveau du choix des surcoûts à appliquer.
 
peu de surcoûts : on accepte les chemins optimaux, mais avec pas mal de changements
beaucoup de surcoûts : on a un nombre de changements minimal, au risque d'avoir des trajets beaucoup plus longs

 
rhaa j'avais pas vu
 
 
Burps >> Y a une catégorie Algo, c'est pas pour rien hein

 
Parceque c'est une erreur, ca devait etre dans la catégorie Algo
 
Sinon, les solutions que vous me proposez me plaisent moyennement...

 
Si tu trouves mieux , tu m'emvoie un MP car je suis plutôt curieux.
Car rien qu'à la main avec ton plan de métro c'est la merde (prends gare du nord-Montparnasse par ex.).

Tout à fait ! C'est a ce que j'ai pensé en relisant le topic

--------------------------------------------------------------------------------------------------
---------------------------Fin du sujet precedent   ----------------------------------------------
--------------------------------------------------------------------------------------------------
 
(Pardon pour les accents => clavier qwerty)
 
Salut,
 
Je profite de ce sujet deja ouvert pour poser un probleme du meme ordre:
Les sites comme Mappy utiliseraient des algorithmes de recherche base sur Dijkstra. Mais dans le cas d'une recherche a grande echelle (comme un parcours Madrid - Berlin), Dijkstra ne me parrait plus vraiment adapte, 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?
d) ....?
 
Des idees, des liens?
Merci  

L'idée d'un calcul à plusieurs niveaux me semble pas mauvaise...

 
Oui, c'est ce qui me semble le plus adequat...
En se basant sur cette orientation:
a) Soit regrouper un ensemble de noeuds en un seul,
b) 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.
c) ....?
 
Dans le cas a), il s'agirait de construire un graphe de plus haut niveau, et dans le cas b), d'elaguer le graph existant en fonction de la nature des arcs...
 
EDIT: Ou encore, en se basant sur la solution "heuristique" citée plus haut, 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.
 
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 ci 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.
 
Vraiment personne n'a de références/connaissances précises sur cette questions?

Y'a l'algorithme A*, pour lequel on cherche à relier deux points appartenant à un graphe.
 
Chaque chemin est doté d'un poids défini à partir d'heuristiques (par exemple la distance restant à parcourir jusqu'à l'arrivée).
 
On part du départ, on fait la liste des points accessibles, et on calcule le poids associé à chaque arc qui nous permet d'avancer.  
 
On choisit le meilleur chemin, on supprime le point de la liste, et on ajoute à la liste les nouveaux points accessibles grâce à notre avancée.
 
On recommence jusqu'à ce que le point d'arrivée ait été trouvé avec le meilleur chemin (donc on continue à chercher un chemin même si on a atteint l'arrivée, jusqu'à ce que tous les poids de la liste des points restants soient supérieurs au poids associé au point d'arrivée qu'on a trouvé).
 
Je sais pas si c'est clair, ni si c'est ce que vous appellez l'algorithme de Dijkstra...

 
Merci    
Effectivement, l'A* offre une solution au probléme. Je le connaissais dans d'autres contextes (théorie des jeux), mais je n'avais pas fait le lien avec ce contexte ^^
 
J'ai égallement recu deux liens tres intéressants sur un autre forum, si quelqu'un en a besoin...

Essaye le "pathfinding" chez google !