54. A via mais curta

   Já anteriormente, no artigo Pontes e grafos, se falou em grafos e como eles  permitem resolver situações complexas por apenas se concentrarem nos aspetos mais importantes da questão. Eis algumas outras situações em que os grafos são usados para encontrar a melhor solução. Imagine-se uma região que tem 4 localidades (A, B, C, D). Cada aresta representa uma estrada entre as localidades (há 6 estradas no total). Pretende-se encontrar a forma de passar por todas as cidades apenas uma vez (por exemplo, um serviço de carteiro, para distribuir cartas) e voltar à cidade de partida. Qual seria o caminho mais curto?

   Este tipo de situação é o que se chama um circuito de Hamilton, em honra do Matemático William Hamilton (1805-1865) que descreveu esta situação numa carta a um amigo. Hamilton chegou a inventar um jogo, o Jogo de Hamilton, jogado num tabuleiro com a forma da planificação de um dodecaedro em que cada jogador tem de percorrer todos os pontos do tabuleiro uma única vez e voltar ao ponto de origem. Não pode percorrer mais do que uma vez qualquer aresta nem repetir qualquer vértice, mas pode não percorrer todas as arestas. O objetivo do jogo é somente passar por todos os pontos uma só vez. Este é um circuito de Hamilton.

   Mas o que se pretende aqui é percorrer todos os vértices mas da forma mais económica possível, uma vez que cada aresta tem um peso diferente (neste caso distância, podia ser tempo, custo, …). Este tipo de problema é chamado de Problema do caixeiro viajante. Infelizmente não há uma forma de encontrar sempre o caminho mais curto o mais rapidamente possível. A única forma de encontrar sempre a forma mais curta de percorrer todos os pontos é fazer uma lista de todos os circuitos possíveis, somar o peso de cada aresta e ver qual é o mais curto. No caso do exemplo inicial, todos os circuitos de Hamilton existentes são estes: (comecei arbitrariamente por B. Começando por qualquer outro ponto os resultados seriam iguais, uma vez que todos estão listados): B – C – D – A – B 12 + 7 + 15 + 25 = 59 km; B – C – A – D – B → 12 + 18 + 15 + 8 = 53 km; B – D – B – C – B → 8 + 7 + 18 + 25 = 58 kmB – D – C – B – B → 8 + 15 + 18 + 12 = 53 km; B – A – D – C – B → 25 + 15 + 7 + 12 = 59 km; B – A – C – D – B → 25 + 18 + 7 + 8 = 58 km.

   Este caso é bastante simples e é possível listar todas as possibilidades. Mas infelizmente o número de possibilidades cresce muito rapidamente à medida que aumenta o número de vértices. Suponhamos que o grafo tiver 4 vértices, o número de circuitos diferentes é 3×2×1 / 2 = 3. Se o grafo tiver 5 vértices, o número de circuitos diferentes é 4×3×2×1 / 2 = 12. Se o grafo tiver 6 vértices, o número de circuitos diferente é 5×4×3×2×1 / 2 = 60. Se o grafo tiver 10 vértices, o número de circuitos diferente é 9×8×7×6×5×4×3×2×1 / 2 = 181 440. De forma geral, se o grafo tem n vértices, o número de circuitos diferentes é (n – 1)! / 2. O símbolo «!» significa que se multiplica o número por todos os números inteiros menores do que ele até 1 (5! = 5×4×3×2×1 = 120). Até 5 vértices, ainda se pode pensar em listar todos os circuitos e ver qual é o mais curto. Mas, a partir de 6, (360 circuitos diferentes) torna-se difícil fazê-lo (à mão).

   Há alguns métodos para procurar encontrar o caminho mais curto (nenhum infalível e quando dão uma solução nem sempre é a mais curta, pode ser só uma solução que não é muito longe da ideal). Um deles é listar as arestas por ordem crescente de arestas, depois escolher um ponto de partida, e seguidamente começar a escolher as arestas mais curtas que se ligam ao pontos a que se chega. Por exemplo, no grafo ao lado, qual é o caminho mais curto que passa por todos os pontos e volta ao inicial? DE mede 7 km; AE mede 8 km; AD mede 12 km; BC mede 14 km; BE mede 18 km; CE mede 19 km; DC mede 25 km; AB mede 37 km. Começando pelo ponto A, a aresta mais curta que se liga a A é AE (8); a aresta mais curta que liga E a um ponto livre é DE (7); a aresta mais curta que liga D a um ponto livre é DC (25); a aresta mais curta que liga C a um ponto livre é BC (14). Todos os pontos já foram percorridos e só falta regressar a A com AB (37). Obtém-se o circuito A – E – D – C – B – A. No total, o trajecto tem um comprimento de 8+7+25+14+37 = 91 km.

   A situação é também diferente no caso em que o que se pretende ligar entre as cidades não são estradas mas electricidade, ou gás, ou água ou computadores,… redes de coisas que bastam ter uma ligação a um ponto da rede para estarem ligados.  No caso destas 4 cidades, para se viajar por todos os ponto teria de se contornar o quadrado (A-B-C-D), resultando num circuito de comprimento 5 + 9 + 10 + 2 = 26. Mas, para ligar em rede, bastava ligar A-B (5) ; A-C (7) ; C-D (2), resultando num comprimento de 5 + 7 + 2 = 14. Para se encontrar a melhor rede nestes casos (que, mais uma vez, pode não resultar sempre na melhor rede, mas nunca fica longe dela) será listar todas as arestas por ordem crescente de comprimento, escolher o ponto inicial e ligar as arestas mais curtas que unam pontos já na rede que se está a construir a outros que não estejam. Neste caso, AD 2; AB 5; AC 7; BC 9; DC 10. Começando por A, a aresta mais curta que liga A a um ponto livre é AB (5); a aresta mais curta que liga um ponto já escolhido (A ou B) a um livre é AC (7); a aresta mais curta que liga um ponto já escolhido (A ou B ou C) a um livre é CD (2). A rede mais curta é então D – C – A – B, que tem 5 + 7 + 2 = 14 de comprimento. E assim, com poucas contas, se consegue encontrar o caminho mais curto para uma viagem de férias, ou a forma mais económica de fazer uma rede de computadores em casa ou na empresa,…

Deixe uma resposta

O seu endereço de email não será publicado. Campos obrigatórios marcados com *