O Caixeiro Viajante

FASAM - FACULDADE SUL AMERICANA

Bacharel em Sistemas de informação

3º Semestre

TEORIA DA COMPUTAÇÃO

SIVALDO PEREIRA DE OLIVEIRA DOS SANTOS

Professora: Dianne  Silva

GOIÂNIA, 26 DE SETEMBRO 2016

Problema do Caixeiro Viajante

        O problema do caixeiro-viajante consiste na procura de um circuito que possua a menor distância, começando numa qualquer cidade, entre várias, visitando cada cidade precisamente uma vez e regressando à cidade inicial.

Existem basicamente duas formas:

Métodos exatos

        Basicamente, analisam todas as alternativas possíveis. A complexidade é fatorial! Por isto, os métodos mais usados são os do tipo ”branch-and-bound”.

 Estes, consistem em expandir os nós e cortar caminhos de pesquisa que não são promissores.

Métodos heurísticos

Com base em heurísticas é possível encontrar soluções aproximadas, isto é, não são soluções exatas mas fornecem um resultado satisfatório em tempo hábil. Os métodos exatos não retornam solução alguma para um número de cidades maior do que 14 ou 15.

Métodos heurísticos

Algumas técnicas

Basicamente, técnicas de inteligência artificial

Métodos de busca heurística (algoritmo guloso)

Métodos de computação bioinspirada

Algoritmos genéticos

Colônia de formigas

Circuito hamiltoniano

        

        É um caminho que permite passar por todos os vértices de um grafo G, não repetindo nenhum, ou, seja, passar por todos uma e uma só vez por cada.

         Caso esse caminho seja possível descrever um ciclo, este é denominado circuito hamiltoniano.

        Em 2009 conseguiu-se uma resolução para este problema utilizando-se de bactérias[1] na implementação do algoritmo.

        ”Cientistas americanos criaram uma espécie de computador vivo, produzido com a bactéria Escherichia coli, uma das mais antigas bactérias presentes no intestino do homem. O resultado foi uma máquina que resolve problemas matemáticos com velocidade maior do que a de um PC que leve um processador de silício.”

        Os circuitos hamiltonianos tem este nome em homenagem ao matemático irlandês William Hamilton, que estudou este problema no grafo determinado pelas arestas de um dodecaedro regular (sólido platônico).

Roteamento de veículos

Consiste no atendimento de um conjunto de consumidores por intermédio de uma frota de veículos, que partem de um ou mais pontos denominados depósitos.

Cada veículo v possui uma capacidade C e o somatório das demandas dos consumidores não pode ultrapassar C{v}.

Apesar do seu enunciado relativamente simples, apresenta elevada complexidade computacional.