assembly calculator

UNIVERSIDADE CATÓLICA DO SALVADOR

CAIXEIRO VIAJANTE

EQUIPE:
AMARILIS DIAS
DANILO ASSIS
FÁBIO ROGÉRIO
IVANA ALCÂNTARA
LUISA BERNARDES

Salvador-BA

2011
Introdução

Muitas vezes, para resolver uma determinada situação problemática, temos tendência a fazer um esquema, ou um modelo, que nos facilite a organização das idéias. Com base nesses modelos, conseguimos visualizar melhor qual é a solução para o nosso problema ou definir uma estratégia para resolvê-lo.

Em muitas situações o tipo de modelos utilizados são grafos, que não são mais do que esquemas onde se utilizam pontos ligados por linhas conforme a relação que é estabelecida no problema.

Por exemplo, uma rede metropolitana pode ser esquematizada num grafo, onde os vértices representam as estações e, as linhas, as ligações existentes entre as mesmas. Assim, por exemplo, determinar a forma mais rápida de chegar de uma estação à outra corresponderia a determinar o caminho mais curto entre dois vértices de um grafo, através de algoritmos desenvolvidos na teoria de grafos. Os sistemas informáticos que controlam essas redes Metropolitanas são baseados em programas criados fazendo a analogia entre a rede e o grafo associado, utilizando estruturas próprias da linguagem da programação que permitem implementar esse grafo.

Caixeiro Viajante

O problema do caixeiro viajante se caracteriza por, dado um conjunto de n cidades e uma matriz de distancias, fazer com que seja encontrado um caminho que tenha a menos distancia em ser percorrida para que sejam visitadas todas as cidades passando uma única vez em cada cidade e retornando a cidade de origem.

Esse problema é considerado pelos matemáticos e cientistas da computação como sendo parte de uma classe de equivalência chamada NP-Completo de problemas difíceis onde não se conhece algoritmos que não se fornecem respostas em tempo polinomial.

Em 1954, Dantzig, Fulkerson e Johnson foram os