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, as pessoas usam o termo "Wilson" para propósitos muito diferentes, e isso é bastante confuso: existe o algoritmo de Wilson para gerar labirintos, o Modelo de Wilson (ou EOQ) para inventários e o teorema de Wilson na teoria dos números. Neste artigo, esclarecemos tudo, começando pelo uso original em labirintos e distinguindo cuidadosamente os outros significados, porque Eles não são os mesmos nem se aplicam à mesma área.

Se você já viu uma demonstração ou um applet em que um labirinto "cresce" sozinho, provavelmente já se deparou com o algoritmo de Wilson. Você também já ouviu falar do Modelo de Wilson para calcular a quantidade de ordem econômica ou mesmo do teorema que caracteriza números primos usando fatoriais. Aqui você encontrará uma explicação completa com exemplos, para que possa você pode 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 com apagamento de loops. Sua grande vantagem é que ele produz uma árvore geradora aleatória uniforme sobre a grade: em termos simples, Cada labirinto possível aparece com a mesma probabilidade, sem vieses em relação a direções ou padrões específicos.

A ideia principal é que caminhos são adicionados ao conjunto já construído, mas quando um passeio aleatório se cruza, o loop é "excluído" e a rota continua de onde parou. Esse detalhe evita que o processo crie caminhos ou loops longos e redundantes, mantendo a estrutura como uma árvore conectando todas as células. O resultado é um labirinto "justo": nenhum corredor ou curva tem vantagem estatística sobre outro.

Existem projetos e applets criados pela comunidade que mostram o algoritmo em ação de forma visual e altamente divertida. Entre eles, destacam-se alguns applets de Cruz Godar, onde você pode escolher o tamanho da grade e colocá-la em funcionamento para ver como o labirinto surge passo a passo. Observá-lo em execução ajuda a entender o porquê. A eliminação do loop equilibra as probabilidades em cada extensão do gráfico.

Construir e resolver labirintos são tarefas que, embora possam parecer jogos, estão intimamente ligadas a problemas de busca e otimização. Projetá-los requer um equilíbrio entre clareza e interesse, evitando soluções triviais ou becos sem saída; explorar um espaço finito com combinações enormes. Portanto, tanto no papel quanto em simulações digitais, eles funcionam como Ótimos exercícios de lógica, probabilidade e paciência.

Como funciona (em termos práticos)

Abaixo está uma descrição de alto nível do algoritmo, sem código, mas com a mecânica essencial para entender seu comportamento. Lembre-se de que o objetivo é construir uma árvore (sem ciclos) que conecte todas as células, de modo que existe apenas um caminho simples entre qualquer par de 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.

Comparado a outros métodos (como Aldous-Broder, primeiro ou Kruskal adaptado a labirintos), Wilson se destaca pela uniformidade da amostragem da árvore geradora. Seu custo computacional é razoável em grades típicas e, acima de tudo, garante que cada solução seja igualmente provável, algo muito apreciado em contextos acadêmicos e de simulação.

Outros significados: Modelo de Wilson ou EOQ (estoques)

Em logística, o “Modelo Wilson” (também chamado de EOQ, Quantidade Econômica do Pedido; ou CEP, Quantidade Econômica do Pedido) não tem nada a ver com labirintos. É um método clássico para determinar a quantidade ideal do pedido com o objetivo de minimizar os custos totais de estoque. Foi popularizado em 1934 por R.H. Wilson, embora A primeira proposta foi feita por Ford Whitman Harris em 1913.

Seu objetivo é encontrar o tamanho do lote Q que equilibra o custo de pedido e o custo de manutenção de estoque. A partir da demanda anual (D), do custo por pedido (K) e do custo de armazenagem por unidade e período (G), obtém-se uma quantidade que, dentro da estrutura de suas premissas, reduz o custo total do estoque.

A fórmula mais comum é Q = √(2 D K/G). Isso fornece o tamanho do lote; a partir daí, o número de pedidos anuais será D/Q, e a partir disso você pode derivar a cadência temporal. Também é importante definir o ponto de reabastecimento (levando em consideração o lead time) e o estoque de segurança para evitar rupturas, embora o fórmula básica não incorpora incerteza explicitamente.

Aplicações típicas: usado 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, se D, K e G forem conhecidos com confiabilidade suficiente, A empresa pode dimensionar seus lotes e programar seu fornecimento com maior controle.

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

As premissas são cruciais para a validade dos resultados. 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 armazenagem sejam conhecidos e dependam do nível de estoque, que os tempos de fornecimento sejam constantes e, além disso, não contempla 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, de acordo com suas condições. Seus benefícios incluem redução do excesso de estoque, redução do risco de rupturas (se acompanhado de um ponto de reposição e estoque de segurança) e clareza no planejamento de compras. Muitas organizações o valorizam porque oferece uma base numérica simples para decidir quanto pedir.

Desvantagens: Não funciona bem com demanda sazonal ou irregular, ignora descontos por volume e pressupõe reposição imediata (ou fixa), o que é irrealista em muitas cadeias de suprimentos. Portanto, em ambientes como o Grupo Toyota, a fórmula EOQ foi substituída por sistemas mais robustos, como Kanban ou Just in Time, que Eles 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 armazenagem é de € 2.000, aplicando a fórmula Q = √(2 D K/G) com D = 1.000, K = 200, G = 2.000, obtém-se Q ≈ 14,14. Isso sugere lotes de 14 kg e aproximadamente 71 pedidos por ano. Este é 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 armazenamento por unidade por ano é de € 5 (G). Aplicando a equação, Q ≈ 848,52, 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 os custos de preparação de pedidos.

Além da fórmula, é uma boa ideia calcular o ponto de reabastecimento considerando o lead time e a manutenção do 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 poderia compensar os custos de estoque se forem utilizados lotes maiores.

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

O teorema de Wilson pertence ao aritmética modular e essencialmente diz 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)" é frequentemente 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 prova conhecida tenha sido dada por Lagrange (1771), e de fato, A formulação remonta a Alhacen no século XI.

Exemplo concreto: para p = 11, ao agrupar cada elemento com seu inverso multiplicativo no conjunto {1, 2, …, p − 1}, o produto total torna-se ≡ −1 (mod p). Todos os fatores se cancelam uniformemente quando g g^{-1} ≡ 1, exceto 1 e p − 1, e assim 10! ≡ −1 (módulo 11)Essa abordagem usa que, com p primo, (Z/pZ)^× é um grupo multiplicativo e cada elemento (exceto 1 e p − 1) tem 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 1, 2, …, p − 1 anulam f(x) pelo pequeno teorema de Fermat. Portanto, f(x) é identicamente 0 mod p e o termo independente 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 é caro e existem testes mais rápidos (como Miller-Rabin ou testes determinísticos para intervalos específicos). Mesmo assim, é útil para deduzir propriedades úteis: por exemplo, se p = 2n + 1 é primo, então temos ∏_{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), uma vez que pode ser escrito como o quadrado do produto 1 2 2k quando p = 4k + 1, que mostra quando −1 é quadrado em Z/pZ.

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

Gauss generalizou o teorema: o produto de todas as unidades módulo n, ∏_{1≤a É aquele elemento de ordem 2.

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

Na tabela a seguir, você pode ver valores específicos para n entre 2 e 30. Para n primo, o resto de (n − 1)! quando dividido por n é igual a n − 1 (que é ≡ −1 mod n). Em compósitos, o resto geralmente é 0. −1 mod n também é incluído para comparação. Esses dados ilustram muito bem como o teorema de Wilson se comporta em casos pequenos e ajudam a consertar 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, use o algoritmo de Wilson: sua base em caminhadas aleatórias com exclusão de loops garante árvores uniformes. Para estoques, 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, JIT ou software de planejamento avançado podem ser mais apropriadas. 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 um teste de primalidade para grandes números.

Não existe uma fórmula única para calcular os custos de pedidos e armazenagem: cada empresa precisa 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 monetizar. Essa personalização é fundamental para tornar o Q calculado útil e, juntamente com um bom ponto de reposição e estoque de segurança, evitar rupturas de estoque ou excesso de estoque.

Vale lembrar que o termo "algoritmo de Wilson" nas pesquisas geralmente se refere ao gerador de labirintos, enquanto "modelo de Wilson" ou "EOQ" se refere a inventários, e "teorema de Wilson" se refere à teoria dos números. Distinguir os termos desde o início evita confusão e permite que você utilize melhor cada abordagem: Labirintos imparciais, lotes ótimos sob suposições realistas e uma caracterização elegante de primos que, embora não seja um teste prático de primalidade, ainda é uma peça valiosa do quebra-cabeça matemático.