Chemin minimale entre deux ville
Résolu
Bonjour,
j'ai un mini projet de l'intelligence artificielle, ce projet consiste d'une recherche du chemin minimale entre deux villes sur une carte routière par les algorithmes de recherche aveugles et heuristique.
si vous avez une idée sur ça aidez moi SVP merci d'avance
j'ai un mini projet de l'intelligence artificielle, ce projet consiste d'une recherche du chemin minimale entre deux villes sur une carte routière par les algorithmes de recherche aveugles et heuristique.
si vous avez une idée sur ça aidez moi SVP merci d'avance
A voir également:
- Chemin minimale entre deux ville
- Nombre de jours entre deux dates excel - Guide
- Deux ecran pc - Guide
- Comment faire deux colonnes sur word - Guide
- Itinéraire google map entre deux adresses - Guide
- Code gta vice city psp débloquer ville - Forum PSP
2 réponses
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
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.
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é.
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
merci infiniment
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