Problema — Volta ao redor do mundo
Em 1856, William Hamilton apresentou um famoso desafio geométrico: em um dodecaedro com 20 vértices, cada um associado a uma cidade diferente, deve-se traçar um percurso ao longo das arestas que passe por todas as cidades uma única vez, retornando ao vértice inicial.
Por que o problema é difícil na prática?
À primeira vista, o problema do ciclo hamiltoniano parece simples: encontrar um percurso que visite cada vértice exatamente uma vez e retorne ao ponto inicial. Na prática, porém, esse problema se torna computacionalmente difícil.
A principal dificuldade está no fato de que não se conhece nenhum algoritmo eficiente que resolva o problema do ciclo hamiltoniano para todos os grafos. O número de possíveis ordens em que os vértices podem ser visitados cresce de forma fatorial: para um grafo com \(n\) vértices, existem até \(n!\) permutações a serem consideradas no pior caso.
Mesmo utilizando técnicas de poda, backtracking e heurísticas, o espaço de busca cresce de forma explosiva. Um grafo com apenas 20 vértices já possui mais de \(2{,}4 \times 10^{18}\) possíveis sequências de visita, o que torna inviável qualquer abordagem por força bruta.
Essa explosão combinatória explica por que problemas hamiltonianos ocupam um papel central na teoria da complexidade computacional, sendo exemplos clássicos de problemas NP-completos. Verificar se um percurso é hamiltoniano é fácil; encontrar um, por outro lado, pode exigir a exploração de um número exponencial de possibilidades.
Na prática, isso significa que soluções exatas só são viáveis para grafos pequenos ou muito estruturados. Para instâncias maiores, algoritmos recorrem a heurísticas, aproximações ou conhecimento específico do problema, abrindo mão de garantias absolutas de eficiência.