Exercicio

7.9. Exercício de Implementação O primeiro passo para irmos de encontro a uma "solução" para problemas complexos, é você ganhar um "feeling" para estes problemas.

Para poder ter uma noção de o que significa resolver um problema complexo, nós vamos implementar o problema do caixeiro viajante, que todos vimos em Teoria dos Grafos, e observar o seu comportamento no tempo:

Para a solução do Problema do Caixeiro Viajante existem muitos algoritmos, dentre eles o "Método Algébrico de Christofides", o Algoritmo de Rubin e o Algoritmo de Roberts e Flores. O mais interessante é o de Roberts e Flores pois pode ser implementado de forma recursiva bastante simples em uma linguagem como Prolog. Podemos também implementá-lo em "C" ou Pascal sem muitos problemas.

Exercício 2.1 (prazo: 2 semanas):

• Implemente o Problema do Caixeiro Viajante usando um algoritmo de sua escolha e uma linguagem de sua escolha.
• Calcule o Ciclo de Menor Custo para os grafos abaixo, observando o tempo de execução para cada um deles.
• Plote o tempo de execução em uma curva, mostrando o comportamento assintótico deste algoritmo com relação a: a) o número de vértices do grafo, b) o número de arestas do grafo. Para isso você pode utilizar uma função de plotagem de alguma planilha que você use ou o programa Gnuplot.
• Qual a complexidade de tempo aproximada do algoritmo para n=número de vértices ? E para n=número de arestas ?

• Além dos grafos acima, rode o programa também para:
  - Um grafo de 7 vértices,
  - um grafo de 10 vértices,
  - um grafo de 15 vértices e
  - um grafo 20 vértices
  onde os custos das arestas são valores aleatórios entre 5 e 30.

Exercício 2.2 (prazo: 2 semanas):

Torres de Hanoi

Este é um jogo milenar consistindo de três pinos e de um conjunto variável de discos, todos de tamanhos diferentes. Inicialmente os discos estão empilhados em um extremo, o maior embaixo, o menor em cima. O objetivo é colocar todos os discos no outro lado do tabuleiro, na mesma ordem, seguindo as seguintes regras:

• Um único disco pode ser movido diretamente, saltando por cima do pino do meio;
• N discos podem ser movidos em três passos:
• Mova N - 1 discos para o pino do meio,
• Mova o último disco diretamente para o pino da direita,
• Mova os N - 1 discos do pino do meio para o da direita.

O único prerequisito é que nunca um disco maior poderá estar sobre um menor.

Resolva este exercício da mesma forma que o anterios, implementando-o (pesquise na literatura - o mais simples é usar Prolog), rodando-o para 2,3,4,5,10,15,20,30 e 50 discos e plotando o sresultados em uma curva. Identifique a complexidade do problema justificando.