Últimas atualizações
Novo endereço do Cognosco: http://www.cognoscomm.com
Diário das pequenas descobertas da vida.
Domingo, 13 de Novembro de 2005
Plus exigua via
Em maré de optmizações de situações concretas com o uso de grafos, 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?
[Error: Irreparable invalid markup ('<img [...] height"159">') in entry. Owner must fix manually. Raw contents below.]

Em maré de optmizações de situações concretas com o uso de grafos, 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).
<img src="http:\\cognoscomm.com/mm\GrafoCidade.jpg" height="203" width="300" border="0" />
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?
<img alt="Jogo de Hamilton \ planificação de um dodecaedro" src="http:\\cognoscomm.com/mm\GrafoDodecaedro.gif" height"159" width="167" align="right" border="0" />
Este tipo de situação é o que se chama um <b>circuito de Hamilton</b>, em honra do Matemático que descreveu esta situação numa carta a um amigo.
<i>Hamilton chegou a inventar um jogo, o </i>Jogo de Hamilton<i>, jogado num tabuleiro com a forma da planificação de um dodecaedro (ver <a href="http:\\cognosco.blogs.sapo.pt/arquivo/805859.html"><font color="blue">Omnia factus mathematica</font></a> sobre este e outros sólidos platónicos) 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 objectivo do jogo é somente passar por todos os pontos uma só vez. Este é um <b>circuito de Hamilton</b>.</i>

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 <b>peso</b> diferente (neste caso distância, podia ser tempo, custo, ...). Este tipo de problema é chamado de <b>Problema do caixeiro viajante</b> ou <b> Problema do carteiro chinês</b>.

Infelizmente <b>não</b> há uma forma de encontrar sempre o caminho mais curto o mais rapidadmente 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 circuito de Hamilton existentes são estes:
<i>(comecei arbitrariamente por B. Começando por qualquer outro ponto os resultados seriam iguais, uma vez que todos estão listados)</i>

&#8226 B - C - D - A - B 12 + 7 + 15 + 25 = 59 km
&#8226 <u>B - C - A - D - B 12 + 18 + 15 + 8 = 53 km</u> &#8592
&#8226 B - D - B - C - B 8 + 7 + 18 + 25 = 58 km
&#8226 <u>B - D - C - B - B 8 + 15 + 18 + 12 = 53 km</u> &#8592
&#8226 B - A - D - C - B 25 + 15 + 7 + 12 = 59 km
&#8226 B - A - C - D - B 25 + 18 + 7 + 8 = 58 km

Este caso é bastante simples e é possível listar todas as possibilidades (se se for sistemático de forma a não esquecer nenhum). Mas infelizmente o número de possibilidades cresce de forma explosiva à medida que aumenta o número de vértices.

Suponhamos que o grafo tem 4 vértices:
~ o número de circuitos diferente é 3 x 2 x 1 / 2 = <u>3</u>.
Se o grafo tem 5 vértices:
~ o número de circuitos diferente é 4 x 3 x 2 x 1 / 2 = <u>12</u>.
Se o grafo tem 6 vértices:
~ o número de circuitos diferente é 5 x 4 x 3 x 2 x 1 / 2 = <u>60</u>.
...
Se o grafo tem 10 vértices:
~ o número de circuitos diferente é 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 / 2 = <u>181 440</u>.
De um forma geral, se o grafo tem <i>n</i> vértices:
~ o número de circuitos diferentes é <u>(n - 1)! / 2</u>
<i>O símbolo «!» significa que se multiplica o número por todos os números inteiros menores do que ele até 1 (5! = 5 x 4 x 3 x 2 x 1 = 120)</i>
(Para mais sobre este símbolo e os métodos de contagem ver <a href="http:\\cognosco.blogs.sapo.pt\784643.html"><font color="blue">Caecus adnumeratio</font></a>)

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 quase impossível fazê-lo.
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:
<img src="http://cognoscomm.com/mm/GrafoCidades.jpg" height="165" width="205" align="right" border="0" />
DE 7
AE 8
AD 12
BC 14
BE 18
CE 19
DC 25
AB 37

Comecemos 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. Só falta regressa 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.
Mais uma vez podia ser simples encontrar o caminho por tentativa e erro, mas para grafos maiores (e mais reais) pode ser muito complicado.

A situação é também diferente no caso de o que se pretende ligar entre as cidades não for 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.
<img src="http://cognoscomm.com/mm/GrafoRede.jpg" height="118" width="457" border="0" />
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

Comecemos 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,...

<i>A via mais curta</i>


Publicado por Mauro Maia às 23:00
Atalho para o Artigo | Cogitar | Adicionar aos favoritos

6 comentários:
De Maria Papoila a 14 de Novembro de 2005 às 21:22
Gostei muito do artigo Mauro, mas aplica-se mais á rede de computadores porque na viagem de férias podemos perdermo-nos pelos caminhos mais longos...são muitas vezes mais agradáveis e têm mais de ver...Quanto a outros caminhos tinha sempre a mania que havia uma hipotenusa a percorrer entre catetos...Aprendi hoje, mais uma lição e a Matemática é uma caixinha de sonhos! Beijo


De Mauro a 14 de Novembro de 2005 às 22:15
Na verdade há, geralmente, incluídos nesta questão, hipotenusas e catetos, mas unicamente para determinar as distâncias. Conhecendo as distâncias (num mapa, por exemplo) podemos partir para os grafos. E acho também que a melhor parte de uma viagem é descobrir os caminhos mais longos, que são geralmente os mais floridos, os mais interessantes. Mas o seu interesse sai sempre reforçado (e o espírito por outro lado apaziguado) quando se tem uma planificação que, nos momentos certos, se dobra para incluir aquela villa pitoresca no sopé do monte que não vinha no mapa...


De Elsita a 15 de Novembro de 2005 às 14:21
Bolas, Mauro a isto chama-se rapidez, ou será atraso, meu?!?!?: ontem vim cá ler o teu post, mas não consegui fazê-lo com o cuidado e atenção pretendida, porque estava a adorar "ler-te", então hoje voltei para fazê-lo com o cuidado essencial e já havia outro post Isso é que é trabalhar, heim!
Fica bem


De Mauro a 15 de Novembro de 2005 às 20:45
E agora o ritmo está bem mais lento, Elsita. Como puderás comprovar nas sinopses, antes das férias, o ritmo de produção de artigos era de 2 artigos todos os dias (fim-de-semanas incluídos), artigos tão ou mais extensos do que este. Aquele era um ritmo que percebi ser excessivo e potencialmente a causa do baixo número de comentários no blog. Eu simplesmente não parava para respirar nem deixava os leitores respirarem. Não só havia dois artigos extensos para ler num dia como no dia seguinte havia mais dois. E isso por 3 ou 4 meses. Fiz o esforço de me conter, apesar de, por vezes, um só tema propiciar-se a ser muito mais abrangente e eu sintir que um só artigo é insuficiente. Mas vou apontando os assuntos que desejo abordar para futuros artigos. E é sempre compensador ter quem leia, comente e lhe agrade cada artigo. Só isso vale a pena a contenção. Obrigado, como sempre, Elsita.


De Pais Separados e Crianas - blog da Associao 26-4 a 18 de Novembro de 2005 às 13:21
a associação 26-4, Pais Separados (e crianças Espancadas ) , emn http://www.26-4.com/ , precisa de colaboradores, Mauro ... se quiser, colabore . Por exemplo, para melhorar imagens de scanners , para reunir dados sobre crianças espancadas, etcetc .. toda a ajuda, é bem vinda .


De Mauro a 18 de Novembro de 2005 às 22:17
Sem dúvida um movimento que merece toda a atenção e todo o apoio. Conhecia já o blog «Portugal abrupto... mas». Fica aqui o endereço de mais um blog sobre a mesma temática, muitas vezes esquecida até que nos bate à porta. Deixo aqui o repto aos leitores. Quanto a mim, assim eu oportuno, contactar-vos-ei. As maiores felicidades para o vosso blog.


Comentar artigo

Cognosco ergo sum

Conheço logo sou

Estatísticas

Nº de dias:
Artigos: 336
Comentários: 2358
Comentários/artigo: 7,02

Visitas:
(desde 26 de Abril de 2005)
no Cognosco
 
Cogitações recentes
Obrigado, João, pela contribuição. Não está no art...
Estive lendo sua cogitação à respeito do cálculo d...
Obrigado, Aleff, pelo apreço pelo artigo. Exatamen...
achei muito interessante essa sua forma de ver a l...
Obrigado, Desejo um bom 2014 também.
Artigos mais cogitados
282 comentários
74 comentários
66 comentários
62 comentários
44 comentários
Artigos

Agosto 2017

Julho 2017

Junho 2017

Maio 2017

Abril 2017

Março 2017

Fevereiro 2017

Janeiro 2017

Dezembro 2016

Novembro 2016

Outubro 2016

Julho 2016

Março 2015

Dezembro 2014

Outubro 2013

Maio 2013

Fevereiro 2013

Outubro 2012

Setembro 2012

Agosto 2012

Junho 2012

Janeiro 2012

Setembro 2011

Abril 2011

Fevereiro 2011

Dezembro 2010

Maio 2010

Janeiro 2010

Abril 2009

Fevereiro 2009

Janeiro 2009

Novembro 2008

Outubro 2008

Agosto 2008

Julho 2008

Junho 2008

Abril 2008

Fevereiro 2008

Janeiro 2008

Novembro 2007

Outubro 2007

Agosto 2007

Julho 2007

Junho 2007

Maio 2007

Abril 2007

Março 2007

Fevereiro 2007

Janeiro 2007

Dezembro 2006

Novembro 2006

Outubro 2006

Setembro 2006

Agosto 2006

Julho 2006

Junho 2006

Maio 2006

Abril 2006

Março 2006

Fevereiro 2006

Janeiro 2006

Dezembro 2005

Novembro 2005

Outubro 2005

Setembro 2005

Julho 2005

Junho 2005

Maio 2005

Abril 2005

Março 2005

Fevereiro 2005