Algoritmo vizinho mais próximo
estes são os passos do algoritmo:
- inicializar todos os vértices como não convidados.
- seleccione um vértice arbitrário, configure-o como o vértice actual U. Marca u como visitado.
- Descubra a aresta mais curta que liga o vértice u actual e um vértice v.
- define v como o vértice actual U. Marca v como visitado.
- Se todos os vértices do domínio são visitados, então terminar. Senão, vai para o Passo 3.
A sequência dos vértices visitados é a saída do algoritmo.,
o algoritmo vizinho mais próximo é fácil de implementar e executar rapidamente, mas às vezes pode perder rotas mais curtas que são facilmente notadas com o insight humano, devido à sua natureza “gananciosa”. Como um guia geral, se as últimas etapas da turnê são comparáveis em comprimento às primeiras etapas, então a turnê é razoável; se eles são muito maiores, então é provável que excursões muito melhores existem. Outra verificação é usar um algoritmo como o algoritmo de limite inferior para estimar se esta turnê é boa o suficiente.,
no pior caso, o algoritmo resulta em uma turnê que é muito mais longa do que a turnê ideal. Para ser preciso, para cada constante R há uma instância do problema do caixeiro viajante tal que a duração da turnê calculada pelo algoritmo vizinho mais próximo é maior do que R vezes o comprimento da turnê ideal. Além disso, para cada número de cidades há uma atribuição de distâncias entre as cidades para as quais o vizinho heuristic mais próximo produz o único pior passeio possível., (If the algorithm is applied on every vertex as the starting vertex, the best path found will be better than at least n / 2-1 other tours, where N is the number of vertices.)
O algoritmo vizinho mais próximo pode não encontrar um tour viável, mesmo quando existe.