Bonjour,
Je poss=E8de le mod=E8le d'un r=E9seau routier.
Mettons que :
A est =E0 10 km de B, =E0 15 km de C, =E0 30 km de D.
B est =E0 12 km de C, =E0 14 km de D.
C est =E0 17 km de D.
Comment calculer le chemin le plus court entre A et D sans =E9tudier
l'ensemble des possibilit=E9s ? Si toutefois c'est possible.
Merci.
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
Jean-Marc
On May 27, 3:48 pm, fraction wrote:
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
On May 27, 3:48 pm, fraction <fract...@tele2.fr> wrote:
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.
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
On May 27, 3:48 pm, fraction wrote:
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
On May 27, 3:48 pm, fraction <fract...@tele2.fr> wrote:
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
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
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 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.
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
On May 27, 10:43 pm, fraction wrote:
> 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
On May 27, 10:43 pm, fraction <fract...@tele2.fr> wrote:
> 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.
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.
