Discussion :

[tagsOf]

Salut à tous,

Je suis en train d'essayer d'implémenter l'heuristique gloutonne du voyageur de commerce (insertion ville par ville de manière optimum), il semble a priori que le meilleure moyen pour cela est d'utiliser une Liste plutôt qu'un Tableau a cause des insertions, le coup sur une liste est rapide, alors que sur un tableau il y des décalages à envisager.

Que me conseillerai vous pour implémenter facilement, clairement, et optimalement cette heuristique ?

En vous remerciant d'avance !

[tagsOf]

Pour l'algorithme glouton, voici une un résumé rapide de la procedure:

Une méthode gloutonne par insertion
Une première méthode pour trouver rapidement une solution approchée est la suivante. On part du chemin entre les villes 0 et 1. On cherche à insérer la ville 2 dans ce chemin de manière à minimiser la longueur. Si plusieurs positions sont possibles, on choisi la dernière dans une exploration gauche-droite de la liste courante des villes. On procède ainsi successivement pour chaque ville.

[karamellam]

Pour l'algorithme glouton, voici une un résumé rapide de la procedure:

Est ce que quelqu'un pourrait me dépanner avec un code ( quelque sois le langage) pour la programmation de l'heuristique gloutonne pour le problème de voyageur de commerce???

Merciiiiiiiiii

[Jedai]

Est ce que quelqu'un pourrait me dépanner avec un code ( quelque sois le langage) pour la programmation de l'heuristique gloutonne pour le problème de voyageur de commerce??

Voyons, supposons que tu aies les fonctions et types suivants :

Code Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
distance :: Graph -> Town -> Town -> Cost
data Path = Path { cost :: Cost, towns :: [Town] }
foldNodes :: (a -> Town -> a) -> a -> Graph -> a

Alors l'algorithme glouton pour le voyageur de commerce serait :

Code Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
-- greedyBest graph ==> "best" circuit
greedyBest :: Graph -> Path
greedyBest g = foldNodes optimize (Path 0 []) g
  where
   optimize bestPath town = minimumBy (comparing cost) (inserts bestPath town)
   inserts (Path 0 []) town = [Path 0 [town]]
   inserts (Path c (t:ts)) town = Path (c + distance g town t) (town:t:ts) : go (t:) t ts
     where
      go f t ts@(hd:tl) = 
          Path (c + distance g t town + distance g town hd - distance g t hd) (f (town : ts)) 
             : go (f . (hd:)) hd tl
      go f t [] = 
          [Path (c + distance g t town) (f [town])]

La partie un peu dure de ce code est inserts : elle génère toutes les insertions possibles d'une ville dans un chemin (mon code pour cette fonction est un peu complexe, surtout la fonction auxiliaire go() , pour être efficace). optimize sélectionne ensuite la possibilité la moins coûteuse et foldNodes effectue récursivement cette opération pour toutes les villes du graphe.

Bonne chance !
--
Jedaï

[Trap D]

Jedaï >> ne sentirait-on pas pointer comme un peu d'ironie dans ce post ?

[Jedai]

Jedaï >> ne sentirait-on pas pointer comme un peu d'ironie dans ce post ?

C'est sans doute le côté : "j'ai la flemme de chercher un code de voyageur de commerce utilisant l'heuristique gloutonne mais il me faut la réponse tout de suite et (je suis tellement un crack que le langage n'importe pas/je ne lirais même pas la réponse avant de la rendre à mon prof donc le langage n'importe pas)"...
Je suis peut-être un peu cynique mais c'est ce que j'ai compris du post de karamellam.

Néanmoins ma réponse est également sérieuse, bien que légèrement incomplète puisque basée bêtement sur l'heuristique exposée plus haut, qui ne gère même pas le cas où la ville n'est pas atteignable depuis les villes déjà dans le circuit.

--
Jedaï

[lamine minyar]

pour generer les voyageur on peut utuliser la fonction rand() ou random.
et concernant le code voici :
*matrice distance;
placer les vouyageurs
afficher meilleur parcours
et si tu veux tu peux faire une interface graphique