Algoritmo do vizinho mais próximo

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:

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 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()));
    }
}