Algoritmo do vizinho mais próximo
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())); } }
Este artigo sobre programação de computadores é um esboço. Você pode ajudar a Wikipédia expandindo-o.
|