O caixeiro-viajante

Circuito hamiltoniano

Nos grafos de Euler queríamos percorrer todas as arestas (ruas) uma só vez. Agora o objetivo é outro: visitar todos os vértices (locais) uma só vez, como um entregador que tem de passar por todos os clientes.

Repara na diferença: num circuito de Euler podes passar várias vezes no mesmo vértice, mas nunca repetes uma aresta. Num circuito hamiltoniano, cada vértice aparece uma só vez (o de partida é o único que se repete, no fim), e não é obrigatório usar todas as arestas.

O circuito destacado é $R \to S \to T \to U \to V \to R$. A aresta $RT$ existe no grafo, mas o circuito não precisa dela.

Quando existe um circuito hamiltoniano?

Para Euler há um critério simples (graus pares e grafo conexo). Para Hamilton não existe um critério simples que funcione sempre. O que temos são condições fáceis de verificar.

A razão é simples: num circuito, cada vértice é «entrado» por uma aresta e «saído» por outra. Um vértice com grau 1 (uma única aresta) não consegue ser atravessado e regressar ao início.

Os mapas de estradas entre cidades costumam ser quase completos, por isso o problema aparece sempre com muitas soluções possíveis.

O problema do caixeiro-viajante

Voltemos à Rita. Os locais são vértices; as estradas entre eles são arestas com um peso, a distância em quilómetros. Num grafo ponderado como este, queremos um circuito hamiltoniano de peso total mínimo. Este é o problema do caixeiro-viajante: visitar todos os locais uma só vez, voltar ao início e gastar o menos possível (quilómetros, combustível, dinheiro).

Seja $A$ a pastelaria e $B$, $C$ e $D$ os três cafés. As distâncias, em km, estão na figura.

Com 3 cafés, partindo de $A$, há $3 \times 2 \times 1 = 6$ ordens possíveis: três escolhas para o primeiro café, duas para o segundo, uma para o último. Organizamo-las numa árvore (cada ramo é uma escolha) e somamos os pesos ao longo de cada caminho, sem esquecer a viagem de volta a $A$.

O mínimo é 18 km, com $A \to B \to D \to C \to A$ (ou o mesmo percurso em sentido contrário, $A \to C \to D \to B \to A$). Repara que cada percurso aparece duas vezes, uma em cada sentido, com o mesmo total.

Um algoritmo: o vizinho mais próximo

Quando há muitos vértices, listar tudo é impraticável. Usamos um algoritmo: uma sequência de decisões passo a passo que dá sempre uma solução. O mais simples é o método do vizinho mais próximo.

O algoritmo é rápido, mas nem sempre dá o melhor percurso: escolher o mais barato em cada passo pode obrigar a uma viagem de regresso muito longa. Dá uma solução aceitável, que podes comparar com a ótima quando conseguires listar todas as possibilidades. Aqui o algoritmo dá 23 km e o ótimo é 18 km.

Voltando à Rita: com a árvore, ela descobre que o melhor percurso é $A \to B \to D \to C \to A$, com 18 km; o vizinho mais próximo daria 23 km, mais 5 km por dia.

Em resumo

• Um circuito hamiltoniano passa por todos os vértices uma só vez e regressa ao início; não tem de usar todas as arestas (diferente de Euler).

• Não há critério simples para a sua existência. Condição necessária: todos os vértices com grau ≥ 2. Um grafo completo com 3 ou mais vértices tem sempre circuito hamiltoniano.

• No problema do caixeiro-viajante, num grafo ponderado procura-se o circuito hamiltoniano de menor peso total (não esquecer a aresta de regresso).

• A árvore lista todos os percursos: partindo de um vértice, num grafo completo com $n$ vértices há $(n-1)!$. Soma-se o peso de cada um e compara-se.

• O vizinho mais próximo é um algoritmo rápido: em cada passo vai-se para o vértice não visitado mais próximo e no fim regressa-se. Dá uma solução aceitável, nem sempre a ótima.