Problema do Caicheiro Viajante

Problema do Caixeiro Viajante

Descrição do Problema


Ciclo Hamiltaniano :
É um grafo completo
Se houver vértices que não são adjacentes, podemos introduzir as arestas em falta de forma a obter o grafo completo, e atribuir-lhes o peso +∞.
Assim, só serão aceitas soluções cujo peso seja finito. 

Árvore Geradora
Minima
Uma árvore geradora mínima é então uma árvore de extensão com peso menor ou igual a cada uma das outras árvores de extensão possíveis. Outros Exemplos
•rotas de autocarros escolares •redes de distribuição postal •construção de placas de circuitos integrados •programação de máquinas para realizar várias tarefas em sucessão

Tipos de Métodos
Métodos Exatos:
 Retornam a solução ótima do problema
 Tempo de execução muito alto

Complexidade:
NP-difícil

Métodos Heurísticos:
 Tempo de execução razoável  Não há garantias de se obter a melhor solução Método Exaustivo
É um método exato
Consiste em fazer uma lista de todos os ciclos
Hamiltonianos do grafo, calcular o peso de cada um e escolher um de peso mínimo
 Em um problema de n nós, existem (n-1)! caminhos diferentes 


Explicação do ultimo topico: Um caminho em Kn´e determinado por uma sequˆencia de v´ertices distintos. Para ser um ciclo Hamiltoniano, todos os v´ertices devem ocorrer na sequˆencia, e o ´ultimo v´ertice dever´a ser igual ao primeiro. Logo, existemn! sequˆencias distintas. No entanto, num ciclo n˜ao interessa qual ´e o v´ertice inicial, j´a que podemos come¸car em qualquer v´ertice. Assim, podemos fixar o v´ertice inicial e obtemos um total de (n−1)! ciclos
Hamiltonianos distintos emKn
2
Como n˜ao interessa o sentido em que o ciclo ´e percorrido, podemos identificar um ciclo com o seu ciclo inverso, obtendo ent˜ao um total de (n−1)!/2 ciclos Hamiltonianos emKn

Método do Vizinho Mais Próximo
Trata-se de uma heurística
Pertence á classe de algoritmo “guloso”
Escolhe-se um vértice e a aresta de menor