Calcul du chemin le plus court

Le
fraction
Bonjour,
Je possède le modèle d'un réseau routier.
Mettons que :
A est à 10 km de B, à 15 km de C, à 30 km de D.
B est à 12 km de C, à 14 km de D.
C est à 17 km de D.
Comment calculer le chemin le plus court entre A et D sans étudier
l'ensemble des possibilités ? Si toutefois c'est possible.
Merci.
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Jean-Marc
Le #22178061
On May 27, 3:48 pm, fraction
Bonjour,
Je possède le modèle d'un réseau routier.
Mettons que :
A est à 10 km de B, à 15 km de C, à 30 km de D.
B est à 12 km de C, à 14 km de D.
C est à 17 km de D.
Comment calculer le chemin le plus court entre A et D sans étudier
l'ensemble des possibilités ? Si toutefois c'est possible.
Merci.



Bonjour,
c'est un problème très classique d'informatique, connu sous le nom
générique de "problème du voyageur de commerce" ou "salesman problem" .
C'est un problème difficile, dit "NP complet". voir pour info :
http://fr.wikipedia.org/wiki/Probl%C3%A8me_du_voyageur_de_commerce

La bonne nouvelle, c'est que pour un nombre raisonnable de points, il
existe des méthodes heuristiques donnant la meilleure (ou l'une des
meilleures) solution en un temps assez court.
Les 2 méthodes les plus adaptées sont les algorithmes génétiques et la
méthode de "recuit simulé".

Pour ma part, je l'avais fait avec un algo génétique et on trouve le
meilleur chemin pour une trentaine de points en quelques secondes ou
dizaines de secondes.

En googlant avec les termes ci dessus, tu trouveras ton bonheur.

Cordialement,

--
Jean-marc Noury
Jean-Marc
Le #22178051
On May 27, 3:48 pm, fraction
Bonjour,
Je possède le modèle d'un réseau routier.
Mettons que :
A est à 10 km de B, à 15 km de C, à 30 km de D.
B est à 12 km de C, à 14 km de D.
C est à 17 km de D.
Comment calculer le chemin le plus court entre A et D sans étudier
l'ensemble des possibilités ? Si toutefois c'est possible.
Merci.



J'ai même retrouvé mon code d'algo génétique. C'est un essai brutal ,
programmé en 30 minutes comme un cochon, mais tout est la:
http://users.skynet.be/candide/v1.zip

Bonne lecture!

--
Jean-marc
fraction
Le #22179071
Jean-marc Noury



Merci, je ne suis pas encore familier avec les algorithmes génétiques,
il me faudrait un exemple simple et je ne peux pas lire ton programme,
car je travaille sur Excel.
En revanche, je me suis documenté sur le recuit simulé, et ça
correspond bien à mes attentes.
Jean-Marc
Le #22181241
On May 27, 10:43 pm, fraction
> Jean-marc Noury

Merci, je ne suis pas encore familier avec les algorithmes génétiques ,
il me faudrait un exemple simple et je ne peux pas lire ton programme,
car je travaille sur Excel.



Hello,

tu peux tout de même lire le programme. Le code est lisible dans
le .frm avec un simple éditeur de texte.

Cordialement,

Jean-marc Noury
Publicité
Poster une réponse
Anonyme