Trabalho na Ideia #152
O Script do Problema dos Quadrados e Resultados Iniciais
No Problema dos Quadrados, você tem um tabuleiro com células que podem assumir ou o valor "1" ou "0", aleatoriamente, dada uma certa probabilidade p. O objetivo é estudar a distribuição das áreas contíguas de uns, uma área que têm vizinhos nas direções para cima, baixo, direita ou esquerda. Células vizinhas na diagonal não são consideradas contíguas.
FIGURA 1. Exemplo de um tabuleiro;
Eu abordei o Problema dos Quadrados algumas vezes, no computador, não tendo muito sucesso no início. Eventualmente, consegui desenvolver um script de força bruta que é capaz de calcular a distribuição de áreas de um tabuleiro gerado aleatoriamente. O script se encontra disponível para download no fim desta página.
[Depois de perguntar ao ChatGPT e conduzi-lo ao problema, descobri que o que eu fiz foi essencialmente uma versão não otimizada do algoritmo depth-first].
Primeiro, o script gera o tabuleiro, usando números aleatórios. Em seguida, para cada célula com um "'1", ele tenta se mover nas quatro direções, e continua fazendo isto até atingir as fronteiras das regiões contíguas. Quando faz um movimento bem sucedido, ele tenta se mover de novo, em um algoritmo em cascata.
Porém, o script calcula a distribuição de áreas a um enorme custo computacional, e é altamente ineficiente para grandes tabuleiros. Apesar de suas limitações, ele é capaz de mostrar alguns aspectos curiosos do problema.
Vamos analisar dois resultados do script em python:
A imagem na esquerda mostra os tabuleiros, com uns e zeros. A planilha de Excel a direita tabula a distribuição de áreas calculada, contando quantas áreas tem área de uma única célula, duas células, e assim por diante. Não existem áreas com mais de 11 células em nenhuma das duas execuções. Como pode ser visto, embora a distribuição de áreas não seja exatamente igual, ela é aproximadamente a mesma. A proporção de células brancas/pretas para uma dada probabilidade, no tabuleiro todo, permanece a mesma, aproximadamente igual a p.
Esta semi-preditabilidade, de que mesmo resultados aleatórios podem mostrar distribuições de área similares, foi uma das razões iniciais para ter decidido investigar este problema mais de perto.
Uma vez que o tabuleiro é gerado aleatoriamente, tem pouca utilidade resultados individuais. Faz mais sentido rodar o script algumas vezes e tomar a média da distribuição de áreas.
FIGURA 2. Distribuição de áreas média para 100 tabuleiros com lado de 50 células, para p = 0.5.
Como pode ser visto no gráfico acima, as áreas mais comuns são as isoladas, com uma única célula (contada em 85,3 áreas separadas). Com área 2, duas células, a contagem cai para 22,35. Com três células, 13,18. Quatro células, 9,27. Cinco células, 7,04. É fácil perceber que isto lembra uma função hiperbólica, decrescendo acentuadamente.
Também podemos variar a probabilidade p e rodar algumas vezes, e ver como os resultados mudam:
FIGURA 3. Distribuição de áreas para vários valores de p.
O gráfico acima mostra alguns resultados, mas só apresenta o intervalo inicial dos valores de área por motivos de clareza. Áreas isoladas são muito mais comuns do que, digamos, áreas acima de 10 células. Isto é válido para uma grande faixa de valores de probabilidade p.
Para valores realmente pequenos de p, entretanto, existem muitos "1"s no tabuleiro, e eles começam a formar grandes clusters. Isto forma uma cauda na curva acima, altamente irregular, feita destes grandes clusters.
Poderia se dizer que, a medida em que você diminui p, a curva varia de uma curva que cai rapidamente para valores baixos de área para outra curva que cresce rapidamente on valores altos de área. Não se atinge a mesma altura vertical entretanto, pois uma única área com muitas células corresponde a uma grande porção do tabuleiro. A posição da cauda também varia com p, conforme esperado.
FIGURE 4. Cauda da distribuição de áreas para valores pequenos da probabilidade p.
Parece bem provável que estes resultados possam ser fitados em distribuições estatísticas, mas meu conhecimento deste assunto é um tanto limitado.
LINKS DE DOWNLOAD:
O arquivo acima contém o script que calcula a distribuição de áreas para uma tabela. Ele devolve vários arquivos, um para cada execução, com tabelas contento a distribuição de áreas calculada para um tabuleiro aleatório. Sabe-se que este script roda bem mais rápido para valores altos de p, pois há menos uns no tabuleiro.
Este arquivo é um script simples que faz a média entre vários arquivos de distribuição de áreas obtidos de execuções diferentes.
Você deve primeiro rodar o script area_distribution_v_1_5 e em seguida o merge_v1.py.
BANNER IMAGE CREDITS: ESA/Hubble & NASA, A. Filippenko, R. Jansen
Want to know more about this image? Follow this external link.