[irrlicht][vc++ 2003] projet darwin : voyageur de commerce avec algorithme génétique
Description
Le problème du voyageur de commerce est de trouver le cycle le plus court passant par toutes les villes qu'il doit visiter.
C'est un problème NP-complet, ce qui veut dire que pour l'instant, pour prouver qu'on a la meilleure solution, on doit tester toutes les solutions ou presque. On a une complexité de (n-1)!/2 avec n le nombre de ville.
Le problème de tester toutes les solutions, c'est que ça prend un temps considérable, je n'ai pas reussi à faire mieux que 20 villes (environ 80 millions de milliard de possibilité), ça m'a prit 6h sur un Q6600 (quad core de chez intel). Pour arriver à ce résultat, je droppe souvent en plus milieux du calcul du chemin car il y a des moyens de savoir si ce chemin a des chances d'être le meilleur ou pas. Par exemple, si le chemin à un croisement, alors il n'est pas optimal.
Bon, c'est bien beau, mais 20 villes, c'est pas bien compliqué, même pour un humain.
Donc, qu'est ce qu'on peut faire de mieux ?
C'est là que l'algorithme génétique à été employé (tout comme plusieurs sources ici).
Il y a 2 programmes, un qui permet de construire des graphes et un autre qui essaye de le résoudre.
Qu'apporte de plus ma source ? je pense un meilleur résultat et de plus, on peut l'exploiter (du moins, avec le mode sans décroisement car ce mode me fait planter aléatoirement le programme quand la population de chemin converge, et je n'ai pas le temps ni la motivation pour le modifier maintenant que mon projet est rendu).
Tout le projet ne rentre pas dans le zip, je laisse donc un rar sur le site où vous pouvez tout dl.
Pour plus d'infos, je vous conseille le rapport de projet disponible ici :
http://www.mupuf.fr.nf/Projets/Darwin/Rapport_darwin.doc
Amusez vous bien avec ;-)
C'est un problème NP-complet, ce qui veut dire que pour l'instant, pour prouver qu'on a la meilleure solution, on doit tester toutes les solutions ou presque. On a une complexité de (n-1)!/2 avec n le nombre de ville.
Le problème de tester toutes les solutions, c'est que ça prend un temps considérable, je n'ai pas reussi à faire mieux que 20 villes (environ 80 millions de milliard de possibilité), ça m'a prit 6h sur un Q6600 (quad core de chez intel). Pour arriver à ce résultat, je droppe souvent en plus milieux du calcul du chemin car il y a des moyens de savoir si ce chemin a des chances d'être le meilleur ou pas. Par exemple, si le chemin à un croisement, alors il n'est pas optimal.
Bon, c'est bien beau, mais 20 villes, c'est pas bien compliqué, même pour un humain.
Donc, qu'est ce qu'on peut faire de mieux ?
C'est là que l'algorithme génétique à été employé (tout comme plusieurs sources ici).
Il y a 2 programmes, un qui permet de construire des graphes et un autre qui essaye de le résoudre.
Qu'apporte de plus ma source ? je pense un meilleur résultat et de plus, on peut l'exploiter (du moins, avec le mode sans décroisement car ce mode me fait planter aléatoirement le programme quand la population de chemin converge, et je n'ai pas le temps ni la motivation pour le modifier maintenant que mon projet est rendu).
Conclusion :
Tout le projet ne rentre pas dans le zip, je laisse donc un rar sur le site où vous pouvez tout dl.
Pour plus d'infos, je vous conseille le rapport de projet disponible ici :
http://www.mupuf.fr.nf/Projets/Darwin/Rapport_darwin.doc
Amusez vous bien avec ;-)
Codes Sources
- AlgoDarwin
- Graphs
- GUI
- Media
- randomc
- Algorithme.cpp
- Algorithme.h
- Algo_CC.cpp
- Algo_CC.h
- bruteforce.cpp
- bruteforce.h
- Constants.h
- Darwin.sln
- Darwin.suo
- Darwin.vcproj
- err.cpp
- err.h
- graph.cpp
- graph.h
- heur_rnd.cpp
- heur_rnd.h
- Multithreading.cpp
- Multithreading.h
- node.cpp
- node.h
- ppv.cpp
- ppv.h
- SPath.cpp
- SPath.h
- tree.cpp
- tree.h
A voir également
- [irrlicht][vc++ 2003] projet darwin : voyageur de commerce avec algorithme génétique
- Projet intranet - Forum Visual Basic
- Mini projet gestion d'un cabinet medical - Forum Visual Basic 6
- Projet c++ débutant - Forum C++ & C++ .NET
- Etat avancement projet ✓ - Forum VB.NET
- Projet php - Forum PHP
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.