Chemin minimale entre deux ville
Résolu/Fermé
zineb_iga
Messages postés
21
Date d'inscription
mardi 10 novembre 2009
Statut
Membre
Dernière intervention
3 mars 2010
-
10 nov. 2009 à 21:27
mamiemando Messages postés 33446 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 20 décembre 2024 - 19 oct. 2012 à 20:24
mamiemando Messages postés 33446 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 20 décembre 2024 - 19 oct. 2012 à 20:24
A voir également:
- Chemin minimale entre deux ville
- Itinéraire google map entre deux adresses - Guide
- Deux ecran pc - Guide
- Deux comptes whatsapp - Guide
- Faire deux colonnes sur word - Guide
- Chaque fichier en ligne sur le web a un chemin d’accès sur un serveur. c’est le cas du fichier du logo présent sur la page de cette ville. quel est le chemin de ce fichier à partir de la racine du site ? ✓ - Forum Réseau
2 réponses
mamiemando
Messages postés
33446
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
20 décembre 2024
7 812
10 nov. 2009 à 23:49
10 nov. 2009 à 23:49
En fait c'est un peu dommage de faire de la recherche pour un problème qui se résout en temps polynomial avec l'algorithme de dijkstra.
https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra
Une première approche peut être de s'inspirer d'un algorithme de path finding (utilisé par exemple dans les jeux vidéos pour déplacer une unité entre deux points).
https://fr.wikipedia.org/wiki/Recherche_de_chemin
En recherche aveugle il faut pouvoir calculer à chaque fois qu'on atteint un carrefour :
- la direction globale de chaque route qui part de ce carrefour
- la direction globale à suivre pour atteindre la destination (direction cible = objectif de l'heuristique)
- choisir la route qui se rapproche le plus de la direction cible (heuristique)
Tu peux déterminer la direction (l'angle sur la boussole) d'une route à partir de la position du carrefour courant (x,y) et de la position du carrefour qui suit (x',y') : si x != x' : angle = tan((y'-y)/(x'-x)) : cette formule calcule l'angle par rapport à la ligne ouest/est.
Tu peux ainsi calculer l'angle suivi par chaque route et calculer celui qui se rapproche le plus de l'angle cible. Une fois ce choix fait tu fais un mouvement (au sens propre et au sens "méta heuristique"). Ceci signifie que tu fais évoluer les variables de sorte à te rapprocher de ton objectif. On peut en outre mémoriser les positions (les carrefours) par lesquelles on est passé.
À ce stade, ça risque de marcher la plupart du temps si la carte n'est pas trop un "labyrinthe". Mais supposons qu'on applique une telle heuristique dans un labyrinthe, tu risques rapidement de tourner en rond. C'est là qu'il faut utiliser des ruses provenant du monde des méta heuristiques, par exemple un mécanisme tabou. Cela consiste à mémoriser une liste de choix faits par le passé en vue de ne pas les refaire par la suite. Ainsi si tu tournes en rond, quand tu tomberas sur un carrefour que tu as déjà croisé, tu prendras une autre direction (sous entendu : la direction qui paraît la meilleure sera taboue).
En espérant que ça t'aide,
Bonne chance
https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra
Une première approche peut être de s'inspirer d'un algorithme de path finding (utilisé par exemple dans les jeux vidéos pour déplacer une unité entre deux points).
https://fr.wikipedia.org/wiki/Recherche_de_chemin
En recherche aveugle il faut pouvoir calculer à chaque fois qu'on atteint un carrefour :
- la direction globale de chaque route qui part de ce carrefour
- la direction globale à suivre pour atteindre la destination (direction cible = objectif de l'heuristique)
- choisir la route qui se rapproche le plus de la direction cible (heuristique)
Tu peux déterminer la direction (l'angle sur la boussole) d'une route à partir de la position du carrefour courant (x,y) et de la position du carrefour qui suit (x',y') : si x != x' : angle = tan((y'-y)/(x'-x)) : cette formule calcule l'angle par rapport à la ligne ouest/est.
Tu peux ainsi calculer l'angle suivi par chaque route et calculer celui qui se rapproche le plus de l'angle cible. Une fois ce choix fait tu fais un mouvement (au sens propre et au sens "méta heuristique"). Ceci signifie que tu fais évoluer les variables de sorte à te rapprocher de ton objectif. On peut en outre mémoriser les positions (les carrefours) par lesquelles on est passé.
À ce stade, ça risque de marcher la plupart du temps si la carte n'est pas trop un "labyrinthe". Mais supposons qu'on applique une telle heuristique dans un labyrinthe, tu risques rapidement de tourner en rond. C'est là qu'il faut utiliser des ruses provenant du monde des méta heuristiques, par exemple un mécanisme tabou. Cela consiste à mémoriser une liste de choix faits par le passé en vue de ne pas les refaire par la suite. Ainsi si tu tournes en rond, quand tu tomberas sur un carrefour que tu as déjà croisé, tu prendras une autre direction (sous entendu : la direction qui paraît la meilleure sera taboue).
En espérant que ça t'aide,
Bonne chance
ScorpU
Messages postés
143
Date d'inscription
mardi 24 mai 2011
Statut
Membre
Dernière intervention
17 janvier 2022
77
19 oct. 2012 à 00:33
19 oct. 2012 à 00:33
Existe-t-il l'algorithme de Dijkstra pour trouver le point le plus centrale entre deux lieux ? Peut-on l'étendre à plusieurs lieux ?
Ex : j'organise un weekend entre pote. Le but du weekend est de jouer aux échecs, donc on peut le faire n'importe où. Mais nous habitons tous très loin les uns des autres. Nous cherchons donc à trouver un point central où nous retrouver.
Ex : j'organise un weekend entre pote. Le but du weekend est de jouer aux échecs, donc on peut le faire n'importe où. Mais nous habitons tous très loin les uns des autres. Nous cherchons donc à trouver un point central où nous retrouver.
mamiemando
Messages postés
33446
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
20 décembre 2024
7 812
19 oct. 2012 à 10:21
19 oct. 2012 à 10:21
Merci à l'avenir d'ouvrir un nouveau sujet, car la question est différente et ce sujet est résolu?
Oui tu peux utiliser plusieurs instances de l'algorithmes de Dijkstra pour résoudre ce problème. Pour chaque point de départ s du calcule Dijkstra qui va ta calculer vers l'ensemble des villes d'arrivées. Ensuite tu calcules tu fais la moyenne et tu prends la ville dont le coup moyen est le plus faible.
Après il y a peut-être une approche plus subtile qui offrent une meilleure complexité que de calculer S algorithmes de Dijkstra ou S est le nombre de sommets sources, mais comme ça reste une approche polynomiale, donc ça reste envisageable même pour de gros graphes. Dans le même genre, tu peux aussi regarder du côté de l'algorithme de Ford Bellman (du coup il faut raisonner sur les villes d'arrivées).
À ta place je regarderais aussi du côté des algorithmes de calcul de centralité.
Oui tu peux utiliser plusieurs instances de l'algorithmes de Dijkstra pour résoudre ce problème. Pour chaque point de départ s du calcule Dijkstra qui va ta calculer vers l'ensemble des villes d'arrivées. Ensuite tu calcules tu fais la moyenne et tu prends la ville dont le coup moyen est le plus faible.
Après il y a peut-être une approche plus subtile qui offrent une meilleure complexité que de calculer S algorithmes de Dijkstra ou S est le nombre de sommets sources, mais comme ça reste une approche polynomiale, donc ça reste envisageable même pour de gros graphes. Dans le même genre, tu peux aussi regarder du côté de l'algorithme de Ford Bellman (du coup il faut raisonner sur les villes d'arrivées).
À ta place je regarderais aussi du côté des algorithmes de calcul de centralité.
ScorpU
Messages postés
143
Date d'inscription
mardi 24 mai 2011
Statut
Membre
Dernière intervention
17 janvier 2022
77
19 oct. 2012 à 18:17
19 oct. 2012 à 18:17
Merci pour ton aide Mamiemando !
Ta première proposition est celle que je me suis résolu à programmer. Mais je continue de chercher le nom de ce problème, qui est peut-être en fin de compte trop insignifiant pour porter un nom propre.
J'ai également ouvert un autre sujet "Problème du point central" :
https://forums.commentcamarche.net/forum/affich-26282855-probleme-du-point-central#p26283030
Ta première proposition est celle que je me suis résolu à programmer. Mais je continue de chercher le nom de ce problème, qui est peut-être en fin de compte trop insignifiant pour porter un nom propre.
J'ai également ouvert un autre sujet "Problème du point central" :
https://forums.commentcamarche.net/forum/affich-26282855-probleme-du-point-central#p26283030
mamiemando
Messages postés
33446
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
20 décembre 2024
7 812
19 oct. 2012 à 20:24
19 oct. 2012 à 20:24
Parfait :-)
11 nov. 2009 à 00:25
merci infiniment
11 nov. 2009 à 23:09
Je t'ai déjà donné un début d'algorithme dans mon message précédent. Lui se base sur la position du carrefour auquel on se trouve et le prochain carrefour où l'on arrivera. Il est donc aveugle dans la mesure ou il ne voit qu'à un bond là ou il va arriver. Il est heuristique car il part du principe que "plus une route est dans la bonne direction, plus on elle a de chance de nous emmener à destination".
Bonne chance
18 nov. 2009 à 18:42
18 nov. 2009 à 20:09