Voyageur de Commerce

**hugobosscool26** · 02/04/2007, 22h18

Salut à tous

Je m'intéresse actuellement au problème du voyageur de commerce et j'ai vraiment besoin d'aide sur cet algorithme.

Le but étant de passer par un max de points en un temps limité ce qui correspond au but de cet algo mais je n'en connais pas le déroulement

.

Pourrais-je avoir s'il vous plaît un pseudo-code ou code (java ou c#) pour résoudre cet algo? J'ai bien sûr déja était sur Wiki ou autre donc ces liens ne me seront pas utiles

Je précise que je recherche un algo assez rapide (< 5 secondes) en gros pour 50 points maximum !

Merci d'avance pour toutes vos réponses

**ToTo13** · 02/04/2007, 23h34

Bonjour,

mmmm, je ne suis pas sûr que tu trouves du code tout fait sur le sujet.
En général, cela se passe de la façon suivante :
- tu disposes d'un graphe représentant les différents lieux, les accés entre ces lieux et les temps pour s'y rendre.
Mais en pratique cela est variable en fonction de ton problème (type de déplacement).
- tu donnes un point de départ et une date.
- tu appliques l'algorithme de Dijkstra (suis pas sûr de l'orthographe :s) à partir de chaque nouveau point où tu te trouves.
- ce n'est pas un problèmes facile au niveau complexité, donc tu peux ajouter des heuristiques.

**lun4t1k** · 02/04/2007, 23h37

Un code tout fait c'est tendu, mais tu trouveras juste des heuristiques en cherchant bien.
Et puis vu que c'est un probleme np-complet, si tu trouves la meilleure solution de tous les heuristiques existants, tu m'appelles !
(récompense à la clé :p )

**ToTo13** · 02/04/2007, 23h42

Envoyé par lun4t1k

...
(récompense à la clé :p )

de l'ordre du million de dollars me semble t-il ... :p

**hugobosscool26** · 02/04/2007, 23h52

- tu disposes d'un graphe représentant les différents lieux, les accés entre ces lieux et les temps pour s'y rendre.
- tu donnes un point de départ et une date.
- tu appliques l'algorithme de Dijkstra (suis pas sûr de l'orthographe :s) à partir de chaque nouveau point où tu te trouves.
- ce n'est pas un problèmes facile au niveau complexité, donc tu peux ajouter des heuristiques.

Ok pour calculer les distances j'ai Astar (pas Dijkstra

mais c'est le même principe sauf qu'il est plus rapide normalement).

Je n'ai pas de graphe mais des points sur une carte avec des coordonnées x et y

des heuristiques stp c'est ?

parce que avec ca:

Une heuristique (du grec heuriskêin, trouver) est l'utilisation de règles empiriques :

* pratiques, simples et rapides,
* facilitant la recherche des faits et l'analyse de situations,
* dans un objectif de résolution de problèmes et de prise de décision,
* dans un domaine particulier.
Cela ne m'aide pas trop

Source: Wiki

Sinon si ya pas de code je veux bien du pseudo code

cela ne me dérange pas car là je vois pas mieux pr l'instant !

Vu que j'ai une carte de 200*200 si je dois tester chaque position avec les distances etc ca fait bcp^^

**hugobosscool26** · 03/04/2007, 00h48

voilà je me suis renseigné et je vais utiliser plutôt l'insertion plus proche, si quelqu'un a un pseudo code

merki

**lun4t1k** · 03/04/2007, 11h09

Envoyé par ToTo13

de l'ordre du million de dollars me semble t-il ... :p

tout a fait !

**CedricMocquillon** · 03/04/2007, 14h35

Bonjour

Une des meilleures heuristiques qui existe est basée sur une première phase de résolution du problème d'affectation correspondant. La solution du problème d'affectation te donne entre 1 et n cycles (si n est le nombre de villes à visiter), si tu tombes sur 1 alors stop, tu as ta solution au problème de voyageur de commerce (PVC) sinon il faut que tu fusionnes les cycles obtenus. Il existe plusieurs règles de fusion mais une qui n'est pas trop difficile à implémenter et qui marche pas trop mal est de trier les cycles obtenus par taille décroissante, ensuite pour les deux premiers cycles, tu retires les arcs de sorte à ce que ton cout initial moins les deux arcs retirés (un dans chaque cycle) plus les arcs ajoutés pour fusionner soit minimum. Ensuite tu itères jusqu'a n'obtenir plus qu'un seul cycle.
Il existe également des méthodes assez efficaces pour obtenir l'optimum: tu fais une procédure par séparation évaluation ou à chaque noeud tu prends une décision sur les arcs: l'arc (i,j) appartient ou non à la solution.

Bon courage

PS: la récompense d'un million de $ correspond à la preuve de "P=NP" et n'a rien à voir avec "la meilleure solution de tous les heuristiques existants" si je trouve une nouvelle heuristique plus efficace, je n'aurais pas pour autant prouvé "P=NP" pour cela il faut trouver une méthode exacte (méthode exacte != heuristique) qui donne la solution en temps polynomial.

**pseudocode** · 03/04/2007, 22h55

Envoyé par hugobosscool26

Je précise que je recherche un algo assez rapide (< 5 secondes) en gros pour 50 points maximum ! (...) J'ai bien sûr déja était sur Wiki ou autre donc ces liens ne me seront pas utiles

C'est louche. Le 1er lien que me donne Google c'est du code java qui résout 48 points en moins de 1 seconde. C'est un algo 2-opt avec 2 transformations: décroisement + inversion.

la demo ici