Discussion :

[carton99]

Bonjour,
désolé j'ai beaucoup cherché avant de posté la question ici mais je voyais pas trop ou la poser.

Je dois réaliser un programme qui résout des problèmes de voyageur du commerce (TSP).
Pour cela je dois utiliser l'algorithme de little.

Du point de vue java, il n'y a pas de problème.

Par contre dans la compréhension de l'algorithme j'ai 2 problèmes majeurs.

Ma première question et quand deux « 0 » on le même poids, comment faire pour choisir le bon?(c'est une question très importent, puisque sa change énormément la suite de l’arbre)
La deuxième est directement liée à la première, comment faire pour savoir le chemin final, quand s'arrête l'algorithme et comment reconstruire le chemin?

Exemple à la deuxièmes questions mon chemin final le plus cour est DE/-->BA-->CD-->CE sachant qu'il y a 5 villes A,B,C,D,E. Quel sera le chemin final du voyageurs, es que cette solution est possible?

[carton99]

Personne ne connait Little.
voici un lien pour vous faire une idée.
http://pageperso.lif.univ-mrs.fr/~mi...s/cours4_8.pdf

[flunch]

Salut,

Alors pour répondre as tes questions, il est tard, mais peut etre que tu en as encore besoin.

avec l'algorithme de little tu as deux choses, d'un coté tes matrices, et de l'autre coté une arborescence qui tiens compte de tes choix ou de tes non choix.

Matrice: Concernant ta question, lorsque tu as 2 poids identiques sur la meme matrice, le choix est fait arbitrairement, il n'y a aucune façon de savoir quelle choix sera mieux. En revanche, fait attention a bien interdire l'inverse des chemins que tu as déjà déterminé.

Arborescence:Une fois que tu as trouvé tout ton arborescence, et qu'il ne te reste plus de ville a traité, attention a la mauvaise interprétation de l'arborescence, tu as trouvé les couples dans un certain ordre, mais cet ordre n'est en aucun cas l'ordre d'exécution.
dans ton exemple tu as du trouver tes couples dans cet ordre la:
DE-->BA-->CD-->CE ce qui est faux, car tu as deux fois un depart de la ville C, il fallait interdire le chemin CE car tu avais trouvé CD et DE donc CE est impossible. mais pour répondre a ta question sur un autre exemple on va prendre ceci BE-->AC-->DA-->FB-->CF (trouvé dans cet ordre)
Ton chemin final sera: DACFBE (D) (tu repars de la ville de l'ancienne destination)

Voila j'espère que tu aura compris.