- 威尔逊算法使用循环删除步行将迷宫生成为均匀随机树。
- 威尔逊模型（EOQ）计算需求和价格稳定的最佳批量，但不考虑折扣或季节性。
- 威尔逊定理用 (n−1)! ≡ −1 (mod n) 来描述素数，并且有经典的推广。
在互联网上，“威尔逊”一词的用法五花八门，令人困惑：它既指用于生成迷宫的威尔逊算法，也指威尔逊库存模型（或经济订货量模型），还指数论中的威尔逊定理。本文将从其在迷宫生成中的最初用法入手，逐一阐明其含义，并仔细区分其他各种解释，因为它们并非同一概念，也不属于同一领域。
如果你看过迷宫自动“生长”的演示或小程序，那你可能已经接触过威尔逊算法了。你也可能听说过威尔逊模型（用于计算经济订货量）或者用阶乘表征素数的定理。在这里，你会找到完整的解释和示例，帮助你理解并正确运用每个概念。
威尔逊迷宫算法是什么？
威尔逊算法是一种基于消除环路随机游走的迷宫生成方法。它的主要优点在于能够生成覆盖整个网格的均匀随机生成树：简而言之，每个可能的迷宫出现的概率都相同，不会偏向任何特定的方向或模式。
其核心思想是，路径会添加到现有网络中，但当一条随机路径与自身相交时，环路会被“消除”，路径会从不再相交的点继续延伸。这一细节避免了路径冗余或形成循环，从而保持了连接所有单元格的树状结构。最终得到的是一个“公平”的迷宫：任何路径或转弯在统计上都不具有优势。
社区创建了一些项目和小程序，以直观有趣的方式演示了该算法的运行过程。其中，Cruz Godar 的一些小程序尤为突出，用户可以选择网格大小并运行程序，观察迷宫如何逐步生成。观看运行过程有助于理解为什么循环消除会在图的每次扩展中使概率趋于平衡。
构建和解决迷宫看似游戏，实则与搜索和优化问题密切相关。设计迷宫需要在清晰性和趣味性之间取得平衡，避免平庸的解法或死胡同，并在有限的空间内探索丰富的组合。因此，无论是在纸上还是在数字模拟中，迷宫都是锻炼逻辑思维、概率论和耐心能力的绝佳途径。
工作原理（实际操作）
以下是对该算法的概要描述，不包含代码，但包含了理解其运行机制所需的基本原理。请记住，目标是构建一棵连接所有单元格的树（无环），使得任意两点之间只有一条简单路径。
- 它从一个空网格开始：随机选择一个单元格并将其标记为树的一部分。
- 随机选择另一个单元格，开始逐步随机游走，如果路径与自身相交，则立即删除循环（循环擦除）。
- 当步行到达已经生成的树时，整个细化的路径（没有循环）就会“粘”到树上。
- 它重复：我们选择一个新的未连接的单元，循环删除并加入树。
- 最后，所有单元格都连接起来，迷宫是一个均匀随机生成树，因此 没有方向或拓扑偏差.
与其他方法（例如适用于迷宫的 Aldous-Broder、Prim或 Kruskal 方法）相比，Wilson 方法的突出之处在于其生成树采样的均匀性。在典型的网格上，它的计算成本合理，而且最重要的是，它保证了每个解的概率相等，这在学术研究和模拟环境中都非常重要。
其他含义：威尔逊模型或 EOQ（库存）
在物流领域，威尔逊模型（也称经济订货量，EOQ）与迷宫毫无关系。它是一种经典的确定最优订货量以最小化总库存成本的方法。该模型由R.H.威尔逊于1934年推广，但其最初概念由福特·惠特曼·哈里斯于1913年提出。
其目的是找到使订货成本和库存持有成本达到平衡的批量大小 Q。基于年需求量 (D)、每次订货成本 (K) 和每单位每期存储成本 (G)，可以得到一个在既定假设框架内能够降低总库存成本的批量大小。
最常用的公式是 Q = √(2·D·K/G)。该数值表示每批次的规模；由此可得年订单量 D/Q，进而推导出订货周期。此外，设定再订货点（需考虑提前期）和安全库存以避免缺货也至关重要，尽管基本公式并未明确考虑不确定性。
典型应用：适用于原材料或任何类型的商品，只要采购和仓储成本能够可靠确定即可。实际上，通过充分可靠地掌握D、K和G值，公司可以更有效地控制批量大小和采购计划。
威尔逊模型的假设、优势和局限性
这些假设对结果的有效性至关重要。经济订货量模型假设需求恒定且已知，单价保持稳定，仓储成本已知且取决于库存水平，交货周期恒定，此外，该模型不考虑批量折扣。
- 稳定、独立的需求，没有季节性或突然的高峰。
- 在分析期间内，购买价格固定或几乎没有变化。
- 已知每单位和每期间的存储成本。
- 无数量折扣，且不立即或持续补货。
主要优势：实施简便，应用广泛，并有助于在规定范围内最大限度地降低订货和库存成本。其益处包括减少库存积压、降低缺货风险（与再订货点和安全库存结合使用时），以及提高采购计划的清晰度。许多组织重视它，因为它为确定订货量提供了直接的数值依据。
缺点：它不适用于季节性或不规则需求，忽略了批量折扣，并且假设补货是即时（或固定）的，这在许多供应链中是不现实的。因此，在像丰田集团这样的环境中，经济订货量（EOQ）公式已被看板或准时制（JIT）等更强大的系统所取代，这些系统能更好地应对实际的波动性和连续的供应链。
EOQ 的实际例子（Wilson）
例1（典型）：一家年产量为10.000件的公司采购了1.000公斤原材料。如果每笔订单的成本为200欧元，年度总仓储成本为2.000欧元，则应用公式Q = √(2·D·K/G)，其中D=1.000，K=200，G=2.000，得出Q ≈ 14,14。这表明每次采购量应为14公斤，每年大约需要71笔订单。这是一个示例性的例子，通过较小的样本量，我们可以看到批量大小如何平衡订单和库存。
例 2：Sillas Grandes World SL 公司经销 6.000 把椅子 (D)，每笔订单成本为 300 欧元 (K)，每把椅子的年仓储成本为 5 欧元 (G)。根据公式，Q ≈ 848,52，这意味着该公司每年大约需要下 7,07 笔订单。在这种批量下，该公司倾向于采用更高效的库存水平，在不显著增加订单准备成本的情况下降低仓储成本。
除了公式本身之外，建议在计算再订购点时考虑提前期并维持安全库存，因为纯粹的模型没有考虑不确定性。它也没有估算批量折扣的影响，而批量折扣有时可以在大批量生产时抵消库存成本。
不要与威尔逊定理（数论）混淆
威尔逊定理属于模运算范畴，其本质是：大于 1 的整数 n 为素数当且仅当 (n − 1)! ≡ −1 (mod n)。“若 n 为素数，则 (n − 1)! ≡ −1 (mod n)”这一蕴含式通常被严格地称为“威尔逊定理”，其逆命题也成立。历史上，爱德华·沃林将此结果归功于约翰·威尔逊（1770 年），尽管已知的第一个证明是由拉格朗日（1771 年）给出的，而该定理的表述实际上可以追溯到 11 世纪的阿尔哈曾。
具体例子：当 p = 11 时，将集合 {1, 2, …, p − 1} 中的每个元素与其乘法逆元分组，则总乘积为 ≡ −1 (mod p)。所有因子两两抵消，因为 g·g⁻¹ ≡ 1，除了 1 和 p − 1 之外，因此10! ≡ −1 (mod 11)。这种方法利用了以下事实：当 p 为素数时，(Z/pZ)⁻¹ 是一个乘法群，并且每个元素（除了 1 和 p − 1 之外）都有不同的逆元。
有几种证明方法。一种多项式技巧考虑 g(x) = (x − 1)(x − 2)···(x − (p − 1)) 和 f(x) = g(x) − (x^{p−1} − 1)。模 p，如果 f(x) 不是零多项式，则至多有 p − 2 个根，但根据费马小定理，所有 1, 2, …, p − 1 都使 f(x) 为零。因此，f(x) 模 p 恒等于 0；常数项导致(p − 1)! ≡ −1 (mod p)。
它不常被用作素性的实际检验方法，因为计算大 n 时的 (n − 1)! mod n 非常耗时，而且存在更快的检验方法（例如 Miller-Rabin 检验或针对特定秩的确定性检验）。即便如此，它仍然可以用来推导出一些有用的性质：例如，如果 p = 2n + 1 是素数，我们得到 ∏_{j=1}^{n} j^2 ≡ (−1)^{n+1} (mod p)。并且，作为部分推论，如果 p ≡ 1 (mod 4)，则 −1 是模 p 的二次剩余，因为当 p = 4k + 1 时，它可以写成乘积 1·2···2k 的平方，这表明 −1在 Z/pZ 中的平方。
还有一个实际的“逆”：对于任何大于 5 的合数 n，n 都能整除 (n − 1)!。n = 4 的情况是一个经典的例外（3! 不是 4 的倍数）。一种理解方法是计算能整除 n 的素数 q 的幂：在 (n − 1)! 中，q 的倍数足以涵盖 n 中出现的幂，除了上述例外情况，这导致了除 n = 4 之外的结果。
高斯推广了该定理：所有模 n 的单位元的乘积，∏_{1≤a<n, (a,n)=1}a，若 n ∈ {4, p^k, 2p^k} 且 p 为奇素数，则 ≡ −1 (mod n)；在所有其他情况下，则 ≡ 1 (mod n)。从有限阿贝尔群的角度来看，除非恰好存在一个阶为 2 的元素，否则其所有元素的乘积都是单位元；若存在一个阶为 2 的元素，则乘积即为该阶为 2 的元素。
(n − 1)! mod n 的说明表，其中 n = 2…30
下表列出了 n 取值在 2 到 30 之间的具体数值。对于质数，(n − 1)! 除以 n 的余数等于 n − 1（即 ≡ −1 mod n）。对于合数，余数通常为 0。表中也包含了 −1 mod n 的值以作比较。这些数据清晰地展示了威尔逊定理在小样本情况下的表现，并有助于巩固直觉。
| n> 1 | （n − 1）！ | (n − 1)! 模 n | −1 模 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 |
应用、限制和建议
如果你想生成无偏迷宫，可以使用威尔逊算法：它基于随机游走并消除环路，从而确保生成均匀的树。对于库存管理，当需求、价格和成本稳定且精确已知时，威尔逊模型非常有用；但在波动较大的环境中，看板、准时制或高级计划软件等方法可能更合适。在数学领域，威尔逊定理是一个理论上的瑰宝，具有许多有趣的推导（例如二次残差），但它作为大数素性检验并不实用。
计算订货和仓储成本没有统一的公式：每家公司都必须细分工时、流程、运输、收货、人员、租金、能源、保险和财务成本。许多专业人士会估算每项操作所需的时间，并采用小时费率进行货币化。这种定制化是确保计算出的订货量 (Q) 有效的关键，并且与合理的再订货点和安全库存相结合，有助于避免缺货或库存过剩。
值得注意的是，在搜索结果中，“威尔逊算法”通常指的是迷宫生成器，而“威尔逊模型”或“经济订货批量”（EOQ）指的是库存管理，“威尔逊定理”则指的是数论。从一开始就区分它们可以避免混淆，并让你更好地利用每种方法：无偏迷宫、在合理假设下的最优批次，以及对素数的精妙刻画——尽管它并非实用的素性证明，但仍然是数学难题中不可或缺的一部分。
