Algoritmo de Wilson: Guia completo, diferenças com EOQ e o teorema

Informatec Digital » Engenharia » Algoritmo de Wilson: Guia completo, diferenças com EOQ e o teorema

Na internet, o termo "Wilson" é usado para muitas coisas diferentes, o que pode ser bastante confuso: existe o algoritmo de Wilson para gerar labirintos, o Modelo de Inventário de Wilson (ou EOQ) e o teorema de Wilson na teoria dos números. Neste artigo, esclarecemos tudo, começando pelo seu uso original em labirintos e distinguindo cuidadosamente os outros significados, pois não são a mesma coisa e não se aplicam ao mesmo campo.

Se você já viu uma demonstração ou aplicativo onde um labirinto "cresce" sozinho, provavelmente já se deparou com o algoritmo de Wilson. Você também pode ter ouvido falar do Modelo de Wilson para calcular a quantidade econômica de pedido ou até mesmo do teorema que caracteriza os números primos usando fatoriais. Aqui você encontrará uma explicação completa com exemplos, para que possa identificar cada conceito e usá-lo corretamente.

O que é o algoritmo de Wilson para labirintos?

O algoritmo de Wilson é um método de geração de labirintos baseado em caminhadas aleatórias sem laços. Sua principal vantagem é produzir uma árvore geradora aleatória uniforme em toda a grade: em outras palavras, cada labirinto possível aparece com a mesma probabilidade , sem viés em relação a direções ou padrões específicos.

A ideia principal é que caminhos são adicionados à rede existente, mas quando um caminho aleatório se cruza, o loop é "apagado" e a rota continua do ponto onde ficou livre. Esse detalhe impede que o processo favoreça caminhos longos redundantes ou crie ciclos, mantendo a estrutura como uma árvore que conecta todas as células. O resultado é um labirinto "justo": nenhum caminho ou curva tem vantagem estatística sobre outro.

Existem projetos e aplicativos criados pela comunidade que demonstram o algoritmo em ação de forma visual e divertida. Entre eles, alguns dos aplicativos de Cruz Godar se destacam, nos quais você pode escolher o tamanho da grade e executá-los para ver como o labirinto emerge passo a passo. Observar a execução ajuda a entender por que a eliminação de loops nivela as probabilidades em cada extensão do grafo.

Construir e resolver labirintos, embora pareçam jogos, estão intimamente ligados a problemas de busca e otimização. Projetá-los exige um equilíbrio entre clareza e intriga, evitando soluções triviais ou becos sem saída impossíveis; explorando um espaço finito com vastas combinações. Portanto, tanto no papel quanto em simulações digitais, eles servem como excelentes exercícios de lógica, probabilidade e paciência.

Como funciona (em termos práticos)

A seguir, uma descrição geral do algoritmo, sem código, mas com os mecanismos essenciais para entender seu comportamento. Lembre-se de que o objetivo é construir uma árvore (sem ciclos) que conecte todas as células, de forma que exista apenas um caminho simples entre quaisquer dois pontos.

• Começa com uma grade vazia: uma célula é escolhida aleatoriamente e marcada como parte da árvore.
• Outra célula é escolhida aleatoriamente, uma caminhada aleatória passo a passo é iniciada e, se o caminho se cruzar, os loops são imediatamente removidos (apagamento de loops).
• Quando a caminhada atinge a árvore já gerada, todo o caminho refinado (sem loops) é “colado” à árvore.
• Repete-se: escolhemos uma nova célula desconectada, caminhamos com a exclusão do loop e juntamos a árvore.
• No final, todas as células estão conectadas e o labirinto é uma árvore de extensão aleatória uniforme, então não há vieses direcionais ou topológicos.

Em comparação com outros métodos (como Aldous-Broder, Prim ou Kruskal adaptados a labirintos), o método de Wilson destaca-se pela uniformidade da amostragem da árvore geradora. Seu custo computacional é razoável em grades típicas e, sobretudo, garante que cada solução seja equiprovável , algo altamente valorizado em contextos acadêmicos e de simulação.

Outros significados: Modelo de Wilson ou EOQ (estoques)

Em logística, o modelo de Wilson (também chamado de EOQ, Quantidade Econômica de Pedido) não tem nada a ver com labirintos. É um método clássico para determinar a quantidade ideal de pedido para minimizar os custos totais de estoque. Foi popularizado em 1934 por R.H. Wilson, embora o conceito inicial tenha sido proposto por Ford Whitman Harris em 1913.

Seu objetivo é encontrar o tamanho do lote Q que equilibra o custo de fazer pedidos e o custo de manter o estoque. Com base na demanda anual (D), no custo por pedido (K) e no custo de armazenamento por unidade por período (G), obtém-se uma quantidade que, dentro do escopo de suas premissas, reduz o custo total do estoque.

A fórmula mais comum é expressa como Q = √(2·D·K/G). Este valor fornece o tamanho de cada lote; a partir daí, o número de pedidos anuais será D/Q, e com isso você pode calcular o ciclo de pedidos. Também é importante definir o ponto de reposição (levando em consideração o prazo de entrega) e o estoque de segurança para evitar rupturas de estoque, embora a fórmula básica não incorpore explicitamente a incerteza.

Aplicações típicas: É utilizado com matérias-primas ou qualquer tipo de mercadoria para a qual os custos de compra e armazenamento possam ser determinados com confiabilidade. Na prática, ao conhecer D, K e G com precisão suficiente, a empresa pode dimensionar seus lotes e programar suas aquisições com maior controle.

Suposições, vantagens e limitações do Modelo Wilson

As premissas são cruciais para a validade do resultado. O modelo EOQ pressupõe que a demanda seja constante e conhecida, que o preço unitário permaneça estável, que os custos de armazenamento sejam conhecidos e dependam do nível de estoque, que os prazos de entrega sejam constantes e, além disso, não considera descontos por volume.

• Demanda estável e independente, sem sazonalidade ou picos repentinos.
• Preço de compra fixo ou praticamente inalterado durante o período analisado.
• Custos de armazenamento conhecidos por unidade e período.
• Sem descontos por quantidade e reposição imediata ou constante.

Principais vantagens: É simples de implementar, amplamente utilizado e ajuda a minimizar os custos de pedidos e estoque, conforme suas condições. Os benefícios incluem a redução do excesso de estoque, a diminuição do risco de ruptura de estoque (quando combinado com um ponto de reposição e estoque de segurança) e maior clareza no planejamento de compras. Muitas organizações o valorizam porque fornece uma base numérica direta para determinar as quantidades de pedidos.

Desvantagens: Não funciona bem com demanda sazonal ou irregular, ignora descontos por volume e pressupõe reabastecimento imediato (ou fixo), o que é irrealista em muitas cadeias de suprimentos. Portanto, em ambientes como o do grupo Toyota, a fórmula do Lote Econômico de Compra (EOQ) foi substituída por sistemas mais robustos, como Kanban ou Just-in-Time, que lidam melhor com a variabilidade real e o fluxo contínuo.

Exemplos práticos do EOQ (Wilson)

Exemplo 1 (típico): Uma empresa com uma produção anual de 10.000 unidades adquire 1.000 kg de matéria-prima. Se cada pedido custa €200 e o custo total anual de armazenamento é de €2.000, aplicando a fórmula Q = √(2·D·K/G) com D=1.000, K=200 e G=2.000, obtém-se Q ≈ 14,14. Isso sugere lotes de 14 kg e aproximadamente 71 pedidos por ano. Trata-se de um exercício ilustrativo onde, com números modestos, podemos ver como o tamanho do lote equilibra os pedidos e o estoque.

Exemplo 2: A Sillas Grandes World SL distribui 6.000 cadeiras (D), cada pedido custa €300 (K) e o custo anual de armazenamento por unidade é de €5 (G). Aplicando a equação, Q ≈ 848,52, o que significa que a empresa faria aproximadamente 7,07 pedidos por ano. Com esse tamanho de lote, a empresa tende a um nível de estoque mais eficiente , reduzindo os custos de armazenamento sem aumentar significativamente os custos de preparação de pedidos.

Além da própria fórmula, é aconselhável calcular o ponto de reposição considerando o prazo de entrega e manter um estoque de segurança, pois o modelo puro não leva em conta a incerteza. Ele também não estima o impacto dos descontos por volume, que às vezes podem compensar os custos de estoque se lotes maiores forem utilizados.

Não deve ser confundido com o teorema de Wilson (teoria dos números)

O teorema de Wilson pertence à aritmética modular e essencialmente afirma que um inteiro n > 1 é primo se e somente se (n − 1)! ≡ −1 (mod n). A implicação "se n é primo, então (n − 1)! ≡ −1 (mod n)" é geralmente chamada estritamente de "teorema de Wilson", e a implicação inversa também é verdadeira. Historicamente, Edward Waring atribuiu o resultado a John Wilson (1770), embora a primeira demonstração conhecida tenha sido dada por Lagrange (1771), e a formulação remonte a Alhazen no século XI.

Exemplo concreto: para p = 11, agrupando cada elemento com seu inverso multiplicativo no conjunto {1, 2, …, p − 1}, o produto total é ≡ −1 (mod p). Todos os fatores se cancelam aos pares, pois g·g^{-1} ≡ 1, exceto para 1 e p − 1, e portanto 10! ≡ −1 (mod 11) . Essa abordagem utiliza o fato de que, com p primo, (Z/pZ)^× é um grupo multiplicativo e cada elemento (exceto 1 e p − 1) possui um inverso distinto.

Existem várias demonstrações. Uma técnica polinomial considera g(x) = (x − 1)(x − 2)···(x − (p − 1)) e f(x) = g(x) − (x^{p−1} − 1). Módulo p, f(x) teria no máximo p − 2 raízes se não fosse o polinômio nulo, mas todos os valores 1, 2, …, p − 1 tornam f(x) zero pelo Pequeno Teorema de Fermat. Portanto, f(x) é identicamente 0 módulo p; o termo constante leva a (p − 1)! ≡ −1 (mod p).

Não é usado como um teste prático de primalidade porque calcular (n − 1)! mod n para n grande é custoso, e existem testes mais rápidos (como Miller-Rabin ou testes determinísticos para postos específicos). Mesmo assim, pode ser usado para deduzir propriedades úteis: por exemplo, se p = 2n + 1 é primo, obtemos ∏_{j=1}^{n} j^2 ≡ (−1)^{n+1} (mod p). E, como um corolário parcial, −1 é um resíduo quadrático módulo p se p ≡ 1 (mod 4), já que pode ser escrito como o quadrado do produto 1·2···2k quando p = 4k + 1, o que se mostra quando −1 é elevado ao quadrado em Z/pZ.

Existe também um "inverso" prático: para qualquer número composto n > 5, n divide (n − 1)!. O caso n = 4 é a exceção clássica (3! não é múltiplo de 4). Uma maneira de ver isso é contar as potências de um primo q que divide n: em (n − 1)! existem múltiplos suficientes de q para cobrir a potência que aparece em n, exceto pela exceção mencionada, o que leva ao resultado, exceto para n = 4.

Gauss generalizou o teorema: o produto de todas as unidades módulo n, ∏_{1≤a<n, (a,n)=1} a, é ≡ −1 (mod n) se n ∈ {4, p^k, 2p^k} com p primo ímpar, e ≡ 1 (mod n) em todos os outros casos. Da perspectiva de grupos abelianos finitos, o produto de todos os seus elementos é a identidade, a menos que exista exatamente um elemento de ordem 2, caso em que o produto é esse elemento de ordem 2.

Tabela ilustrativa de (n − 1)! mod n para n = 2…30

A tabela a seguir mostra valores específicos para n entre 2 e 30. Para números primos, o resto da divisão de (n − 1)! por n é igual a n − 1 (que é ≡ −1 mod n). Para números compostos, o resto é frequentemente 0. −1 mod n também é incluído para comparação. Esses dados ilustram claramente como o teorema de Wilson se comporta em casos pequenos e ajudam a consolidar a intuição.

n> 1	(n − 1)!	(n − 1)! mod n	−1 mod n
2	1	1	1
3	2	2	2
4	6	2	3
5	24	4	4
6	120	0	5
7	720	6	6
8	5040	0	7
9	40320	0	8
10	362880	0	9
11	3628800	10	10
12	39916800	0	11
13	479001600	12	12
14	6227020800	0	13
15	87178291200	0	14
16	1307674368000	0	15
17	20922789888000	16	16
18	355687428096000	0	17
19	6402373705728000	18	18
20	121645100408832000	0	19
21	2432902008176640000	0	20
22	51090942171709440000	0	21
23	1124000727777607680000	22	22
24	25852016738884976640000	0	23
25	620448401733239439360000	0	24
26	15511210043330985984000000	0	25
27	403291461126605635584000000	0	26
28	10888869450418352160768000000	0	27
29	304888344611713860501504000000	28	28
30	8841761993739701954543616000000	0	29

Aplicações, limites e recomendações

Se você busca gerar labirintos imparciais, utilize o algoritmo de Wilson: sua base em caminhadas aleatórias com eliminação de laços garante árvores uniformes. Para gestão de estoque, o modelo de Wilson é útil quando a demanda, os preços e os custos são estáveis ​​e precisamente conhecidos; em ambientes voláteis, metodologias como Kanban, Just-in-Time ou softwares avançados de planejamento podem ser mais adequadas. E em matemática, o teorema de Wilson é uma joia teórica com derivações interessantes (como resíduos quadráticos), mas não é prático como teste de primalidade para números grandes.

Não existe uma fórmula única para calcular os custos de pedidos e armazenamento: cada empresa deve detalhar horas, processos, transporte, recebimento, pessoal, aluguel, energia, seguro e custos financeiros. Muitos profissionais estimam as horas por operação e aplicam uma taxa horária para monetização. Essa personalização é fundamental para garantir que a quantidade de pedido (Q) calculada seja útil e, juntamente com um bom ponto de reposição e estoque de segurança, ajude a evitar rupturas de estoque ou excesso de inventário.

Vale lembrar que o termo "algoritmo de Wilson" em buscas geralmente se refere ao gerador de labirintos, enquanto "modelo de Wilson" ou "EOQ" se referem a estoques, e "teorema de Wilson" à teoria dos números. Distinguir esses termos desde o início evita confusão e permite que você aproveite melhor cada abordagem: labirintos não enviesados, lotes ótimos sob suposições realistas e uma caracterização elegante de números primos que, embora não seja uma prova prática de primalidade, continua sendo uma peça valiosa do quebra-cabeça matemático.