Como o algoritmo 3-opt para TSP funciona?

Entendo que a Heurística 3-Opt para solucionar o problema do Vendedor ambulante envolve a remoção de três arestas de um gráfico e a adição de mais três para recompletar o passeio. No entanto, já vi muitos trabalhos que mencionam que, quando três arestas são removidas, restam apenas duas maneiras possíveis de recombinar o passeio - isso não faz sentido para mim.

Por exemplo, encontrei um artigo [1] que diz:

O algoritmo 3-opt funciona de maneira semelhante, mas em vez de remover duas arestas, removemos três. Isso significa que temos duas maneiras de reconectar os três caminhos em um tour válido1 (figura 2 e figura 3). Um movimento de 3 opt pode ser visto como dois ou três movimentos de 2 opt.

No entanto, conto três maneiras diferentes de reconectar o passeio. O que estou perdendo aqui?

Além disso, alguém pode me vincular a um algoritmo para 3-opt, se possível? Estou apenas tentando entender, mas ainda não encontrei nenhum algoritmo claro: todos os recursos encontrados simplesmente dizem "remova três arestas, reconecte-os". É isso, que é meio vago.

Aqui estão os três passeios que me parecem 3-opt depois de remover três arestas.

1. Heurísticas para o problema do vendedor ambulante de C. Nilsson

Você perdeu a nota de rodapé - essas maneiras "não incluem as conexões idênticas a uma única jogada de 2 opções". De fato, existem apenas duas permutações em$S_3$sem pontos fixos (também conhecidos como desarranjos ),$(123)$ e $(132)$. Mais geralmente, por um$k$-opt move, basta considerar permutações sem pontos fixos, já que aqueles com $t$ pontos fixos são $(k-t)$-move.

O algoritmo para $k$-opt pesquisa local é a seguinte. Comece com uma solução inicial, digamos a produzida pelo algoritmo de Christofides. Tente melhorar repetidamente executando um$k$-opt: escolha $k$ arestas e reconecte-as de uma maneira diferente (desta vez, tudo bem se a movimentação também for uma $\ell$-move para alguns $\ell < k$) que resulta em um passeio mais curto.

A maneira como isso é implementado é analisando todos os conjuntos de $k$ arestas e sobre todas as maneiras de reconectar as arestas, talvez em alguma ordem inteligente, e calcular a diferença de comprimento (não é necessário recalcular a duração de todo o passeio, apenas a diferença de comprimento; isso leva $O(k)$ ao invés de $O(n)$); se uma melhoria for encontrada, fazemos a troca e repetimos desde o início. Continuamos assim até ficarmos presos.

Uma variante diferente é sempre tentar todas as possibilidades e usar a que resulta na melhor melhoria. Existem também outras variantes que você provavelmente pode encontrar na literatura.

Digamos que temos 3 pontos A, B e C. Primeiro trocamos (A, B) e depois só podemos trocar (B, C) ou trocar (A, C). Desta forma, temos apenas duas possibilidades diferentes.

Eu poderia encontrar 4 movimentos de 3-opt (que não são 2-opt): se eu desse ao tour hexagonal uma numeração de 123456 (a partir do vértice superior esquerdo), os outros tours teriam os números 125634, 124365, 126534 e 125643 , que são um subconjunto do desarranjo de 12 [3456] (onde 3456 está sendo desarranjado).