Algoritmo de Wilson: guía completa, diferencias con EOQ y el teorema

Informatec Digital » Ingeniería » Algoritmo de Wilson: guía completa, diferencias con EOQ y el teorema

En Internet se habla de “Wilson” para cosas bien distintas, y eso confunde bastante: está el algoritmo de Wilson para generar laberintos, el Modelo de Wilson (o EOQ) de inventarios y el teorema de Wilson en teoría de números. En este artículo lo aclaramos todo, empezando por el uso original en laberintos y distinguiendo cuidadosamente las otras acepciones, porque no son lo mismo ni se aplican al mismo ámbito.

Si has visto alguna demo o applet donde un laberinto va “creciendo” solo, quizá ya te topaste con el algoritmo de Wilson. También habrás oído hablar del Modelo Wilson para calcular la cantidad económica de pedido o incluso del teorema que caracteriza los números primos mediante factoriales. Aquí encontrarás una explicación completa y con ejemplos, de forma que puedas identificar cada concepto y usarlo con propiedad.

Qué es el algoritmo de Wilson para laberintos

El algoritmo de Wilson es un método de generación de laberintos basado en caminatas aleatorias con borrado de bucles (loop-erased random walks). Su gran virtud es que produce un árbol generador aleatorio uniforme sobre la cuadrícula: dicho en sencillo, cada laberinto posible aparece con la misma probabilidad, sin sesgos hacia direcciones o patrones concretos.

La idea clave es que se van añadiendo caminos al conjunto ya construido, pero cuando una caminata al azar se cruza a sí misma, se “borra” el bucle y la ruta continúa desde el punto donde quedó libre. Este detalle hace que el proceso no favorezca rutas largas redundantes ni Cree ciclos, manteniendo la estructura como un árbol que conecta todas las celdas. El resultado es un laberinto “justo”: ningún pasillo o giro tiene ventaja estadística sobre otro.

Hay proyectos y applets creados por la comunidad que muestran el algoritmo en acción de forma visual y muy entretenida. Entre ellos, destacan algunos applets de Cruz Godar, donde puedes elegir el tamaño de la cuadrícula y ponerlo a trabajar para ver cómo surge el laberinto paso a paso. Verlo ejecutarse ayuda a entender por qué el borrado de bucles nivela las probabilidades en cada extensión del grafo.

Construir y resolver laberintos son tareas que, aunque parezcan juegos, están estrechamente vinculadas a problemas de búsqueda y optimización. Diseñarlos requiere equilibrio entre claridad e interés, evitando soluciones triviales o callejones imposibles; explorar un espacio finito con combinaciones enormes. Por eso, tanto en papel como en simulaciones digitales, funcionan como ejercicios estupendos de lógica, probabilidad y paciencia.

Cómo funciona (en términos prácticos)

A continuación, una descripción de alto nivel del algoritmo, sin código pero con la mecánica esencial para entender su comportamiento. Recuerda que el objetivo es construir un árbol (sin ciclos) que conecte todas las celdas, de forma que solo exista un camino simple entre cualquier par de puntos.

• Se parte de una cuadrícula vacía: se escoge una celda al azar y se marca como parte del árbol.
• Se elige otra celda al azar, se inicia una caminata aleatoria paso a paso y, si la ruta se cruza a sí misma, se eliminan los bucles inmediatamente (loop-erasing).
• Cuando la caminata alcanza el árbol ya generado, todo el camino depurado (sin bucles) se “pega” al árbol.
• Se repite: elegimos una nueva celda no conectada, caminata con borrado de bucles y unión al árbol.
• Al final, todas las celdas están conectadas y el laberinto es un árbol generador aleatorio uniforme, por lo que no hay sesgos direccionales ni topológicos.

Frente a otros métodos (como Aldous–Broder, Prim o Kruskal adaptados a laberintos), Wilson brilla por la uniformidad del muestreo del árbol generador. Su coste computacional es razonable en cuadrículas típicas y, sobre todo, garantiza que cada solución sea equiprobable, algo muy apreciado en contextos académicos y de simulación.

Otras acepciones: el Modelo de Wilson o EOQ (inventarios)

En logística, “Modelo de Wilson” (también llamado EOQ, Economic Order Quantity; o CEP, Cantidad Económica de Pedido) no tiene nada que ver con laberintos. Es un método clásico para determinar la cantidad óptima de cada pedido con el objetivo de minimizar los costes totales de inventario. Se popularizó en 1934 por R. H. Wilson, si bien el primer planteamiento fue de Ford Whitman Harris en 1913.

Su finalidad es encontrar el tamaño de lote Q que equilibra el coste de hacer pedidos y el coste de mantener existencias. A partir de la demanda anual (D), el coste por pedido (K) y el coste de almacenamiento por unidad y periodo (G), se obtiene una cantidad que, en el marco de sus supuestos, reduce el coste total de inventario.

La fórmula más conocida se expresa como Q = √(2·D·K/G). Esta cifra da el tamaño de cada lote; a partir de ahí, el número de pedidos anuales será D/Q, y con ello puedes derivar la cadencia temporal. Es importante también fijar el punto de pedido (teniendo en cuenta el lead time) y el stock de seguridad para evitar roturas, aunque la fórmula básica no incorpora incertidumbre de forma explícita.

Aplicaciones habituales: se usa con materias primas o con cualquier tipo de mercancía para la que se puedan determinar de manera estable los costes de compra y almacenamiento. En la práctica, al conocer D, K y G con suficiente fiabilidad, la empresa puede dimensionar sus lotes y programar su aprovisionamiento con mayor control.

Supuestos, ventajas y limitaciones del Modelo de Wilson

Los supuestos son críticos para la validez del resultado. El modelo EOQ presupone que la demanda es constante y conocida, que el precio unitario permanece estable, que los costes de almacenamiento son conocidos y dependen del nivel de existencias, que los tiempos de aprovisionamiento son constantes y, además, no contempla descuentos por volumen.

• Demanda estable, independiente, sin estacionalidad ni picos bruscos.
• Precio de compra fijo o prácticamente invariable durante el periodo analizado.
• Costes de almacenamiento conocidos por unidad y periodo.
• Sin descuentos por cantidad y reposición inmediata o de tiempo conocido y constante.

Ventajas principales: es simple de aplicar, está muy extendido y ayuda a minimizar costes de pedido y de stock bajo sus condiciones. Entre sus beneficios se cuentan la reducción de sobrestock, la disminución del riesgo de roturas (si se acompaña de un punto de pedido y stock de seguridad) y la claridad para planificar compras. Muchas organizaciones lo valoran porque ofrece una base numérica sencilla para decidir cuánto pedir.

Desventajas: no sirve bien con demandas estacionales o irregulares, ignora los descuentos por volumen y asume reposición inmediata (o fija), algo poco realista en muchas cadenas de suministro. Por ello, en entornos como el grupo Toyota, la fórmula EOQ se ha visto desplazada por sistemas más robustos como Kanban o Just in Time, que manejan mejor la variabilidad real y el flujo continuo.

Ejemplos prácticos del EOQ (Wilson)

Ejemplo 1 (tipo): una empresa con producción anual de 10.000 unidades adquiere 1.000 kg de materia prima. Si cada pedido cuesta 200 € y el coste anual de almacenamiento total es de 2.000 €, al aplicar la fórmula Q = √(2·D·K/G) con D=1.000, K=200, G=2.000 se obtiene Q ≈ 14,14. Eso sugiere lotes de 14 kg y unos 71 pedidos al año. Es un ejercicio ilustrativo donde, con números modestos, se ve cómo el tamaño de lote equilibra pedidos y stock.

Ejemplo 2: Sillas Grandes World SL distribuye 6.000 sillas (D), cada pedido cuesta 300 € (K) y el almacenamiento por unidad al año es 5 € (G). Aplicando la ecuación, Q ≈ 848,52, luego haría unos 7,07 pedidos anuales. Con este tamaño de lote, la firma tiende a un nivel de inventario más eficiente, reduciendo costes de almacenaje sin disparar los costes de preparación de pedidos.

Más allá de la fórmula, conviene calcular el punto de pedido considerando el lead time y mantener stock de seguridad, porque el modelo puro no recoge la incertidumbre. Tampoco estima el impacto de descuentos por volumen que, en ocasiones, podrían compensar costes de stock si se aprovechan lotes mayores.

No confundir con el teorema de Wilson (teoría de números)

El teorema de Wilson pertenece a la aritmética modular y dice, esencialmente, que un entero n > 1 es primo si y solo si (n − 1)! ≡ −1 (mod n). A la implicación “si n es primo entonces (n − 1)! ≡ −1 (mod n)” se la suele llamar estrictamente “teorema de Wilson”, y la implicación recíproca también es cierta. Históricamente, Edward Waring atribuyó el resultado a John Wilson (1770), aunque la primera demostración conocida la dio Lagrange (1771) y, en realidad, la formulación se remonta a Alhacén en el siglo XI.

Ejemplo concreto: para p = 11, al agrupar cada elemento con su inverso multiplicativo en el conjunto {1, 2, …, p − 1}, el producto total resulta ≡ −1 (mod p). Todos los factores se cancelan par a par como g·g^{-1} ≡ 1, excepto 1 y p − 1, y por eso 10! ≡ −1 (mod 11). Este enfoque usa que, con p primo, (Z/pZ)^× es grupo multiplicativo y cada elemento (salvo 1 y p − 1) tiene un inverso distinto.

Hay diversas demostraciones. Una técnica polinómica considera g(x) = (x − 1)(x − 2)···(x − (p − 1)) y f(x) = g(x) − (x^{p−1} − 1). A módulo p, f(x) tendría a lo sumo p − 2 raíces si no fuera el polinomio nulo, pero todos 1, 2, …, p − 1 anulan f(x) por el pequeño teorema de Fermat. Por tanto, f(x) es idénticamente 0 mod p y el término independiente conduce a (p − 1)! ≡ −1 (mod p).

No se utiliza como test práctico de primalidad, porque calcular (n − 1)! mod n para n grande es costoso y existen pruebas más rápidas (como Miller–Rabin o deterministas para rangos concretos). Aun así, sirve para deducir propiedades útiles: por ejemplo, si p = 2n + 1 es primo, se obtiene ∏_{j=1}^{n} j^2 ≡ (−1)^{n+1} (mod p). Y, como corolario parcial, −1 es un residuo cuadrático módulo p si p ≡ 1 (mod 4), pues se puede escribir como el cuadrado del producto 1·2···2k cuando p = 4k + 1, lo que muestra cuándo −1 es cuadrado en Z/pZ.

Existe además un “inverso” a efectos prácticos: para cualquier compuesto n > 5, se cumple que n divide a (n − 1)!. El caso n = 4 es la excepción clásica (3! no es múltiplo de 4). Una manera de verlo es contar las potencias de un primo q que divide n: en (n − 1)! hay suficientes múltiplos de q como para cubrir la potencia que aparece en n, salvo en la excepción indicada, lo que lleva al resultado salvo para n = 4.

Gauss generalizó el teorema: el producto de todas las unidades módulo n, ∏_{1≤a<n, (a,n)=1} a, es ≡ −1 (mod n) si n ∈ {4, p^k, 2p^k} con p impar primo, y ≡ 1 (mod n) en los demás casos. Desde la óptica de grupos abelianos finitos, el producto de todos sus elementos es la identidad salvo que exista exactamente un elemento de orden 2, en cuyo caso el producto es ese elemento de orden 2.

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

En la siguiente tabla puedes ver valores concretos para n entre 2 y 30. Para n primo, el resto de (n − 1)! al dividir por n coincide con n − 1 (que es ≡ −1 mod n). En los compuestos, frecuentemente el resto es 0. Se incluyen también −1 mod n para comparar. Estos datos ilustran muy bien cómo se comporta el teorema de Wilson en los casos pequeños y ayudan a fijar la intuición.

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

Aplicaciones, límites y recomendaciones

Si buscas generar laberintos sin sesgos, usa el algoritmo de Wilson: su base en caminatas aleatorias con borrado de bucles asegura árboles uniformes. Para inventarios, el Modelo Wilson es útil cuando demanda, precios y costes son estables y se conocen con precisión; en entornos volátiles, metodologías como Kanban, JIT o software de planificación avanzado pueden ser más adecuados. Y en matemáticas, el teorema de Wilson es una joya teórica con derivaciones interesantes (como los residuos cuadráticos), pero no es práctico como test de primalidad para números grandes.

Para el cálculo del coste de pedido y de almacenamiento, no hay una “fórmula universal”: cada empresa debe desglosar horas, procesos, transporte, recepción, personal, alquileres, energía, seguros y costes financieros. Muchos profesionales estiman horas por operación y aplican una tarifa horaria para monetizar. Esta personalización es clave para que la Q calculada sea útil y, junto con un buen punto de pedido y stock de seguridad, evitar rupturas o exceso de inventario.

Conviene recordar que el término “algoritmo de Wilson” en búsquedas suele apuntar al generador de laberintos, mientras que “Modelo de Wilson” o “EOQ” remite a inventarios y “teorema de Wilson” a teoría de números. Distinguirlos desde el principio evita confusiones y te permite aprovechar mejor cada enfoque: laberintos sin sesgos, lotes óptimos bajo supuestos realistas y una caracterización elegante de los primos que, aunque no sea una prueba de primalidad práctica, sigue siendo una pieza preciosa del rompecabezas matemático.