O CAIXEIRO VIAJANTE QUE TEM DE VISITAR SEIS CIDADES IBÉRICAS  

Tarefa:
    Considerar os dois algoritmos (Algoritmo dos Mínimos Sucessivos e Algoritmo por Ordenação dos Pesos das Arestas) que referimos como executáveis para resolver PCVs, (PCV = Problema do Caixeiro Viajante ),  e aplique-os à situação do caixeiro viajante que tem de visitar as seguintes seis cidades ibéricas, referidas no seguinte grafo completo e pesado (distâncias em quilómetros).
    - As soluções que encontrou são boas?
    - Seria fácil encontrar a solução óptima?
    - Quanto tempo demoraria a encontrar a solução óptima por um método exaustivo? Compensaria?  

 Pelo  Algoritmo dos Mínimos Sucessivos:

             Vamos usar como ponto de partida cada uma das seis cidades :
 

 
 
     ---»  Portanto o melhor percurso é:  BEFCMAB, que corresponde a 2011 km.

Pelo Algoritmo por Ordenação dos Pesos das Arestas:

Começemos  por ordenar as 15 arestas do grafo completo, por ordem crescente de distância inter-vértices.

E99B    ;  E231F  ;  B269C  ;  C326F  ;   F331B  ;   A353E  ;  A372B  ;  M403B  ; 
M424C  ;   E426C  ;  M502E  ;  M559A  ;  A582F  ;  C641A  ;  F750M.  

Vamos escolher em cada etapa a aresta de mais baixo custo verificando as condições:

- nunca se tomam três arestas a incidir num vértice (um circuito de Hamilton usa exactamente duas arestas por vértice);
- nunca se fecha um circuito circular havendo vértices por visitar.

Assim, foram eliminadas as arestas:

    C326F ; F331B ;  A353E ; A372B  ; M403B ;  E426C ; M502E ; C641A ;  F750M .
 

 Obtivemos como resultado final;

        E99B    ;  E231F  ;  B269C  ;   M424C  ;  M559A  ;  A582F  .

Sugestão: Clique em cada uma das cidades para uma visita turística

Conclusão:

    A melhor solução foi encontrada pelo Algoritmo dos Mínimos Sucessivos, 2011 km. Considero que o percurso encontrado é uma solução óptima. Claro que para ter a certeza desta afirmação teria de encontrar todas as soluções pelo Método Exaustivo, o que implica a análise de 60 percursos, tarefa pouco aconselhável e nada compensatória !

Voltar à página principal