Um atalho que cabia no desenho

O trabalho era fazer um simulador de cidades distribuir água e energia entre bairros que cresciam e mudavam a demanda. Geradores de um lado, consumidores do outro, tubulações e linhas no meio. Vendo o mapa, dava vontade de simplificar o desenho da rede. Mas as conexões formavam uma malha, com bifurcações, caminhos alternativos e limites de capacidade em cada trecho. Calcular o fluxo na malha inteira custava caro. Veio então uma ideia tentadora: nos casos simples, usar uma árvore, conferir as capacidades e deixar o cálculo completo para o restante.

A árvore era fácil de explicar. Cada consumidor teria um caminho até a origem; bastaria somar as demandas nos trechos compartilhados e verificar se nada passava do limite. Se a conta fechasse, teríamos uma solução sem consultar a malha inteira. Até aí, ótimo. A armadilha estava em interpretar o que significava quando a conta não fechava.

A cidade tinha caminhos que o desenho apagou

Na medição registrada, a árvore ligada ao gerador mais próximo aceitou 12 de 212 tentativas de alocação. Uma segunda versão, que compartilhava a geração entre os ramos, aceitou as mesmas 12. Isso não queria dizer que as outras alocações eram impossíveis. A malha tinha caminhos válidos que nenhuma das árvores representava.

Imagine dois bairros ligados à mesma origem. O caminho mais curto passa por um trecho estreito, mas há uma rota pela outra lateral da rede com capacidade livre. Se a árvore escolhe só o trecho estreito, a soma das demandas ultrapassa o limite ali. Na malha, o fluxo pode se dividir entre os dois lados. A árvore só avalia os caminhos que escolheu; o erro seria tomar essa resposta como uma conclusão sobre a rede inteira.

Em linguagem de otimização, a simplificação restringiu o conjunto de soluções viáveis. Encontrar uma solução nesse conjunto é útil. Não encontrar nenhuma não prova que o problema original seja inviável. Essa diferença muda o algoritmo: a árvore pode propor uma solução, mas, se falhar, é preciso consultar a malha completa.

O fluxo antigo também guardava voltas

A investigação tentou outro atalho: aproveitar a distribuição anterior e ajustá-la à demanda seguinte. À primeira vista, o fluxo já calculado parecia um bom ponto de partida. Só que todas as amostras iniciais continham circulação, voltas em que o recurso atravessava arestas sem aumentar a entrega a ninguém. Na hora de reaproveitar a solução, essas voltas ocupavam capacidade e faziam a checagem falhar.

Eliminar essas voltas preservou o balanço em cada nó e liberou capacidade nos trechos. Assim, 48 das 212 tentativas passaram na verificação de reuso. Uma variação que admitia novos consumidores em pontos já atendidos chegou a 75. Isso revelou algo sobre a estrutura do problema, mas não bastou para trocar de método: os experimentos com reuso não trouxeram ganho suficiente no tempo total.

Gosto desse detalhe porque ele separa duas perguntas que costumam virar uma só. O fluxo atende à demanda? E a representação desse fluxo está limpa o bastante para ser reutilizada sob novas restrições? A primeira pode ser verdadeira enquanto a segunda falha por causa de uma volta que não entrega nada.

O que a medição permitiu dizer

Uma das árvores terminou a execução isolada mais rápido que o método de referência. Mas ela aceitou poucas tentativas, e uma única medição não bastava para torná-la a opção padrão. A última versão do reuso, depois de filtrar os casos pela demanda, levou 101,63 segundos, contra 98,70 do método de referência no mesmo cenário, e usou mais memória. Nenhum desses atalhos substituiu o cálculo original.

O que vale levar para outro problema é saber exatamente o que o atalho consegue comprovar. Uma solução encontrada pela árvore pode poupar trabalho se também respeitar as restrições da malha. Já uma falha nos caminhos escolhidos pela árvore não prova que a malha inteira seja inviável. E, se o tempo total com o cálculo completo como alternativa não melhora, a elegância da ideia não basta.