miniaturadaimagem|Exemplo de aplicação do Algoritmo do Vizinho mais Próximo, na resolução de um problema, utilizando sete cidades. Ajuda 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: escolha um vértice arbitrário como vértice atual. descubra a aresta de menor peso que seja conectada ao vértice atual e a um vértice não visitado V. faça o vértice atual ser V. marque V como visitado. se todos os vértices no domínio estiverem visitados, encerre o algoritmo. 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 os últimos passos do percurso são comparáveis em comprimento aos dos primeiros passos, o percurso é razoável; se eles são muito maiores, então é provável que existam percursos bem melhores.
Exemplo de código fonte Exemplo simples em Java do algoritmo do vizinho mais próximo para encontrar o caminho mais curto em um grafo completo.import java.util.ArrayList; import java.util.Arrays; import java.util.List;
public class NearestNeighbour {
private int[][] graph; private int numNodes; private List<Integer> path;
public NearestNeighbour(int[][] graph) { this.graph = graph; this.numNodes = graph.length; this.path = new ArrayList<>();
public List<Integer> getShortestPath(int startNode) { // Adiciona o nó inicial ao caminho path.add(startNode);
// Enquanto não visitou todos os nós while (path.size() < numNodes) { // Seleciona o vizinho mais próximo int currentNode = path.get(path.size() - 1); int nextNode = getNearestNeighbour(currentNode);
// Adiciona o vizinho mais próximo ao caminho path.add(nextNode);
// Adiciona o nó inicial novamente para fechar o caminho path.add(startNode);
return path;
private int getNearestNeighbour(int node) { int nearestNeighbour = -1; int shortestDistance = Integer.MAX_VALUE;
// Procura o vizinho mais próximo não visitado for (int i = 0; i < numNodes; i++) { if (i != node && !path.contains(i) && graph[node][i] < shortestDistance) { nearestNeighbour = i; shortestDistance = graph[node][i];
return nearestNeighbour;
public static void main(String[] args) { // Grafo completo com pesos int[][] graph = { {0, 2, 9, 10}, {2, 0, 6, 4}, {9, 6, 0, 8}, {10, 4, 8, 0}
// Cria o objeto do algoritmo NearestNeighbour nn = new NearestNeighbour(graph);
// Encontra o caminho mais curto a partir do nó 0 List<Integer> shortestPath = nn.getShortestPath(0);
// Imprime o caminho mais curto System.out.println("Caminho mais curto: " + Arrays.toString(shortestPath.toArray()));
Categoria:Algoritmos de grafos Categoria:Algoritmos de aproximação