Varrendo todo o chão da Albert Heijn. Parece simples. E deveria ter sido simples.
Mas sou estudante de Ciência da Computação e tenho um problema: não consigo parar de tentar otimizar coisas que (provavelmente) não precisam de otimização.
Então, em vez de apenas fazer meu trabalho e, bem… varrer… fiz o que qualquer pessoa “razoável” faria: transformei a planta do supermercado em um gráfico de grade, construí um editor visual e escrevi um otimizador de caminho C++ usando recozimento simulado.
Mas antes de nos aprofundarmos em como isso deu espetacularmente errado e como isso me fez perceber como isso deixa todo mundo infeliz, preciso que você responda a uma pergunta rápida:
Se você assumisse meu trabalho por um dia (eu não recomendaria, mas hipoteticamente falando) e precisasse varrer todo o andar da Albert Heijn, você seguiria o caminho A ou B?
Seriamente. Olhe para eles. Qual deles parece mais eficiente para varrer o chão de um supermercado?
Se você escolheu o caminho A: parabéns, você pensa como um algoritmo e provavelmente é um robô. (Boa sorte com perguntas CAPTCHA.)
Mas você está tecnicamente certo. O caminho A é mais curto em distância. No entanto, é absolutamente inútil.
Veja essas curvas. Na verdade, imagine por um segundo que você andaria por aí fazendo essas curvas. Você pareceria louco, como um Roomba tendo uma convulsão.
O Caminho A é o que acontece quando você otimiza para a coisa errada.
Qual, alerta de spoiler, é o objetivo desta história. Mas chegaremos lá, deixe-me primeiro explicar como chegamos aqui:
Primeiro, peguei a planta baixa de Albert Heijn e a converti em uma grade. Cada peça está vazia (deve ser varrida) ou é um obstáculo (parede, caixa, pacote de iogurte que alguém jogou no chão).
Eu construí um editor visual em Processamento (uma ferramenta Java para pessoas que gostam de deixar as coisas legais), para que eu pudesse mapear facilmente a loja e exportar o gráfico resultante.
Converter a planta baixa na estrutura de grade foi, portanto, bastante fácil.
Os ladrilhos do piso real ajudaram a subdividir a área em pedaços pequenos.
Isso poderia então ser facilmente convertido em uma estrutura de rede (também chamada de gráfico), interpretando cada bloco como um nó e conectando-os a blocos vizinhos.
Como você pode ver, permiti movimentos horizontais e verticais, bem como movimentos diagonais (desde que você não voe através das paredes).
A única coisa a fazer a seguir foi encontrar um ciclo através desta rede, certificando-se de visitar todos os nós (blocos). Esta seria então a solução para o meu problema abrangente.
(Esse problema também é chamado de Problema do caixeiro viajanteconsulte o artigo para obter mais detalhes e por que é tão difícil de “resolver”.)
Como é computacionalmente impossível encontrar o melhor caminho num grafo deste tamanho, temos que recorrer à heurística. A heurística basicamente tenta encontrar um muito bom solução em pouco tempo, em vez de tentar encontrar a solução perfeito solução (o que é mais ou menos impossível).
Então implementei o otimizador de caminho em C++.
O algoritmo heurístico subjacente: recozimento simulado.
Se você não estiver familiarizado, o recozimento simulado consiste essencialmente em tentar uma série de pequenas mudanças (também chamadas de movimentos locais).
No início, você apenas aceita cada pequena alteração (mesmo que isso piore o caminho), mas ao longo do algoritmo você lentamente se torna mais exigente e no final só permite alterações que melhorem estritamente o caminho.
Isso é inspirado na forma como os metais esfriam. Começando com uma temperatura alta (apenas tentando movimentos diferentes) para explorar bastante, e depois resfriando gradualmente para chegar a um estado de baixa energia (próximo do ideal).
Assista a este gif. Veja como tudo começa caótico e gradualmente se transforma em algo estável? Isso é recozimento simulado fazendo seu trabalho.
Para a mudança local, usei a mudança de 2 opções. Você pega duas arestas em seu caminho, remove-as e reconecta-as de uma maneira diferente. Se esta pequena mudança melhorar o caminho, mantenha-a. Caso contrário, guarde-o (se a temperatura ainda estiver alta) ou descarte-o.
Então faça isso 1 bilhão de vezes. Ou bem… deixe seu computador fazer isso 1 bilhão de vezes.
Depois de deixá-lo rodar por um tempo, consegui meu primeiro caminho “otimizado”. Aqui está o que surgiu:
Olhe para isso. Esse caminho tem curvas mais acentuadas do que um filme de Christopher Nolan. Não há como alguém ser louco o suficiente para varrer assim. Você provavelmente vomitaria depois.
Tecnicamente, cobre todo o piso. Tecnicamente, é (quase) o caminho mais curto. Tecnicamente, é perfeito.
Existem algumas partes boas nisso, mas na prática é absolutamente inútil.
O algoritmo fez exatamente o que eu pedi. (Felizmente, imagine se isso fizesse algo totalmente diferente, isso seria assustador.)
Acabei de fazer a pergunta errada.
Rapidamente percebi que estava otimizando para a coisa errada. A distância não é tudo.
Acontece que importa. O impulso é importante. Não parecer um robô com defeito é importante.
Então adicionei uma “penalidade de giro” à função de custo e pedi para também minimizar isso. Basicamente, dizer ao algoritmo: “Girar 90 graus custa pontos extras. Girar 180 graus? Você está louco.”
Isso resultou em rotas mais suaves, mesmo que torne a distância um pouco mais longa.
Veja isso. Na verdade, é… caminhável. Você poderia dar esse caminho a um ser humano real e ele não desistiria imediatamente.
Não estamos mais otimizando para distância. Estamos otimizando para a realidade.
É aqui que fica divertido.
Você pode ajustar a penalidade para curvas fechadas. Isso funciona como um controle deslizante entre “pura eficiência” e “realmente útil”.
Você pode literalmente ver a compensação. À medida que você aumenta a penalidade, o caminho fica mais suave, mas um pouco mais longo. À medida que você diminui, você obtém eficiência, mas caos.
O caminho que você escolhe depende inteiramente de você. Depende de coisas como quão fácil é para você virar, se a distância total é uma prioridade ou não e quanta tontura você pode tolerar.
No entanto, não se trata apenas de varrer o chão.
Isto é sobre tudo.
Algoritmos de mídia social otimizam o engajamento. Eles são muito bons nisso. O problema?
Engajamento ≠ felicidade. Engajamento ≠ verdade. Engajamento = cliques, tempo de tela, raiva e reação.
Consequências? Indignação, desinformação, rolagem do apocalipse, ansiedade.
Os algoritmos estão funcionando perfeitamente. Ele está fazendo exatamente o que foi projetado para fazer. A função de custo está simplesmente errada. (O Instagram provavelmente pensaria o contrário.)
Os algoritmos de recomendação otimizam o tempo de exibição e as taxas de cliques. Sua avó está assistindo teorias da conspiração no YouTube por 6 horas.
O algoritmo esmagou tudo. Ela se sente uma merda.
Não há surpresas aí.
Até mesmo LLMs (Large Language Models) como ChatGPT otimizam para a coisa errada. Eles otimizam para parecer confiante. Por parecerem que sabem a resposta.
Não por estar certo. Não por ser honesto.
Eles são treinados para completar padrões e não para dizer “não sei”. Então eles apenas adivinham. Sem vergonha nenhuma e com gramática perfeita.
Isso se aplica até mesmo a coisas fora da tecnologia.
Pense em empresas. A maioria deles otimiza para lucro. Terra, meio ambiente, moral ou ética? Eles não estão integrados à função de custo e, portanto, não serão otimizados.
Usei esse caminho otimizado em meu trabalho real?
Não. Obviamente não. Acabei de varrer o chão como uma pessoa normal.
Mas construir isso me ensinou algo em que penso constantemente: a correção técnica não vale nada se você estiver resolvendo o problema errado.
Você pode escrever um código perfeito. Você pode construir sistemas perfeitos. Você pode otimizar totalmente sua função de custo. E você ainda pode acabar com algo que é uma merda.
A parte importante não é o algoritmo de otimização. A parte importante é descobrir o que você deve otimizar em primeiro lugar.
Na maioria das vezes, nem fazemos essa pergunta. Nós apenas otimizamos o que for fácil de medir e esperamos que dê certo.
Spoiler: provavelmente não.
Se você aprendeu algo com isso, ótimo. Se você gostou de me ver complicar demais um trabalho de varredura, ótimo também.
De qualquer forma, obrigado por ler sobre minha tentativa de otimizar uma tarefa que absolutamente não precisava de otimização.
Quer mais experimentos como esse? Mais algoritmos, tecnologia interessante e discursos ocasionais sobre produtividade e economia de atenção? Inscreva-se gratuitamente abaixo! (Sem spam, apenas 1/2x por mês)
Repositório GitHub (código): aqui
Fonte: theverge
