Circuitos de Hamilton pesados
e as dificuldades da solução óptima (8)

Voltemos então ao problema do caixeiro viajante, no caso do gestor de vendas de 10 cidades que procura o caminho mais curto para visitar as cidades. Dado que o modelo é um grafo completo e há circuitos de Hamilton, o gestor pode pensar que é fácil fazer o planeamento da sua viagem pelas 10 cidades: bastaria para isso determinar todos os circuitos possíveis e depois escolher aquele correspondente à menor quilometragem. Antes de começar a fazer a lista dos circuitos possíveis, decidiu fazer o cálculo do número de circuitos. E começou a ficar desesperado.

Quantos são afinal os circuitos?

O gestor de vendas chegou à conclusão que fazer a lista de todos os circuitos de Hamilton possíveis é impraticável, senão praticamente impossível.

Mas ele procura de entre os circuitos de Hamilton aqueles que têm menor quilometragem. Não está em causa percorrer o menor número de arestas simplesmente (aliás o número de arestas a percorrer sobre um grafo completo qualquer é sempre o mesmo qualquer que seja o circuito hamiltoniano escolhido). Passa a ter importância o peso de cada aresta.... no caso, as distâncias quilométricas entre as cidades (vértices).

 

 No exemplo ao lado, no grafo G = (V, A) em que V= {A,B,C,D, E} e A = {AB, AC, AD, AE, BC, BD, BE, CD, CE, DE}, o peso de AB é 418 ( a distância da cidade A à cidade B é 418 km), o peso de AC é 592, de AD é 302, de AE é 607, de BC é 415, de BD é 427, de BE é 613, de CD é 581, de CE é 583 e de DE é 609.

(Reparem que nestes modelos não nos preocupamos com qulaquer escala a relacionar os comprimentos das arestas com os seus pesos)

Ao lado, temos uma representação para um problema do caixeiro viajante envolvendo cinco cidades.

O número de cirucitos hamiltonianos diferentes possíveis para este problema, começando e acabando num dado vértice, é
4x3 =12.
 
De um modo geral, sobre um grafo de n vértices, o número de circuitos de pesos diferentes é
(n-1)(n-2)...4x3

(Para vinte e cinco cidades, um computador, que liste e calcule o peso total de 1 milhão de circuitos por segundo, gasta 10 mil anos para gerar os cerca de 3x10^23 (3 seguido de 23 zeros) circuitos diferentes:
24!/2 = 310 224 200 866 619 719 680 000 segundos se efectuasse um por segundo;
como efectua um milhão por segundo, demora 310224200719,680000 segundos, que, em horas dá 310224200719,680000/3600 ~ 86173389,0888
aproximadamente 3590560 dias ou 9837,15 anos).
Como se pode ver, para problemas de certa dimensão, não é praticável procurar uma solução óptima em absoluto.. em termos de tempo ou em termos de custos.
 
Foi, por isso, necessário inventar algoritmos que façam o trabalho rapidamente (em tempo útil), ainda muitas vezes só com papel e lápis, e cujo resultado, se não for a solução óptima ou o caminho mais curto no caso, há-de estar perto dela o bastante para ser uma solução prática, possível, económica, viável e vantajosa. Estes algoritmos, que não dão garantias de encontrar uma solução óptima, são chamados algoritmos grosseiros, heurísticos,....


voltar ao sumário