-
Voyageur de commerce
J'ai écrit un algorithme sélectif/génétique qui permet de faire un trajet parmi des points imposés sans passer par le même point.
Cependant pour concevoir/redécouvrir celui de l'algorithme du voyageur je bloque, j'ai déjà cherché des articles là-dessus, tous assez complet mais aucun qui ne me décrivait bien le processus.
avez-vous un bon article ou une piste pour m'aider?
-
je comprends pas bien ta question, mais va voir du coté des algorithmes de Dijkstra, tu trouvera peut-être ta réponse ;-)
-
le problème du voyageur de commerce est assez strandard.
Comme intro au algo genetiques, il y a http://www.eudil.fr/~vmagnin/coursag/index.html
qui est pas mal. Il donne quelques directions pour le PVC :mrgreen: .
Un autre site plus dedié au PVC est http://home.alex.tuxfamily.org/pvc.html
en plus il donne des sources.
Si tu parles un peu l'anglais, il y a des milliers de sites pour "travelling salesman".
Par contre il y a d'autres algo qui peuvent etre efficaces pour la resolution de ce problème et voir meme meilleur et plus simple.
Par contre les algorithmes de Dijkstra c'est pas la meme chose mais bien a connaitre.
bon courraage
a+
Vic
-
Il y a entre autre comme algorythmes:
l' Alpha-Beta (on calcule toute les possibilité en descendant dans l'arbre des villes)
le recuit simulé ( approximation du meilleur trajet, en s'inspirant de la cuisson des poteries)
-
Ou 1 algo basé sur une colonie de fourmis aussi ...
-
-
Il s'agit de trouver le plus court chemin reliant toutes les villes en reproduisant le comportement des fourmis
Voilà un lien où tu peux avoir des infos :
http://iridia.ulb.ac.be/~mdorigo/ACO/ACO.html
-
Merci pour les liens, pour l'instant je ne m'y suis pas encore rendu, je me casse d'abord les dents dessus.
-
Super!
Je n'ai pas totalement fini l'algorithme du voyageur de commerce, cependant j'ai trouvé un autre algorithme qui permet de sélectionner dans un graphe, les hiérarchies possibles. En gros sélectionner toutes les solutions d'arbres envisageables. Bon je vais le mettre au propre