O algoritmo de inserção mais próximo

O algoritmo de inserção mais próximo é um algoritmo heurístico usado para encontrar uma solução aproximada para o problema do vendedor ambulante (TSP). O TSP visa encontrar a rota mais curta possível que visita cada cidade (nó) exatamente uma vez e retorna à cidade inicial.

como funciona:

1. Inicialização:
- Comece com um nó arbitrário como o tour inicial (por exemplo, um loop de nó único). Vamos chamar esse nó `start_node`.
- Seja `v` o conjunto de nós que ainda não foram adicionados à turnê.

2. iteração:
- Encontre o nó mais próximo: Para cada nó `i` na turnê atual, encontre o nó` j` em `v` (o conjunto de nós não visitados) que é mais próximo de` i` (ou seja, tem a menor distância). Este nó "mais próximo" `j` é o que queremos inserir. Matematicamente, estamos encontrando:

`j =argmin_ {v ∈ V} min_ {i ∈ Tour} dist (i, v)`

- Insira o nó mais próximo: Encontre a borda (i, k) na turnê atual, onde a inserção do nó `j` entre nós` i` e `k` resulta no menor aumento no comprimento da excursão. Isto é, encontre `i` e` k 'tais:

`dist (i, j) + dist (j, k) - dist (i, k)` é minimizado.

- Insira o nó `j` entre nós` i` e `k`, substituindo efetivamente a borda (i, k) por duas bordas (i, j) e (j, k).
- Remova o nó `j` do conjunto de nós não visitados` v`.

3. terminação:
- Repita a etapa 2 até que todos os nós tenham sido adicionados ao passeio (ou seja, `v` está vazio).

4. fechando o loop:
- Conecte o último nó adicionado ao passeio de volta ao `start_node` para concluir o ciclo.

Exemplo:

Digamos que temos cidades A, B, C, D e E com as seguintes distâncias:

`` `
A B C D E
A 0 10 15 20 25
B 10 0 35 25 30
C 15 35 0 30 20
D 20 25 30 0 0 10
E 25 30 20 10 0
`` `

1. Iniciar: Vamos começar com o nó A como o tour inicial:`tour ={a}`

2. iteração 1:
- O nó mais próximo de A é B (distância 10).
-Insira B no passeio (A -> B -> A). `Tour ={a, b, a}`

3. iteração 2:
- Encontre o nó não visitado mais próximo para qualquer nó no passeio atual:
- mais próximo de A:C (15), D (20), E (25)
- mais próximo de B:C (35), D (25), E (30)
- O mínimo dessas distâncias é 15 (A a C).
- Descubra onde inserir C.
- Inserindo C entre A e B:15 + 35 - 10 =40
- Inserindo C entre B e A:35 + 15 - 10 =40
- Insira C entre A e B (ou B e A). `Tour ={a, c, b, a}`

4. iteração 3:
- Encontre o nó não visitado mais próximo:
- mais próximo de A:D (20), E (25)
- mais próximo de C:D (30), E (20)
- mais próximo de B:D (25), E (30)
- A distância mínima é 20 (C a E ou A a D). Vamos levar C para E.
- Inserir e:
- Inserindo E entre A e C:25 + 20 - 15 =30
- Inserindo E entre C e B:20 ​​+ 30 - 35 =15 (mínimo!)
- Inserindo E entre B e A:30 + 25 - 10 =45
- Insira e entre C e B. `Tour ={A, C, E, B, A}`

5. iteração 4:
- Somente o nó D permanece.
- mais próximo de A:D (20)
- mais próximo de C:D (30)
- mais próximo de E:D (10) (mínimo!)
- mais próximo de B:D (25)
- Insira D:
- Inserindo d entre A e C:20 + 30 - 15 =35
- Inserindo d entre C e E:30 + 10 - 20 =20
- Inserindo d entre E e B:10 + 25 - 30 =5 (mínimo!)
- Inserindo d entre B e A:25 + 20 - 10 =35
- Insira d entre E e B. `Tour ={A, C, E, D, B, A}`

Otimização (ou melhor, aproximação) aspectos:

O algoritmo de inserção mais próximo otimiza, adicionando iterativamente o nó que introduz o menor aumento imediato no comprimento total do passeio em cada etapa. Essa é uma abordagem gananciosa, o que significa que faz a melhor escolha em cada estágio sem considerar o impacto global dessa escolha.

* Localidade: O algoritmo se concentra em minimizar as distâncias locais. Ele seleciona o nó mais próximo do passeio atual, com o objetivo de manter o segmento adicionado do passeio o mais curto possível.

* Crescimento incremental: O passeio é construído de forma incremental adicionando um nó por vez. Cada decisão de inserção é baseada no estado atual da turnê, por isso não planeja ver como a adição de um nó específico pode afetar as inserções futuras.

Limitações:

* não é ideal: O algoritmo de inserção mais próximo é uma heurística, o que significa que não garante a rota mais curta absoluta. Ele pode ficar preso nos ótimos locais, onde uma escolha inicial ligeiramente diferente pode levar a uma solução geral significativamente melhor.

* natureza gananciosa: A natureza gananciosa do algoritmo pode levar a escolhas abaixo do ideal, especialmente nos casos em que as distâncias não são uniformes. Às vezes, escolher um nó um pouco mais distante pode abrir oportunidades para conexões mais curtas mais tarde.

* Dependência do nó inicial: O nó inicial pode afetar o passeio final. Diferentes nós de partida podem resultar em rotas diferentes.

Vantagens:

* Simples de implementar: É relativamente fácil de entender e implementar.

* rápido: Geralmente é mais rápido que os algoritmos que garantem soluções ideais (como pesquisa de força bruta). A complexidade do tempo é tipicamente O (n^2), onde n é o número de nós.

* Aproximação razoável: Geralmente, fornece uma aproximação razoavelmente boa do tour ideal de TSP, especialmente quando as distâncias satisfazem a desigualdade do triângulo (ou seja, a distância direta entre dois pontos é sempre menor ou igual à soma das distâncias ao longo de qualquer outro caminho).

em resumo:

O algoritmo de inserção mais próximo é uma heurística gananciosa que constrói uma turnê de TSP, adicionando repetidamente o nó não visitado mais próximo à turnê existente. Embora não seja garantido para produzir a solução ideal, é uma maneira rápida e simples de encontrar uma aproximação razoavelmente boa. Ele se concentra em minimizar os aumentos de distância local em cada etapa.