Problema do Caixeiro Viajante - Exercício Computacional 6
Observações:
1. Os arquivos ncit*.dat são fornecidos com a seguinte configuração: na primeira linha é apresentado o número de cidades, e nas linhas seguintes, as coordenadas (x,y) de cada cidade. A ordem de apresentação das coordenadas das cidades nos arquivos ncit*.dat é arbitrária. Percorrendo as cidades nesta ordem, a distância resultante é maior que a distância mínima possível.
2. O objetivo é encontrar uma ordenação de tal modo que, uma vez percorrendo as cidades nesta ordem, a distância resultante seja mínima.
3. Não esquecer de contabilizar também o caminho de retorno da última cidade para a primeira.
4. Com a ordenação atual, a distância para percorrer as cidades, na seqüência, apresenta os seguintes valores:
5. As distâncias ótimas conhecidas para os três casos são dadas a seguir:
6. Estas soluções ótimas devem servir apenas para indicar o quão próxima do ótimo se encontra uma solução fornecida pelo seu algoritmo. De forma alguma estes valores ótimos devem ser utilizados para obter o fitness de um candidato a solução ou direcionar de algum modo o processo de evolução. Ou seja, estes valores ótimos não podem estar presentes no código de seu programa.
7. Não existe nenhuma relação direta entre os três problemas. Por exemplo, as 30 cidades presentes em ncit30.dat não representam um subconjunto das 100 cidades de ncit100.dat.