Num grafo, chama-se circuito de Hamilton a um caminho que começa e acaba no mesmo vértice, passando por todos os vértices uma única vez.
Algoritmo do vizinho mais próximo
1)Define-se o vértice de partida.
2)Segue-se para o vértice mais próximo (de menor peso) que ainda não tenha sido visitado (devemos ter em conta que se houver 2 vértices com o mesmo peso, a escolha é aleatória).
3)Só se pode fechar o circuito quando todos os vértices tiverem sido visitados.
Algoritmo do peso das arestas
1)Ordenam-se as arestas pelos seus pesos.
2)Escolhem-se sucessivamente as arestas de menor peso que verifiquem as seguintes condições: um vértice nunca poderá aparecer 3 vezes e nunca se fecha um circuito havendo vértices por visitar.
3)Ordena-se a solução conforme o vértice de partida escolhido.
Sem comentários:
Enviar um comentário