Atividade 15: Cidade Turística – Conjuntos Dominantes

Apresentação

Muitas situações da vida real podem ser abstraídas no formato de rede ou “grafo”, como aquele utilizado para colorir na Atividade 13. As redes apresentam muitas oportunidades para o desenvolvimento de algoritmos que são úteis na prática.

Nesta atividade, queremos marcar algumas junções ou “nós”, de modo que todos os nós estejam, no máximo, a um passo de distância dos nós marcados. A questão que queremos resolver aqui é: com qual quantidade mínima de nós marcados podemos resolver a situação proposta? Este pode ser um problema surpreendentemente difícil.

Disciplinas e conteúdos relacionados

Habilidades

Nível de Ensino

Material

Cada grupo de alunos vai precisar de:

Você vai precisar de:

Conjuntos Dominantes

Introdução

A Folha de Atividade: Vans de Sorvete mostra um mapa de uma Cidade Turística. As linhas são ruas e os pontos são esquinas. A cidade se localiza em um país muito quente onde, no verão, as vans estacionam nas esquinas das ruas e vendem sorvetes para turistas. Queremos posicionar as vans de modo que qualquer pessoa possa chegar até elas andando até o final da rua e, então, no máximo, mais um quarteirão. Para ficar mais fácil de imaginar, considere o seguinte cenário: as pessoas dessa cidade têm suas casas localizadas em cruzamentos; a partir de onde se encontram, elas devem conseguir comprar um sorvete andando, no máximo, apenas mais um quarteirão. A pergunta é: quantas vans são necessárias para isso e em quais cruzamentos devem ser alocadas?

Discussão

  1. Divida os alunos em pequenos grupos. Dê a cada grupo uma cópia da Folha de Atividade: Vans de Sorvete e algumas fichas de pôquer (ou material similar). Após, conte a história apresentada na Introdução.

  2. Mostre aos alunos como devem colocar as fichas nos cruzamentos para marcar as vans de sorvete. Depois, coloque fichas de outras cores nos cruzamentos situados a uma rua de distância daqueles marcados. As pessoas que têm casas nesses cruzamentos, ou ao longo das ruas localizadas entre eles, devem ser consideradas clientes das vans de sorvete.

  3. Incentive os alunos a experimentarem diferentes configurações de posicionamento para as vans. Enquanto eles encontram posições que abrangem todos os moradores da cidade, lembre-os de que as vans são caras e que a ideia desse exercício é fazê-los utilizar o menor número possível de vans para resolver o problema proposto. É óbvio que as condições podem ser cumpridas se houver vans suficientes para alocar em todos os cruzamentos. A questão interessante que queremos resolver aqui é: com qual quantidade mínima de vans alocadas no mapa conseguimos atender a todos os moradores da cidade?

  4. O número mínimo de vans para a cidade turística é seis e uma possibilidade de resolução está abaixo e na folha Resolução da atividade: Vans de Sorvete. No entanto, é muito difícil encontrar essa resolução! Depois de algum tempo de atividade, diga aos grupos que seis vans são suficientes para resolver o problema e desafie a turma a encontrar essa possibilidade de resposta. Essa é uma atividade bastante difícil e é possível que muitos grupos desistam. Mesmo uma resolução que utilize oito ou nove vans pode ser difícil de encontrar.

  1. O mapa da cidade turística foi elaborado a partir das seis peças localizadas na parte de baixo da folha Resolução da atividade: Vans de Sorvete. Para cada uma dessas peças, obviamente, é esperada a alocação de apenas uma van de sorvete. Dessa forma, foram conectadas às peças diversas ruas a fim de mascarar a resolução do problema. A ideia principal consiste em não inserir nenhuma conexão de rua entre os cruzamentos da resolução que contêm pontos abertos (brancos), mas sim entre aqueles pontos a mais, que contêm pontos sólidos (pretos). Ao final da atividade, mostre à turma essa técnica a partir de desenho no quadro ou através do auxílio de um projetor.

  2. Incentive os alunos a elaborar seus próprios mapas, em nível de dificuldade alto, utilizando a mesma técnica apresentada a eles ao final da atividade. Eles podem testar essas criações com seus amigos e família. Dessa forma, descobrirão que podem criar enigmas que eles são capazes de resolver, mas que as outras pessoas não. Na computação, esse fenômeno é denominado “Função de mão única”. Isto é, criar um quebra-cabeça muito difícil de montar pode ser fácil, mas montá-lo será complexo - a não ser que a pessoa que esteja montando seja a criadora do quebra-cabeça. As funções de mão única são ferramentas fundamentais para a criptografia (veja as Atividades 17 e 18).

Variações e Extensões

Há inúmeros tipos de situação nas quais se pode enfrentar o tipo de problema proposto na atividade anterior. Especialmente no contexto do planejamento urbano, quando pensamos na alocação de caixas postais, poços, unidades do corpo de bombeiros, entre outros. Mas, na realidade, os mapas não são baseados em um truque que facilita a resolução do problema. Pense: se você realmente tivesse que resolver uma situação como a apresentada na atividade, o que faria?

Há uma maneira muito simples. Explore e considere todas as formas possíveis de alocar vans de sorvete no mapa e verifique qual é a melhor. Com 26 esquinas na cidade turística, há 26 formas de alocar uma van. É fácil verificar essas 26 possibilidades e é óbvio que nenhuma delas satisfará as condições desejadas. Considerando duas vans, há 26 lugares para alocar o primeiro e, assim, restam 25 lugares para acomodar o segundo. Você, obviamente, não alocaria as duas vans no mesmo cruzamento; afinal, existem 650 (26 × 25) possibilidades de verificação, que são facilmente executáveis, apesar de entediantes. Na verdade, você só precisa checar metade delas (325), já que não importa qual van é qual - se você verificou a van 1 no cruzamento A e a van 2 no cruzamento B, então não há necessidade de verificar a van 1 no cruzamento B nem a van 2 no cruzamento A. Nesse sentido, você poderia continuar a verificar três vans (2600 possibilidades), quatro vans (14950 possibilidades) e assim por diante. Claramente, 26 vans são suficientes já que existem apenas 26 cruzamentos e não há necessidade de haver mais de uma alocada no mesmo ponto. Outra forma de avaliar o número de possibilidades é considerar o número total de configurações possíveis com 26 cruzamentos e qualquer número de vans. Como há duas possibilidades para cada esquina - pode ou não haver uma van em cada uma - o número de possibilidades de configuração é \(2^{26}\); ou seja, 67.108.864.

Esse modelo de resolução de problemas é denominado de algoritmo de “força bruta” e trata-se de uma técnica que demanda muito tempo. A ideia de que os computadores são tão rápidos que podem resolver qualquer problema rapidamente, não importando o montante de trabalho envolvido, é errônea e muito difundida. O tempo de execução do algoritmo de força bruta depende da velocidade de verificação de uma determinada configuração de posicionamento como possível solução. Essa verificação envolve fazer um teste, para cada cruzamento, com a finalidade de encontrar a distância da van mais próxima. Imagine que uma configuração inteira possa ser testada em um segundo. Quanto tempo leva para testar todas as \(2^{26}\) possibilidades de configuração possíveis para a cidade turística? (Resposta: \(2^{26}\) é cerca de 67 milhões; há 86.400 segundos em um dia; portanto, \(2^{26}\) segundos equivalem a cerca de 777 dias, ou cerca de dois anos). Suponha que, em vez de um segundo, tenha levado apenas um milésimo de segundo para verificar cada configuração. Então, esses dois anos permitiriam que o computador encontrasse a solução para uma cidade com 36 cruzamentos já que \(2^{26}\) é cerca de 1000 vezes \(2^{26}\). Mesmo que o computador fosse um milhão de vezes mais rápido, para que um milhão de configurações pudessem ser verificadas a cada segundo, demorariam dois anos para encontrar uma solução para uma cidade de 46 cruzamentos. Note que essas cidades não são muito grandes! (Quantos cruzamentos existem na cidade que você criou?)

Visto que o algoritmo de força bruta é lento, existem outras formas de resolver o tipo de problema proposto? Bom, podemos tentar a abordagem gulosa, que obteve tanto sucesso na atividade “Cidade Enlameada” (Atividade 9). Para isso, precisamos pensar em como podemos ser gananciosos com sorvete - digo, como aplicar a abordagem gananciosa ao problema proposto das vans de sorvete. No entanto, fazer isso não ajuda, necessariamente, a produzir um conjunto mínimo de posições para as vans de sorvete. Na verdade, o cruzamento com o maior número de conexões da Cidade Turística, que tem cinco ruas, não é um bom lugar para alocar uma van (verifique isto com a turma).

Vamos olhar para um problema mais fácil. Imagine que, no lugar de ter que encontrar uma configuração mínima você tenha que verificar se uma dada configuração é mínima ou não. Em alguns casos, essa tarefa é fácil. Por exemplo, o diagrama apresentado abaixo mostra um mapa muito mais fácil cuja solução é ainda mais simples. Se você imaginar as ruas como arestas de um cubo, fica claro que duas vans de sorvete posicionadas em cubos diagonalmente opostos aos vértices são suficientes. Além disso, você deve ser capaz de se convencer de que não é possível resolver o problema com menos de duas vans. É muito mais difícil, embora não impossível, convencer-se de que as pessoas, na cidade turística, não podem ser atendidas por menos de seis vans. Para mapas gerais, é extremamente difícil provar que uma certa configuração de vans de sorvete é mínima.

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?

O que chama a atenção no problema proposto na atividade das vans de sorvete é: não se sabe se existe um algoritmo, para encontrar um conjunto mínimo de locais, que seja significantemente mais rápido que a técnica de busca por força bruta. O tempo gasto ao utilizar essa técnica cresce exponencialmente com o número de cruzamentos - identifica-se esse algoritmo, portanto, como um algoritmo de tempo exponencial. Um algoritmo de tempo polinomial é aquele cujo tempo de execução cresce com a potência ao quadrado, cubo, décima sétima potência, ou qualquer outra potência que corresponda ao número de cruzamentos da cidade. Um algoritmo de tempo polinomial será sempre mais rápido para mapas grandes - mesmo um algoritmo de décima sétima potência -, já que uma função de crescimento exponencial supera qualquer outra de crescimento polinomial, considerando que seu argumento se torna significantemente grande. Por exemplo, resolvendo essa questão em termos práticos, sempre que n for maior que 117, então \(n^{17}\) é menor que \(2^n\). Existe um algoritmo de tempo polinomial para encontrar o conjunto mínimo de locais? Não há uma resposta para essa questão, embora todos tentem encontrar uma. E isso é válido para a tarefa, aparentemente mais fácil, de verificar se um determinado conjunto de locais é mínimo. O algoritmo de busca por força bruta, ao tentar todas as possibilidades para conjuntos mínimos de locais, é exponencial no número de cruzamentos; enquanto os algoritmos polinomiais de tempo não foram descobertos nem têm sua existência comprovada.

Tudo isso faz com que você lembre da atividade de pintura do mapa? Deveria. O sorvete, que é oficialmente conhecido como um problema de “conjunto mínimo dominante”, é um dos muitos milhares de problemas para os quais não se sabe se existem algoritmos polinomiais de tempo. Esses problemas podem ser encontrados em domínios que variam desde a lógica, problemas de arranjo do tipo quebra-cabeça, coloração de mapas, busca por rotas óptimas em mapas, até processos de agendamento. Surpreendentemente, todos esses problemas se mostraram equivalentes no sentido de que, se um algoritmo de tempo polinomial é encontrado para um deles, então ele pode ser convertido em um algoritmo do mesmo tipo para todos os outros. Desse modo, pode-se dizer que ou eles se sustentam ou caem juntos.

Estes problemas são chamados de NP-completos. NP significa “não-determinístico polinomial.” Esse jargão implica que o problema em questão poderia ser resolvido em um tempo razoável se você tivesse um computador que pudesse experimentar um número arbitrariamente grande de soluções de uma só vez (que é a parte não-determinística). Você pode pensar que essa é uma suposição bastante irrealista. E, na verdade, é. Não é possível construir esse tipo de computador já que ele teria que ter dimensões muito grandes. Entretanto, o conceito de uma máquina assim é importante, a princípio, pois aparenta que problemas NP-completos não podem ser resolvidos dentro de um período razoável sem um computador não-determinístico.

Além disso, esse grupo de problemas é chamado de completo devido ao fato de que embora os problemas pareçam muito diferentes - por exemplo, a atividade da pintura do mapa e a de alocação de vans de sorvete -, se um método de resolver um deles eficientemente é encontrado, então ele pode ser adaptado para resolver qualquer um dos outros problemas. É isso que está implicado quando falamos que ou eles “se sustentam ou caem juntos.”

Há milhares de problemas NP-completos. Pesquisadores têm procurado soluções eficientes para eles, durante anos, sem sucesso. Se uma solução eficiente tivesse sido descoberta para apenas um deles, então teríamos soluções eficientes para todos eles. Por essa razão, suspeita-se fortemente que não haja uma solução eficiente para problemas completos. No entanto, provar que esses problemas tomam, necessariamente, um tempo exponencial é o trabalho em aberto de maior destaque na ciência da computação teórica - possivelmente em todo o campo da matemática - atualmente.

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