Algoritmo de vizinho mais próximo - Nearest neighbour algorithm

Algoritmo de vizinho mais próximo

Aula	Algoritmo de aproximação
Estrutura de dados	Gráfico
Desempenho de pior caso	${\ displaystyle \ Theta (N ^ {2})}$
Pior caso de complexidade de espaço	${\ displaystyle \ Theta (N)}$

O algoritmo do vizinho mais próximo foi um dos primeiros algoritmos usados ​​para resolver aproximadamente o problema do caixeiro viajante . Nesse problema, o vendedor começa em uma cidade aleatória e visita repetidamente a cidade mais próxima até que todas tenham sido visitadas. O algoritmo rapidamente produz um passeio curto, mas geralmente não é o ideal.

Algoritmo

Estas são as etapas do algoritmo:

1. Inicialize todos os vértices como não visitados.
2. Selecione um vértice arbitrário, defina-o como o vértice atual u . Marque você como visitado.
3. Descubra a aresta mais curta conectando o vértice atual u e um vértice não visitado v .
4. Defina v como o vértice atual u . Marque v como visitado.
5. Se todos os vértices do domínio forem visitados, encerre. Caso contrário, vá para a etapa 3.

A sequência dos vértices visitados é a saída do algoritmo.

O algoritmo do vizinho mais próximo é fácil de implementar e executa rapidamente, mas às vezes pode perder rotas mais curtas que são facilmente percebidas com a percepção humana, devido à sua natureza "gananciosa". Como um guia geral, se os últimos estágios do passeio forem comparáveis ​​em duração aos primeiros estágios, então o passeio é razoável; se forem muito maiores, é provável que existam tours muito melhores. Outra verificação é usar um algoritmo como o algoritmo de limite inferior para estimar se esse passeio é bom o suficiente.

No pior caso, o algoritmo resulta em um passeio muito mais longo do que o passeio ideal. Para ser mais preciso, para cada constante r existe uma instância do problema do caixeiro-viajante tal que a duração da viagem calculada pelo algoritmo do vizinho mais próximo é maior do que r vezes a duração da viagem ótima. Além disso, para cada número de cidades, há uma atribuição de distâncias entre as cidades para as quais a heurística do vizinho mais próximo produz o pior trajeto único possível. (Se o algoritmo for aplicado em cada vértice como o vértice inicial, o melhor caminho encontrado será melhor do que pelo menos N / 2-1 outros passeios, onde N é o número de vértices.)

O algoritmo do vizinho mais próximo pode não encontrar um roteiro viável, mesmo quando existe um.

Notas

Referências

• G. Gutin, A. Yeo e A. Zverovitch, vizinhanças exponenciais e análise de dominação para o TSP, em O problema do caixeiro viajante e suas variações, G. Gutin e AP Punnen (eds.), Kluwer (2002) e Springer (2007) .
• G. Gutin, A. Yeo e A. Zverovich, O caixeiro viajante não deve ser ganancioso: análise de dominação de heurísticas do tipo ganancioso para o TSP . Discrete Applied Mathematics 117 (2002), 81–86.
• J. Bang-Jensen, G. Gutin e A. Yeo, Quando o algoritmo ganancioso falha . Discrete Optimization 1 (2004), 121-127.
• G. Bendall e F. Margot, Greedy Type Resistance of Combinatorial Problems , Discrete Optimization 3 (2006), 288-298.