domingo, 20 de abril de 2008

Otimização com água e sabão

Ano passado fui pela primeira vez à Estação Ciência, em São Paulo, e fiquei espantado com a qualidade. Eu já visitei o Natural History Museum de Londres, e o American Museum of Natural History em New York, então eu digo, com conhecimento de causa, que a Estação Ciência não fica nada a dever aos museus de ciência do primeiro mundo. Tem dinossauros, planetário, simulador de terremoto, e até simulador de tsunami (que não tinha nos museus lá de cima).

Na verdade, o museu brasileiro tem uma vantagem sobre os outros. Por lá, a média é de, mais ou menos, uns quarenta visitantes por guia, e aqui a média é de três guias por visitante! Se você tiver bastante tempo pra visitar, os guias irão lhe dar explicações extremamente detalhadas das exposições.

A minha predileta foi na seção de matemática experimental, onde fizemos a experiência do sabão. Você pega duas placas paralelas quaisquer, coloca quatro pregos nelas, e mergulha num balde de água com sabão. Eu estava esperando que o sabão grudasse nos pregos e fizesse um quadrilátero, mas na verdade o que ele faz é uma estrutura em duplo Y:

(Você pode fazer em casa esse experimento, mas para melhores resultados, coloque um pouco de glicerina na água. Experimente também com outras quantidades de pregos, e com figuras tridimensionais).

A explicação é que o sabão, como bom sistema físico, vai procurar a posição de energia mínima, que nesse caso é equivalente a minimizar a soma dos comprimentos da película. Anedoticamente, esse problema é conhecido como o problema da estrada (como ligar quatro cidades com estradas, gastando a menor quantidade possível de asfalto?), e a solução ótima é conhecida como Steiner Tree.

À primeira vista pode parecer que a Steiner Tree é equivalente à Minimum Spanning Tree, mas não é. Pra calcular a spanning tree, você só pode usar os pontos do grafo, já na Steiner tree você pode adicionar pontos novos. Isso faz uma diferença enorme na complexidade: existem algoritmos quase lineares para resolver a spanning tree, já a Steiner tree é NP-completa.

Na verdade, há quem diga que isso é uma prova de que P=NP, como os autores desse paper no Arxiv. Segundo eles, existe um computador analógico feito com sabão que resolve um problema NP-completo em tempo polinomial, logo P=NP :)

Pra quem quiser brincar com Steiner trees, o problema ELC do spoj pede pra resolver uma instância com 3k pontos. Como isso é demais para um brute force, você vai ter que aproximar: por exemplo, iterando a partir de uma spanning tree; ou então, calculando a triangulação de Delaunay e depois resolvendo a Steiner tree local de cada triângulo.

8 comentários:

  1. Cara, espero que o museu seja realmente de alto nível, porque o site por outro lado... Sério, eu esperava um site com mais imagens, vídeos e atividades interativas. Mas só tem textos e mais textos, numa diagramação bem amadora tipicamente feita por estudantes e estagiários... Tudo bem, coloquem estagiários pra fazer o site, mas estagiários de design gráfico, e não de física, né?

    ResponderExcluir
  2. O site é muito ruim mesmo, para achar uma foto decente pra ilustrar o post, eu tive que ir procurar no flickr por visitantes do museu :(

    ResponderExcluir
  3. O paper do Arxiv é engraçado, mas é uma sucessão de WTFs: até prova em contrário, o dispositivo não é uma máquina de Turing [1]; ele pode chegar a um mínimo local, não a uma solução ótima; não está claro que o tempo que o dispositivo leva para "computar" a solução é realmente polinomial. Estranhamente, a data de submissão do paper não é primeiro de abril.

    [1] talvez o Stephen Wolfram discorde.

    ResponderExcluir
  4. Ele não é mesmo uma máquina de Turing, é um computador analógico. Em geral os computadores analógicos fazem só uma coisa muito bem, por exemplo, aquelas montagens com 741 que resolvem equações diferenciais. Falarei disso no próximo post :)

    ResponderExcluir
  5. Aliás, eu lembrei que eu vi, lá na Estação Ciência, o sabão convergindo para um mínimo local! O guia colocou um cubo feito de arame dentro do sabão pra mostrar uma estrutura qualquer, mas não formou o que ele queria. Então ele deu uma sacudida no cubo, e aí convergiu pro lugar certo.

    ResponderExcluir
  6. > Então ele deu uma sacudida no cubo, e aí convergiu pro lugar certo.

    Simulated anealing?

    ResponderExcluir
  7. O annealing não era simulated :)
    Mas ao invés de energia térmica, ele adicionou energia cinética.

    ResponderExcluir
  8. Alias, o fato de que ha convergencia para solucoes locais derruba o argumento daquele paper que voce citou, no qual os autores defendem que P=NP porque o computador de sabao resolve um problema NP. E' a mesma coisa que dizer que o simulated annealing prova que P=NP!

    ResponderExcluir