Algoritmo do vizinho mais próximo

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

O algoritmo do vizinho mais próximo foi, na ciência da computação, um dos primeiros algoritmos utilizados para determinar uma solução para o problema do problema do caixeiro viajante. Ele gera rapidamente um caminho curto, mas geralmente não o ideal.


Abaixo está a aplicação do algoritmo do vizinho mais próximo ao problema do caixeiro viajante.

Estes são os passos do algoritmo:

  1. escolha um vértice arbitrário como vértice atual.
  2. descubra a aresta de menor peso que seja conectada ao vértice atual e a um vértice não visitado V.
  3. faça o vértice atual ser V.
  4. marque V como visitado.
  5. se todos os vértices no domínio estiverem visitados, encerre o algoritmo.
  6. Se não vá para o passo 2.

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

O algoritmo do 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 a visão humana, devido à sua natureza "gananciosa". Como um guia geral, se as últimos passos do percurso são comparáveis em comprimento ao dos primeiros passos, o percurso é razoável; se eles são muito maiores, então é provável que existam percursos bem melhores.


Ícone de esboço Este artigo sobre programação de computadores é um esboço. Você pode ajudar a Wikipédia expandindo-o.