[irrlicht][vc++ 2003] projet darwin : voyageur de commerce avec algorithme génétique

Soyez le premier à donner votre avis sur cette source.

Vue 12 973 fois - Téléchargée 1 710 fois

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).

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

A voir également

Ajouter un commentaire Commentaires
Messages postés
536
Date d'inscription
mercredi 27 avril 2005
Statut
Membre
Dernière intervention
22 août 2008

ben, en fait, pour le multithreading, y'en a pas pour la version qui est compilée, y'a du code pour le faire tourner, mais il est pas utilisé :S (manque de temps, j'ai eu 4 mois pour faire ce programme en plus de mes cours).
Oui, j'ai pas mal cherché pour le MT, ça me plait tout ça !
Je suis en 2eme année de DUT info à Montpellier.

Merci pour la note, ça a beaucoup été surtout un travail de recherche, compréhension de ce qui se passe et tentative d'amélioration. J'ai pas fais la moitié de ce que je voulais faire mais bon, c'est la vie :D

Je voulais faire des classes de chemin, sorte de race, y'a le début du code de création de race mais tjs pareil, abandonné par manque de temps. J'ai tout gardé pour ceux que ça intéresserai.

En ce moment, je suis en stage en angleterre, et comme je suis cloué au lit (malade comme un chien), j'en ai profité pour up la source. Devrais bientôt avoir des codes qui vont arrivé en QT et maybe sur les drivers.

bonne journée ! et encore merci pour le commentaire !
Messages postés
1054
Date d'inscription
samedi 2 octobre 2004
Statut
Membre
Dernière intervention
9 juillet 2013
6
Hiya
Bravo! C'est un programme de grande qualites! Ca merite amplement les 10/10.
Tres bonne optimisation de ton algo surtout en ce qui concerne le multithreading... On voit qu'il y a beaucoup de recherche et de travail deriere.

Tu es en quelle annee d'etude?

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.