chemin minimale entre deux ville Résolu/Fermé

Question

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

mamiemando · Accepted Answer

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

ScorpU · Answer

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.

Chemin minimale entre deux ville

2 réponses

Discussions similaires