Discussion :

[thom2535]

Bonjour!

Dans le cadre de mon Projet de Fin d'etudes, je dois implementer un algoritme de type branch and bound pour la resolution du TSP.
j'ai choisi l'algorithme de Little. Il se fait cependant que dans mon implementation de cet algorithme, a partir d'un certain nombre de
villes (17 villes environ ), mon programme ne fonctionne plus bien. En effet, on obtient des sous cycles (ne contenant pas toutes les
villes). Ayant revu mon programme plusieurs fois, je me suis demande si au dela d'un certain nombre de villes l'algorithme de Little ne
fonctionnait plus correctement. Je viens donc, apres avoir parcouru plusieurs forums ou je n'ai pas pu avoir de reponse a ma question,
demander votre aide.

Merci, pour toute intervention.

[kolodz]

Bonjour,

TSP: Traveling Salesman Problem's

Je n'ai pas l'impression qu'il y a un problème particulier avec le branch and bound

Il y a d’ailleurs de bon papier à ce niveau :
http://www.jot.fm/issues/issue_2003_03/column7.pdf
(exemple pris au pif, mais qui semple utiliser cette version de solution pour n > 16)

Peut-on voir la source "Little" ou ta version de l'algo ?

Cordialement,
Patrick Kolodziejczyk.

[thom2535]

Bjr!
Merci pour votre réponse. J'ai consulté le fichier retrouvé au niveau de votre lien. L'algorithme implémenté dans ce document est intéressant mais ne me convient pas, parce que je dois utiliser le logiciel matlab pour coder. Et à ma connaissance avec matlab il n'y a pas de structure comme les listes en java qui permettent de stocker des données de taille inconnues au départ (vu que le nombre de nœud pour l'arbre est inconnu). Voici mes sources pour l'algorithme de Little. https://youtu.be/nN4K8xA8ShM , https://youtu.be/B-VOa6368Y0.

[dourouc05]

Avec MATLAB, tu as trente-six manières de contourner ce problème de bibliothèque standard exécrable. Par exemple : créer un tableau (par exemple, de type cell) et ajouter/retirer des éléments à la fin (exécrable pour les performances, ça peut se remplacer par un compteur pour le dernier élément) ; implémenter toi-même une liste avec des classes ; utiliser directement les listes Java (http://nl.mathworks.com/help/matlab/...in-matlab.html).

[thom2535]

Bjr! Merci pour vos apports qui m’ont éclairé.
J'ai trouvé la solution à mon problème. Il était dû à une mauvaise interprétation de la manière dont des arcs devaient être supprimés (dans la matrice des coûts) pour éviter la formation de sous cycles.