Prg qui recherche le chemin le + court
Résolu/Fermé
A voir également:
- Prg qui recherche le chemin le + court
- Recherche musique - Guide
- 3 bip long 2 bip court hp - Forum BIOS
- Consultez le code source de cette page. copiez la ligne qui indique aux moteurs de recherche de ne pas référencer la page. ✓ - Forum Référencement
- Google recherche par image - Guide
- Évariste souhaite télécharger le logiciel libreoffice depuis le site de son éditeur. sélectionnez le résultat de recherche sur lequel il doit cliquer. ✓ - Forum Windows Vista
8 réponses
Tu as aussi les algorithmes génétiques mais à priori, les résultats ne sont pas meilleurs que le recuit simulé.
De toutes façons, une solution parfaite demanderait un temps de calcul phénoménal et n'est donc pas envisageable.
Pour répondre à Louis, le problème n'est pas résolu à l'heure actuelle, y compris par Googlemaps qui utilise très probablement un recuit simulé.
De toutes façons, considérer un problème comme résolu c'est du domaine de la religion et non de la science : même des choses qui nous semblent aussi fondamentales que 1+1=2 peuvent être remises en question.
De toutes façons, une solution parfaite demanderait un temps de calcul phénoménal et n'est donc pas envisageable.
Pour répondre à Louis, le problème n'est pas résolu à l'heure actuelle, y compris par Googlemaps qui utilise très probablement un recuit simulé.
De toutes façons, considérer un problème comme résolu c'est du domaine de la religion et non de la science : même des choses qui nous semblent aussi fondamentales que 1+1=2 peuvent être remises en question.
Effectivement ca risque d etre corcée: ca entre dans la partie recherche du chemin minimal dans un graphe
qe j ai abordé cette anéee.
Familiarise toi d abord avec ca avant de paser aux algos.
qe j ai abordé cette anéee.
Familiarise toi d abord avec ca avant de paser aux algos.
maily
Messages postés
7556
Date d'inscription
lundi 26 juin 2000
Statut
Contributeur
Dernière intervention
23 juin 2023
453
15 juil. 2003 à 11:55
15 juil. 2003 à 11:55
aye, j'ai trouvé!! L'algo utilisé marche très bien et est très connu!!
Je me disais aussi que je connaissais le problème! c'est l'algorithme de Moore-Dijkstra
Bon courage
Maily :-))))
Je me disais aussi que je connaissais le problème! c'est l'algorithme de Moore-Dijkstra
Bon courage
Maily :-))))
shifer
Messages postés
1
Date d'inscription
mardi 15 juillet 2003
Statut
Membre
Dernière intervention
15 juillet 2003
15 juil. 2003 à 12:35
15 juil. 2003 à 12:35
merci beaucoup, mais dis où es-que je pourrais avoir cet algo?
maily
Messages postés
7556
Date d'inscription
lundi 26 juin 2000
Statut
Contributeur
Dernière intervention
23 juin 2023
453
15 juil. 2003 à 12:53
15 juil. 2003 à 12:53
Tiens voila déjà un lien!!
http://name.math.univ-rennes1.fr/jean-claude.raoult/INFO1/graphes.pdf
Sinon, tu le trouves dans n'importe quel bouquin qui parle de recherche opérationnel ou tout simplement par google!!
bon courage
Maily :-))))
http://name.math.univ-rennes1.fr/jean-claude.raoult/INFO1/graphes.pdf
Sinon, tu le trouves dans n'importe quel bouquin qui parle de recherche opérationnel ou tout simplement par google!!
bon courage
Maily :-))))
teebo
Messages postés
33491
Date d'inscription
jeudi 14 octobre 2004
Statut
Modérateur
Dernière intervention
24 février 2011
1 793
15 juil. 2003 à 11:46
15 juil. 2003 à 11:46
Salut
T'as peur de rien!
Le fameux probleme du voyageur de commerce! Des annees de recherche et toujorus rien de parfait dans le domaine, des algos tous plus compliques les uns que les autres...
Aucune chance de rechercher toutes les solutions...Le meilleur algo a ce jour et a ma connaissance:
Le recuit simule
Demande a l'aami google ce qu'il en pense de cet algo il a surement plein de sites la dessus, mais attention, ca commence a etre des maths de niveau interessant :-D
. .
\_/
T'as peur de rien!
Le fameux probleme du voyageur de commerce! Des annees de recherche et toujorus rien de parfait dans le domaine, des algos tous plus compliques les uns que les autres...
Aucune chance de rechercher toutes les solutions...Le meilleur algo a ce jour et a ma connaissance:
Le recuit simule
Demande a l'aami google ce qu'il en pense de cet algo il a surement plein de sites la dessus, mais attention, ca commence a etre des maths de niveau interessant :-D
. .
\_/
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
maily
Messages postés
7556
Date d'inscription
lundi 26 juin 2000
Statut
Contributeur
Dernière intervention
23 juin 2023
453
15 juil. 2003 à 11:49
15 juil. 2003 à 11:49
Bonjour shifer!
Non Teebo, ce n'est pas le problème du voyageur de commerce, mais tout simplement celui du plus court chemin! Parce que le voyageur de commerce doit passer par toutes les villes, mais la, ce n'est pas nécessaire!!
Par contre, le nom de l'algo utilisé, je n'en ai plus aucune idée, désolée!! Je vais essayer de trouver quand meme!
Maily :-))))
Non Teebo, ce n'est pas le problème du voyageur de commerce, mais tout simplement celui du plus court chemin! Parce que le voyageur de commerce doit passer par toutes les villes, mais la, ce n'est pas nécessaire!!
Par contre, le nom de l'algo utilisé, je n'en ai plus aucune idée, désolée!! Je vais essayer de trouver quand meme!
Maily :-))))
teebo
Messages postés
33491
Date d'inscription
jeudi 14 octobre 2004
Statut
Modérateur
Dernière intervention
24 février 2011
1 793
15 juil. 2003 à 11:54
15 juil. 2003 à 11:54
Arf oui autant pour moi, mais ca releve de la meme problematique quand meme, sauf que tu dois pouvoir peut etre tester toutes les solutions si tu as une bonne machine...
cherche pathfinding dans google, c'est tres utilise notamment dans les jeux...
. .
\_/
cherche pathfinding dans google, c'est tres utilise notamment dans les jeux...
. .
\_/
batmat
Messages postés
1871
Date d'inscription
jeudi 1 novembre 2001
Statut
Membre
Dernière intervention
9 janvier 2008
114
15 juil. 2003 à 13:15
15 juil. 2003 à 13:15
L'algo des chemins minimaux est basé sur des calculs sur des matrices : matrices de connexité, matrice d'adjacence...
avec un tableau à deux dimensions contenant tous les points et leurs distances tu peux trouver le plus court chemin...
De mémoire, il n'est pas extrêmement compliqué (juste ce qu'il faut pour se bouger un peu les neurones qd même ;)
Première chose à faire donc : créer la table ou le fichier contenant ces données de distance point à point...
@++
Vous hésitez entre Linux et Windows ?
Vous voulez dépenser du temps ou de l'argent ?
avec un tableau à deux dimensions contenant tous les points et leurs distances tu peux trouver le plus court chemin...
De mémoire, il n'est pas extrêmement compliqué (juste ce qu'il faut pour se bouger un peu les neurones qd même ;)
Première chose à faire donc : créer la table ou le fichier contenant ces données de distance point à point...
@++
Vous hésitez entre Linux et Windows ?
Vous voulez dépenser du temps ou de l'argent ?
