Atividade 16: Estradas de gelo - Árvores de Steiner

Apresentação

As vezes uma pequena e aparentemente insignificante variação na especificação de um problema faz uma grande diferença em quão difícil é resolvê-lo. Esta atividade, tal qual o problema da Cidade Enlameada (Atividade 9), discorre sobre encontrar caminhos menores através de redes. A diferença é que agora é permitido introduzir novos pontos à rede se isto reduzir o comprimento total do caminho. O resultado é um problema bem mais difícil, não relacionado ao da cidade enlameada, mas sim, algoritmicamente, equivalente ao problema do cartógrafo pobre e ao da cidade turística.

Disciplinas e conteúdos relacionados

Habilidades

Nível de Ensino

Material

Cada grupo de alunos vai precisar de:

Estradas de gelo

Introdução

A última atividade, Cidade Turística, realizou-se em uma cidade muito quente; esta acontece num local justamente oposto. Durante o inverno, no frio congelante do norte do Canadá, nos enormes lagos congelados, “limpa-neves” conectam sítios de perfuração para que as equipes possam se ver. Lá fora, no frio, eles querem construir o mínimo de estradas possíveis, e a sua tarefa é encontrar essas estradas. Não há limitações: rodovias podem ir a qualquer lugar na neve - os lagos estão congelados e cobertos. Tudo é plano.

As estradas devem, obviamente, percorrer em linha reta, já que o incremento de curvas só aumentaria o comprimento delas. Mas não é tão simples como conectar os sítios com linhas retas, porque a adição de intersecções nas terras congeladas pode, muitas vezes, reduzir o comprimento total de uma estrada - o importante é o comprimento, não o tempo de viagem.

Nesta imagem, (a) mostra os três sítios de perfuração. Conectar um deles com os outros, como em (b), criaria um aceitável caminho. Outra possibilidade é fazer uma intersecção próxima ao centro do triângulo e conectá-las aos três sítios, (c). E se você medir a totalidade do caminho que foi limpo, esta é a melhor solução. A intersecção extra é chamada de “ponto de Steiner”, em homenagem ao matemático Jacob Steiner (1796-1863), que estabeleceu o problema e foi o primeiro a notar que o comprimento total pode ser reduzido através da introdução de novos pontos. Você pode imaginar o “ponto de Steiner” como um novo, fictício, sítio de perfuração.

Discussão

Descreva o problema no qual os alunos irão trabalhar. Usando o exemplo acima, demonstre que a adição de um novo sítio pode melhorar a solução ao reduzir o total de estradas construídas.

  1. Os alunos usarão 4 pontos dispostos em m quadrado, como ilustrado em (a). Vá para um ambiente aberto e faça com que cada grupo coloque 4 pregos no gramado, formando um quadrado 1x1 (1 metro por 1 metro).

  2. Faça os estudantes experimentarem diferentes conexões entre os pregos com os fios ou elásticos, medindo e gravando o menor comprimento total necessário. Nesta etapa eles não devem usar nenhum ponto de Steiner. (O mínimo é alcançado quando três lados do quadrado são conectados, como em (b), sendo 3 metros o comprimento total).

  3. Agora veja se eles podem fazer melhor ao usar um ponto de Steiner. (O melhor local para colocá-lo é no centro do quadrado, como em (c). O comprimento total é \(2\sqrt{2} =2,83\) metros). Sugira que eles possam melhorar ainda mais o resultado ao usar dois pontos de Steiner. (Realmente eles podem, ao colocar os dois pontos como em (d), formando ângulos de 120° entre as estradas que entram. O comprimento total será de \(1+\sqrt{3}=2,73\) metros).

  4. Podem, os alunos, fazer melhor utilizando três pontos de Steiner? Não, dois pontos são o melhor e nenhuma vantagem decorre da utilização de mais deles.

  5. Discuta com eles o porquê desses problemas parecerem difíceis. (É porque você não sabe onde colocar os pontos de Steiner, e há muitas possibilidades para testar).

Variações e extensões

  1. Um experimento interessante para os grupos que terminarem a atividade original rapidamente é trabalhar com um retângulo 1x2 (1 metro por 2 metros), como em (a). Os alunos descobrirão que adicionar um ponto de Steiner piora o problema, mas dois melhoram a solução. (Os comprimentos são 4 metros para (b), \(2\sqrt{5}=4,47\) metros para (c), e \(2+\sqrt{3}=3,73\) metros para (d).) Veja se eles conseguem descobrir porque a configuração de um ponto é tão ruim para retângulos. (É porque quando um quadrado é esticado criando um retângulo, o total do alongamento é adicionado apenas uma vez em (b) e em (d), mas ambas as diagonais aumentam em (c).)

  2. Alunos mais velhos podem trabalhar em um problema maior. Duas disposições de sítios para serem conectados com estradas de gelo foram dadas nas folhas de atividades. Eles podem experimentar diferentes soluções usando novas cópias dessas folhas ou escrevendo nelas com caneta removível em uma transparência acima da folha. Alternativamente, os mapas podem ser marcados no chão com os pregos. Eles podem falar para a turma quando considerarem que determinaram um novo recorde para a menor distância. (A figura abaixo mostra duas possíveis soluções para o segundo exemplo, cujos comprimentos totais são bem similares.) O fato de que há duas soluções tão similares ilustra porque esses tipos de problemas são tão difíceis - existem muitos locais para se colocar os pontos de Steiner!

  1. Redes em formato de escada, como as da figura abaixo, podem estender o problema.

  1. Algumas das árvores mínimas de Steiner para redes de escada são mostradas aqui: A usada para uma escada de “dois degraus” é a mesma que a usada para uma disposição quadrada de sítios. Entretanto, para uma escada de “três degraus” a solução é bem diferente - como você vai descobrir se tentar desenhá-la novamente em sua memória! A solução para “quatro degraus” é a mesma que para duas escadas de “dois degraus” juntas, ao passo a solução para uma de “cinco degraus” é como uma extensão da de “três degraus”. Em geral, a forma mínima de uma árvore de Steiner para uma escada depende do número par ou ímpar de degraus. Se for par, é como se houvessem várias escadas de “dois degraus” juntas; se for ímpar, é como uma repetição da solução da de “três degraus”. Mas provar isso rigorosamente não é fácil.

Outra atividade interessante é a construção de modelos “bolha de sabão” das árvores de Steiner. Você pode fazer isso pegando duas folhas de plástico rígido e transparente, colocando alfinetes entre elas, a fim de representar os sítios a serem expandidos, como ilustrado abaixo.

Agora mergulhe todo o aparato na solução de água com sabão. Quando ele sair, você vai descobrir que um fio de sabão conecta os alfinetes em uma linda rede de árvores-Steiner.

Infelizmente, entretanto, ela não representa, necessariamente, a menor árvore de Steiner. O fio de sabão é capaz de encontrar uma configuração que minimiza o comprimento total, mas é apenas um mínimo local, não, obrigatoriamente, um global. Pode haver maneiras completamente diferentes de se colocar os pontos de Steiner resultando em um comprimento menor. Por exemplo, você pode imaginar o fio de sabão parecido com a primeira configuração na Extensão 2 quando é retirado do líquido em uma ocasião, e parecido com a segunda configuração em outra.

Folhas de Atividades e Materiais Adicionais

Você também pode baixar todas as folhas de atividade e materiais adicionais em formato editável aqui.

Do que se trata tudo isso?

As redes com as quais trabalhamos são as árvores mínimas de Steiner (do inglês, Minimal Steiner Trees). Elas são chamadas de “árvores” porque não possuem ciclos, como os galhos de uma árvore que crescem e separam-se, mas não, normalmente, se reúnem e crescem juntos novamente. São chamadas de “Steiner”, em nome a um pesquisador que lidou com problemas como os dessa atividade; a característica trazida pelo Steiner é a de que novos pontos podem ser adicionados aos sítios originais que as árvores conectam. E são chamadas de “mínimas” porque possuem o menor comprimento total com relação a qualquer árvore conectando esses sítios. Na atividade Cidade Enlameada nós aprendemos que uma rede que minimiza o comprimento total e conecta vários sítios é chamada de Árvore Geradora Mínima (do inglês, minimal spanning tree), as árvores de Steiner realizam a mesma função, com a diferença de que novos pontos podem ser introduzidos.

É interessante que enquanto há um algoritmo muito eficiente para encontrar as árvores geradores mínimas (como as mostradas na Cidade Enlameada) - um algoritmo ganancioso que trabalha conectando, os dois pontos mais próximos, até então, desconectados - não existe nenhuma solução geral para a minimização do problema de Steiner. Árvores de Steiner são muito mais difíceis porque você deve decidir, grosseiramente, aonde colocá-los: a diferença entre as duas soluções do exemplo 2, por exemplo. Uma vez que você saiba em quais regiões colocar os novos pontos, afinar eles a fim de otimizar a solução é relativamente simples. Fios de sabão fazem isso eficientemente, e os computadores também podem fazer.

Encontrar árvores de Steiner mínimas é parte de uma história sobre poupar dinheiro nos negócios de telefonia nos Estados Unidos. Antes de 1967, quando clientes corporativos nos EUA operavam redes de telefones grandes e privadas, eles alugavam as linhas de companhias telefônicas. O total do qual eram cobrados não era calculado baseado na utilização das linhas, mas sim baseado sobre qual a menor rede suficiente. Pela razão de que o cliente não deveria ser cobrado a mais só porque a companhia de telefonia usava um caminho com uma rotatória. Originalmente, o algoritmo que calculava o quanto cobrar trabalhava determinando as árvores geradoras mínimas. Entretanto, por volta de 1967, um cliente notou - na verdade uma linha de aviação, com três grandes eixos - que se pedisse por um quarto ponto, em um local intermediário, o comprimento total de sua rede seria reduzido. A telefonia foi forçada a reduzir sua cobrança para o que ela seria se houvesse um câmbio de telefone no ponto de Steiner! Apesar de que, para configurações típicas, a árvore de Steiner mínima é apenas 5% ou 10% mais curta que a árvore geradora mínima, pode valer a pena economizar essas porcentagens quando grandes quantias de dinheiro estão envolvidas. O problema da árvore de Steiner é, muitas vezes, chamado de “problema da rede mais curta”, porque envolve o descobrimento da rede mais curta que conecta um conjunto de sítios.

Se você abordou as seguintes atividades, o Labirinto do Cartógrafo e a Cidade Turística, você não se surpreenderá ao saber que o problema da árvore de Steiner mínima é “NP-completo”. O número de possíveis locais para os pontos de Steiner cresce junto com o aumento do número de sítios, e tentar todas as possibilidades envolve uma busca que cresce exponencialmente. Esta é outro dos centenas de problemas para os quais simplesmente não se sabe se a busca exponencial é o melhor caminho, ou se há um algoritmo “polynomial-time” (o tempo necessário para um computador resolver um problema, onde o tempo é uma função polinomial do tamanho do input) que ainda não foi descoberto. O que se sabe, entretanto, é que se um algoritmo for descoberto para este problema, ele pode ser transformado em um algoritmo para coloração de gráficos, para encontrar conjuntos dominantes mínimos, e para todos os outros problemas da classe NP-completo.

Nós explicamos, no final da última atividade que o “NP” em NP-completo significa non-deterministic polynomial (polinomial não determinística), e o “completo” se refere ao fato de que se um algoritmo polynomial-time for encontrado, ele pode ser transformado e aplicado para todos os outros problemas NP-completos. A lista de problemas que podem ser resolvidos com esse algoritmo é chamada PP. Então a questão crucial é, esse algoritmo existe para problemas NP-completos? - De outro modo, é PP = NP? A resposta para essa pergunta não é conhecida, e é um dos grandes mistérios da ciência da computação moderna.

Problemas para os quais algoritmos polynomial-time existem - mesmo que sejam lentos - são chamados tratáveis, ao contrário, problemas para os quais eles não existem, são chamados intratáveis. Não importa quão rápido o computador, ou quantos computadores são usados conjuntamente, um pequeno aumento no tamanho do problema significará que eles não podem ser resolvidos na prática. Não se sabe se os problemas NP-completos - que incluem o quebra-cabeça do cartógrafo, a cidade turística e as estradas de gelo - são tratáveis ou não. Mas a maioria dos cientistas da computação são pessimistas sobre o descobrimento de um algoritmo para problemas NP-completos, dessa forma provar que um problema é NP-completo é visto como prova segura de que o problema é inerentemente intratável.

O que você pode fazer quando seu chefe pede para você inventar um algoritmo eficiente que otimiza a solução de um problema, mas você não pode encontrar um? - Tão certamente aconteceu quando a linha aérea bateu com o fato de que o custo da rede telefônica poderia ser reduzido com a introdução de pontos de Steiner. Se você pudesse provar que não há tal algoritmo, seria ótimo, mas é difícil provar resultados negativos como esses na ciência da computação, pois quem sabe algum programador inteligente encontre, no futuro, uma pista obscura que resolva o problema. Então, infelizmente, você não está numa posição em que possa dizer categoricamente que nenhum algoritmo eficiente existe - que o problema é intratável. Mas se você puder mostrar que o seu problema é NP-completo, então será verdadeiro que milhares de pessoas em laboratórios de pesquisa trabalharam em problemas equivalentes ao seu, e também falharam em trazer uma solução eficiente. Isso pode não te valer um bônus, mas tirará você dessa situação.

Claro que na vida real esses problemas precisam ser resolvidos, e nesse caso o problema se torna heurístico - algoritmos que não garantem a melhor solução ao problema, mas fornecem soluções dentro de uma pequena porcentagem de otimização. Algoritmos heurísticos podem ser muito rápidos, e a perda advinda de não encontrar a melhor solução possível pode ser bem pequena, então são suficientemente bons para um trabalho. Só é frustrante saber que talvez haja um algoritmo polynomial-time ou uma disposição de rede um pouco melhores.

Para saber mais

O tópico grafos não faz parte do currículo da educação básica, mas pode ser acessível para estudantes de todas as idades. A coleção Matemática Multimídia possui diversos recursos educacionais que abordam esse tópico com níveis de complexidade muito variados. Se você se interessou, conheça alguns deles aqui. O problema tratado nesta atividade é mais avançado do que os da coleção, mas os recursos podem ser um bom caminho para começar o trabalho com grafos e os guias do professor podem ser um bom material de estudo para o professor interessado.

O Portal da Matemática da OBEMP oferece um módulo sobre grafos com várias video-aulas que partem de uma abordagem bastante inicial até problemas bastante avançados.