Voyageur de commerce: méthode par insertion

[aragornerings]

Bonsoir,
Pouvez vous m'expliquer la méthode par insertion dans le problème du voyageur de commerce?
Je ne comprends pas les explications sur internet. Pouvez vous me donner un exemple concret?

Merci

[fatal_error]

salut,

tu as plus type de méthodes par insertion.
En voici une puérile :
supposons tes villes numérotées 1, 2, 3, 4...
maintenant on a un chemin
1423
qui signifie, on part de la ville 1, puis on va a la ville 4, ensuite à la ville 2 et on termine par la ville 3.

bon, mettons que tu construises ton chemin, et pour l'instant, t'en es au chemin 14.

une des méthodes par insertion consiste à prendre la prochaine ville, donc au pif, 2 ou 3.
Mettons qu'on prenne 2.
On peut insérer 2 en début de chemin, entre les villes 1 et 4 ou en fin de chemin.
Bon, ben on l'insere là ou le chemin est le moins long.

Suppose maintenant qu'on a le chemin 124
ben on fait pareil pour la ville 3.

Au niveau des méthodes, tu as l'insertion par voisin le plus proche, par voisin le plus loin, par cout minimal (celui que jtai présenté), et au pif...

la méthode d'insertion consiste à creer un chemin.

rq : j'ai plus les liens, mais tu peux retrouver a l'aide des mots clés
nearest neighbour, farthest neighbour, usca312 et linear programming
en oubliant pas tsp évidemment...

[ittachi]

excuse moi monsieur je ne comprend pas bien le principe d'algorithme d'insertion
si vous pouvez donner un exemple claire et merci d'avance

[Sylviel]

Tu dois relier A,B,C,D.
Je décris un chemin comme suis
ABCD signigie la boucle A -> B -> C -> D -> A
par convention je pars de A.

Pour construire un chemin par insertion je part d'un chemin incomplet
exemple : AD
Ensuite je choisit un nouveau sommet
exemple : C
Puis je décide où je le mets
exemple ACD ou ADC
Pour décider il y a plusieurs manière de faire
exemples :
- je rajoute C après son plus proche voisin
- je rajoute C au hasard
- je rajoute C là où le chemin créé sera le plus court
Puis je prends un nouveau point et je décide où le rajouter...

[ittachi]

merci infiniment (y)