 |
|
|
|
| prg qui recherche le chemin le + court par  shifer |
mardi 15 juillet 2003 à 11:41:28 |
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 . . \_/ |
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. |
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 :-)))) |
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... . . \_/ |
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 :-))))
|
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 ? |
Est-ce que tu as vraiment besoin de ça ? Google Earth ne peut pas t'aider ? Consacre-toi aux problèmes réels et non ceux déjà résolus et avance avec le monde plutôt que de travailler pour la distraction. |
| 13/03 20h55 | Chemin court | Windows | 13/03 22h07 | 9 |
| 15/08 16h08 | recherche de courts ou de livre | Etudes/Formation | 01/09 13h38 | 1 |
| 07/04 12h45 | recherche chemin de mon .class | Programmation | 07/04 14h29 | 4 |
| 27/03 16h48 | algorithmes de recherche de plus court chemin | Internet | 27/03 16h48 | 0 |
