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?
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>
• B - C - D - A - B 12 + 7 + 15 + 25 = 59 km
• <u>B - C - A - D - B 12 + 18 + 15 + 8 = 53 km</u> ←
• B - D - B - C - B 8 + 7 + 18 + 25 = 58 km
• <u>B - D - C - B - B 8 + 15 + 18 + 12 = 53 km</u> ←
• 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 (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>
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>
• B - C - D - A - B 12 + 7 + 15 + 25 = 59 km
• <u>B - C - A - D - B 12 + 18 + 15 + 8 = 53 km</u> ←
• B - D - B - C - B 8 + 7 + 18 + 25 = 58 km
• <u>B - D - C - B - B 8 + 15 + 18 + 12 = 53 km</u> ←
• 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 (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>
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
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 Crianças - blog da Associação 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.
Cognosco ergo sum
Conheço logo sou
no Cognosco
Cogitações recentes
Mauro Maia
Pergunta feita por um menino de 14 anos... Mas a p...
Essa pergunta é interessante: será que ele se quei...
O fogo é fruto de uma reação quÃmica, não tem esta...
Olá Ribeiro. Eis um link atualizado para a folha d...
Seria possÃvel fornecer um link atualizado para o ...
Artigos mais cogitados
282 comentários
74 comentários
66 comentários
62 comentários
44 comentários
Artigos