Discussion :

[lenas_tshaleb]

bonjour,

je suis entrain de développer un programme qui résout le problème de voyageur de commerce, en c++ et en utilisant l'algorithme du recuit simulé.

j'utilise graphe<S,T> pour représenter le graphe, PElement<T> (une arête ou un sommet), Sommet<T>, Arête<S,T>.


ma question est quelle est la meilleur structure de donnée à utiliser pour représenter l'espace d'exploration S qui est l'ensemble des cycles eulériens du graphe, sachant qu'à la fin de l'algo je dois sélectionner une solution dans S la moins coûteuse, ce qui fait que soit les solutions doivent être déjà dans un certain ordre, soit je dois les trier pour sélectionner le min ?


aussi, comment utiliser l'algorithme du recuit simulé pour rechercher un plus court chemin d'un sommet origine à un sommet arrivée dans le graphe ?


merci d'avance pour vos réponses.

[ternel]

une classe bien choisie, permettant de calculer son cout.
Ca peut très bien être un vector<arete> dont tu calcule la somme des couts.

[Jimmy91]

Bonjour !

aussi, comment utiliser l'algorithme du recuit simulé pour rechercher un plus court chemin d'un sommet origine à un sommet arrivée dans le graphe ?

Dans un premier temps, je te conseille d'utiliser le mouvement du 2-opt comme mouvement de transformation. Il est facile à implémenter, et tu as beaucoup de documentation sur le net à ce sujet. Bien entendu, tu auras les paramètres habituels, avec E la performance de ta solution et T le temps de calcul, par exemple.

Après, quand tu auras programmé le mouvement du 2-opt avec succès, tu pourras essayer de programmer l'algorithme de Lin-Kernighan, qui trouve d'excellentes solutions en un temps très restreint.

ma question est quelle est la meilleur structure de donnée à utiliser pour représenter l'espace d'exploration S qui est l'ensemble des cycles eulériens du graphe, sachant qu'à la fin de l'algo je dois sélectionner une solution dans S la moins coûteuse, ce qui fait que soit les solutions doivent être déjà dans un certain ordre, soit je dois les trier pour sélectionner le min ?

En ce qui concerne la structure de données à utiliser : comme l'a précisé leternel, un std::vector est une solution simple pour un premier développement. Après, comme tu te poses la question du meilleur conteneur et comme il s'agit de prendre la meilleure solution trouvée à chaque itération, je te conseillerais une structure de priority_queue fondée sur un tas binaire pour optimiser les performances de calcul, et elle est très efficace si tu as besoin d'accéder fréquemment à la meilleure valeur.

En gros, cette structure ne stocke pas les valeurs (ici les solutions trouvées) dans une simple chaîne classée par ordre croissant ou décroissant. Il s'agit d'un arbre binaire trié par nature, où la meilleure solution est placée au sommet, où chaque nœud père est une meilleure solution que le nœud fils et où chaque père possède au maximum deux fils. Il y a d'autres règles que tu pourras facilement trouver sur le net.

Si tu prends la priority_queue de la STL, tu peux obtenir de bons résultats, mais en implémentant une priority_queue fondée sur un tas binaire, tu as :

- un temps d'accès à la meilleure solution immédiat (O(1) contre O(n) pour un std::vector)
- un temps d'insertion et de suppression en O(log(n)) (contre O(n) pour un std::vector).

Bon courage !