algorithme 2-opt, voisinage d'une visite commentée

Question

je ne peux pas vraiment comprendre comment trouver les voisins d'une visite commentée en utilisant l'algorithme 2-opt:

Supposons que nous ayons T = 0-1-2-4 -0-0

la définition est la suivante: le voisinage de T est défini comme l'ensemble des tours qui peuvent être atteints en changeant deux arêtes non adjacentes en T (2-échange).

Nous avons donc ces bords non adjacents:

(0,1) et (2,4)

(0,1) et (4,3)

(1,2) et (4,3)

(1,2) et (3,0)

(2,4) et (3,0)

nous devons trouver 5 voisins , comment nous pouvons les générer en faisant ces 2 mouvements d'échange?

Merci d'avance.

Answer 1

Vous avez la bonne idée de trouver des paires d'arêtes non adjacentes. Ensuite, pour chaque paire, il y a exactement une façon possible de former un nouveau tour en attachant de nouveaux bords. Par exemple, si nous supprimons (0,1) et (2,4), il y a trois paires d'arêtes que nous pourrions remplacer par:

(0,1) et (2,4): mais ceci est le même que le circuit original

(0,4) et (1,2), mais cela crée deux subtours au lieu d'une excursion

(0,2) et (1,4): ceci est le gagnant

En général, si nous supprimons les arêtes (i, j) et (k, l), nous les remplaçons par (i, k) et (j, l) - en supposant que cela réduit le coût. Notez que cela change l'orientation de la moitié du tour. Donc, selon votre définition, le quartier de T est l'ensemble des nouveaux circuits qui peuvent être atteints de cette manière.