Heurística de Inserção em Grafos na resolução do Problema do Caixeiro Viajante Critérios: mais próximo, mais distante e randômico Implementação e Testes

Diego Gomes Tomé* Francisca Fabiana Pereira da Silva** Francisco Bruno Filgueiras***

RESUMO
Este trabalho tem como objetivo mostrar a resolução do problema caixeiro viajante através da heurística de inserção em grafos. O problema do caixeiro viajante consiste em determinar num grafo ponderado, um ciclo hamiltoniano de custo mínimo. Na implementação do …exibir mais conteúdo…

Forme um novo ciclo com o vértice incluso e retorne a etapa-b até K=V.
Exemplo:
1.3 Heurística de inserção mais próximo
Seja G = (V, E), um grafo completo como na figura 1: O ciclo inicial é: C = {1, 3, 4, 1} com custo inicial Custo(C) = 22.
Iteração 1:

Vértice mais próximo do ciclo é: 5.

Temos 3 inserções possíveis:
•