Problema do Caixeiro-Viajante

Prévia do material em texto

Quatro cidades de partida possíveis, com seis rotas possíveis para cada
cidade de partida = 4 * 6 = 24 rotas possíveis.
Percebe o padrão? Cada vez que uma cidade é adicionada, o número de
rotas que devem ser calculadas aumenta.
Quantas rotas possíveis existem para seis cidades? Se você disse 720, está
certo. Além disso, existem 5.040 rotas para sete cidades e 40.320 para oito
cidades.
Isso é chamado de função fatorial (Você se lembra de ter lido sobre isso no
Capítulo 3?). Então 5! = 120. Suponha que você tenha dez cidades. Quantas
rotas possíveis existem? 10! = 3.628.800. Devem-se calcular perto de 3
milhões de rotas possíveis para dez cidades. Como você pode notar, o
número de rotas possíveis cresce rapidamente! É por isso que é impossível
calcular a solução “correta” para o problema do caixeiro-viajante caso o
número de cidades seja muito elevado.
Tanto o problema do caixeiro-viajante quanto o problema da cobertura de