Discussion :

[sihame]

Bonjour,

je dois écrire un programme en prolog qui résout le problème du voyageur de commerce, mais je ne sais pas comment procéder :?

est ce qu'il y a quelqu'un qui peut m'expliquer le principe et la manière de trouver le chemin le plus court??

merci d'avance

[ulukahio]

Hum. Quelqu'un qui te dit que tu dois résoudre le problème du voyageur de commerce ne doit pas être très au courant des choses... Sans doutes t'a-t-il dit de rechercher une solution approchée, puisque, étant un problème NP difficile (de complexité exponentielle), il est impossible de trouver un moyen sûr de parvenir à la solution.
Ce que je te conseile, c'est de suivre un tutoriel sur la recherche opérationnelle (ça doit pouvoir se trouver sur le net). Mais tu ne tomberas jamais sur la solution miracle, juste une solution approchée.

Donc pour trouver un principe, il faut d'abord que tu saches avec quelle précision tu veux obtenir ton chemin.

[sihame]

je sais k'il n y a pas de solution exacte
peut être j'ai mal choisi les termes mais je ne cherche k'à savoir le principe de la recherche de la solution
quelles sont les points auxquels je dois penser pour essayer de résoudre le prob

[billynirvana]

Salut!

J'ai déjà répondu à ce genre de questions.

regarde dans ce même forum le sujet:

[Prolog] Calcul de plus court chemin ds un graphe

Maintenant, il est largement possible qu'il soit insuffisant. Lis cet article, et reviens avec plus de détails pour ton exercice (énoncé, exemples...).

Il existe des centaines de moyens d'y arriver, par exemple avec la méthode Tabou