Voyageur de Commerce

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 :aie: .

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 :yaisse2:

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.

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 )

Citation:

---

Envoyé par lun4t1k

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

---

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

- 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 :cry:

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^^

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

si tu veux passer par un max de points en un temps limité mais en acceptant de repasser plusieurs fois par un même point (ce qui n'est pas le voyageur de commerce) il y a un algo très simple, qui est celui à la base de la méthode du "convex hull" ou "gift-wrapping".

• Tu prend le point (par exemple) le plus en bas à droite de ton ensemble de points.
  
• Tu ranges les points par rapport à leur angle (croissant) fait avec ce point.
  (avec un qsort)

tu passes par tous les points, mais tu repasses à chaque fos au point de référence, et c'est extrêmement rapide à calculer.

Mais je ne sais pas si c'est ça que tu souhaites...

Il faudrait expliquer un peu plus ce que tu souhaites :

tu as tes points sur la carte, et ?? tu veux sortir quoi ?

Bonsoir,

pour les heuristiques, regarde du coté des méta heuristiques.

Pour ton algo, la solution optimale passe souvent près de l'enveloppe convexe, d'ailleur je sais qu'un algo fait ce genre de procédé. Regarde sur la page de Michel Van Caneghem, il enseigne ce genre de choses.

Sinon, quand tu fais un voyageur de commerce, l'heuritique concernant à choisir le plus proche voisin en premier est courament utilisée. Elle permet d'éliminer les mauvais cas très tôt dans l'arbre de recherche.


Bonne nuit à tous...

Sinon, quand tu fais un voyageur de commerce, l'heuritique concernant à choisir le plus proche voisin en premier est courament utilisée. Elle permet d'éliminer les mauvais cas très tôt dans l'arbre de recherche.


Tout à fait ;) je vais utiliser cet heuristique ;)


et Souviron ta solution ne va pas c'est interdit de repasser par les mêmes points perte de temps :yaisse2:


Méta heurisique (Wiki):

Les métaheuristiques forment une famille d’algorithmes d’optimisation visant à résoudre des problèmes d’optimisation difficile issus de la recherche opérationnelle pour lesquels on ne connaît pas de méthode classique plus efficace.

Les métaheuristiques sont généralement des algorithmes stochastiques itératifs, qui progressent vers un optimum par échantillonnage d’une fonction objectif. Elles se comportent comme des algorithmes de recherche, tentant d’apprendre les caractéristiques d’un problème afin d’en trouver une approximation de la meilleure solution (d'une manière proche des algorithmes d'approximation).


Ca va déja mieux avec cette définition plus explicite ;)

Citation:

---

Envoyé par hugobosscool26

Les métaheuristiques sont généralement des algorithmes stochastiques itératifs, qui progressent vers un optimum par échantillonnage d’une fonction objectif.

---

Ce n'est qu'une classe de métaheuristiques. Et il faut souvent se "méfier" de stochastique itératives, le rendement n'est souvent pas très bon, et souvent aussi avec de petites "simplifications" on peut se ramener à une formule probabiliste explicite. D'autres classes, lié aussi à de l'aléatoire: algos génétiques, réseaux bayésiens, inductions neuronales,...

Citation:

---

Envoyé par ToTo13

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

---

tout a fait ! :mouarf:

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.

avant d'indiquer plus de réponses, il faudrait peut etre que hugobosscool26 precise ce qu'il veut, car le probleme qu'il decrit n'est pas le probleme du voyageur de commerce, comme certain l'ont deja fait remarquer.... donc hugobosscool26, eclaire nous sur ce point !!

Citation:

---

Envoyé par hugobosscool26

et Souviron ta solution ne va pas c'est interdit de repasser par les mêmes points perte de temps :yaisse2:

---

La solution que j'avais donné permet de passer par tous les points sans repasser par le même point. C'est juste si tu traces le résultat que ça passe par le même point, si tu le souhaites.

Mais avec un seul qsort sur les N points, plus une boucle pour déterminer le point le plus bas à droite, tes points sont correctement classifiés et tu peux passer de l'un à l'autre.

C'est juste que ça n'est pas forcément le plus cours chemin, mais c'est un chemin qui passe par tous les points une fois..

D'accord Souviron mais il faut également que ca soit le chemin minimal mais je pense avoir trouvé avec l'heurisitique du plus proche voisin.

On prend apparement:

-3 listes: une avec le chemin, une avec tous les points et une vide au début qu'on nommera liste fermée.

On démarre avec:
Un point initial pris dans la liste des points au hasard qu'ensuite on rajoute à une liste fermée

On regarde le point le plus proche et on l'ajoute au chemin et à la liste fermée.

On regarde de nouveau le point le plus proche et on l'ajoute à la liste fermée


... etc jusqu'à un certain temps ou bien lorsque la liste des villes restantes est vide.

Répéter avec un point de départ différent.


Cet algo est apparement le plus simple à réaliser et le plus rapide !

jobherzt:

Le problème du voyageur de commerce consiste, étant donné un ensemble de villes séparées par des distances données, à trouver le plus court chemin qui relie toutes les villes.


:)

Ca correspond tout à fait à ce que je veux !

Citation:

---

Envoyé par souviron34

La solution que j'avais donné permet de passer par tous les points sans repasser par le même point. C'est juste si tu traces le résultat que ça passe par le même point, si tu le souhaites.

Mais avec un seul qsort sur les N points, plus une boucle pour déterminer le point le plus bas à droite, tes points sont correctement classifiés et tu peux passer de l'un à l'autre.

C'est juste que ça n'est pas forcément le plus cours chemin, mais c'est un chemin qui passe par tous les points une fois..

---

En faite l'algo que j'ai donné précédemment peut être résumé par ce que tu dis également je pense:

listeTotal=tous les points désirés
liste=listeTotal

Tant que point dans listeTotal
{
-Je prends un point parmi listeTotal
-j'enleve ce point dans listeTotal
-Je calcule toutes les distances avec les autres points de liste sauf le mien
-Les classe suivant la distance avec ton qsort dans mon tableau qui contient tous mes points de listeTotal^^
}

et ca revient au même que l'algo que tu dis je pense :)


Si tu as un quicksort en java sans récursivité je veux bien aus passage :yaisse2:
Merki pour tout !

Citation:

---

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

ah oui super :) et tu sais comment le coder?

perso moi non :oops:

Citation:

---

Envoyé par hugobosscool26

ah oui super :) et tu sais comment le coder?

perso moi non :oops:

---

Ca a pas l'air bien dur... Et puis, les sources sont fournies en Java et Delphi