- ウィルソンのアルゴリズムは、ループ削除ウォークを使用して、迷路を均一なランダムツリーとして生成します。
- ウィルソンモデル (EOQ) は、安定した需要と価格による最適なロットサイズを計算しますが、割引や季節性は考慮しません。
- ウィルソンの定理は、素数を(n−1)! ≡ −1 (mod n)で特徴付け、古典的な一般化を持っています。
インターネット上では、「ウィルソン」という用語は様々な意味で使われており、非常に紛らわしい。例えば、迷路生成アルゴリズム、ウィルソン在庫モデル（またはEOQ）、そして数論におけるウィルソンの定理などがある。本稿では、迷路における本来の意味から始め、他の意味を丁寧に区別しながら、それら全てを明確にする。なぜなら、これらは同じものではなく、同じ分野に適用されるものでもないからだ。
迷路が自動的に「成長」するデモやアプレットを見たことがあるなら、おそらくウィルソンのアルゴリズムに既に出会っているでしょう。経済発注量を計算するためのウィルソンモデルや、階乗を用いて素数を特徴づける定理についても耳にしたことがあるかもしれません。ここでは、それぞれの概念を理解し、正しく使えるように、例を交えながら詳しく解説します。
迷路のウィルソンアルゴリズムとは何ですか?
ウィルソンのアルゴリズムは、ループ消去ランダムウォークに基づく迷路生成手法です。その主な利点は、グリッド全体にわたって均一なランダム全域木を生成することです。つまり、あらゆる可能な迷路が、特定の方向やパターンに偏ることなく、同じ確率で出現します。
重要な点は、既存のネットワークに経路が追加されるが、ランダムな経路が自身と交差すると、そのループは「消去」され、経路は自由になった地点から再開されるということである。この仕組みにより、冗長な長い経路が優先されたり、サイクルが発生したりするのを防ぎ、すべてのセルを接続するツリー構造を維持する。結果として「公平な」迷路が完成する。つまり、どの経路や曲がり角も、他の経路や曲がり角に対して統計的に有利になることはない。
コミュニティが作成したプロジェクトやアプレットの中には、アルゴリズムの動作を視覚的かつ楽しく示すものがあります。中でも、Cruz Godar氏のアプレットは秀逸で、グリッドサイズを選択して実行することで、迷路が段階的にどのように出現していくかを見ることができます。実行の様子を見ることで、ループ消去がグラフの各拡張における確率を均一化する理由を理解するのに役立ちます。
迷路の作成と解決は、一見ゲームのように思えるが、探索と最適化の問題と密接に関連している。迷路を設計するには、明快さと面白さのバランスを取り、安易な解決策や行き止まりを避け、限られた空間を膨大な組み合わせで探索する必要がある。そのため、紙の上でもデジタルシミュレーションでも、迷路は論理、確率、そして忍耐力を養う優れた訓練となる。
仕組み（実際）
以下に、アルゴリズムの概要を説明します。コードは示しませんが、動作を理解するための基本的な仕組みを解説します。目標は、すべてのセルを接続する（サイクルのない）ツリーを構築し、任意の2点間に単純なパスが1つだけ存在するようにすることです。
- 空のグリッドから始まり、セルがランダムに選択され、ツリーの一部としてマークされます。
- 別のセルがランダムに選択され、ステップバイステップのランダムウォークが開始され、パスがそれ自体と交差する場合、ループは直ちに削除されます (ループ消去)。
- ウォークがすでに生成されているツリーに到達すると、改良されたパス全体 (ループなし) がツリーに「接着」されます。
- これを繰り返します。つまり、接続されていない新しいセルを選択し、ループ削除をしながら進み、ツリーに結合します。
- 最終的にすべてのセルが接続され、迷路は均一なランダムスパニングツリーとなるので、 方向性や位相的な偏りはない.
他の手法（Aldous-Broder法、Prim法、迷路に適用したKruskal法など）と比較すると、Wilson法は全域木サンプリングの均一性において際立っています。一般的なグリッドでは計算コストも妥当であり、何よりも、各解が等確率であることを保証している点が大きな利点です。これは、学術研究やシミュレーションの分野で非常に高く評価されている点です。
他の意味: ウィルソンモデルまたはEOQ（在庫）
物流におけるウィルソンモデル（EOQ、経済発注量とも呼ばれる）は、迷路とは全く関係ありません。これは、総在庫コストを最小化するための最適な発注量を決定する古典的な手法です。このモデルは1934年にR.H.ウィルソンによって広く知られるようになりましたが、その概念自体は1913年にフォード・ホイットマン・ハリスによって提唱されました。
その目的は、発注コストと在庫保管コストのバランスが取れるロットサイズQを見つけることです。年間需要(D)、1回の発注あたりのコスト(K)、および1単位あたりの期間保管コスト(G)に基づいて、その前提条件の範囲内で総在庫コストを削減する数量が得られます。
最も一般的な式は Q = √(2·D·K/G) で表されます。この数値は各バッチのサイズを示し、そこから年間発注回数は D/Q となり、これを用いて発注サイクルを導き出すことができます。基本的な式には不確実性が明示的に組み込まれていませんが、在庫切れを避けるために、発注点（リードタイムを考慮して）と安全在庫を設定することも重要です。
典型的な用途：原材料や、購入費用と保管費用を確実に算出できるあらゆる種類の商品に使用されます。実際には、D、K、Gを十分な精度で把握することで、企業はバッチサイズを決定し、調達スケジュールをより適切に管理することができます。
ウィルソンモデルの前提、利点、限界
前提条件は結果の妥当性にとって非常に重要です。EOQモデルは、需要が一定かつ既知であること、単価が安定していること、保管コストが既知であり在庫レベルに依存すること、リードタイムが一定であること、さらに数量割引を考慮しないことを前提としています。
- 季節性や突然のピークがなく、安定した独立した需要。
- 分析期間中、購入価格は固定または実質的に変更されません。
- 単位および期間あたりの既知の保管コスト。
- 数量割引はなく、即時または継続的に補充されます。
主な利点：導入が容易で広く利用されており、その条件の下で発注および在庫コストを最小限に抑えるのに役立ちます。メリットとしては、過剰在庫の削減、在庫切れリスクの低減（再発注点と安全在庫と組み合わせた場合）、購買計画の明確化などが挙げられます。多くの組織は、発注数量を決定するための明確な数値的根拠を提供するという点で、このシステムを高く評価しています。
デメリット：季節変動や不規則な需要には対応しにくく、数量割引を無視し、即時（または固定）補充を前提としているため、多くのサプライチェーンでは非現実的です。そのため、トヨタグループのような環境では、EOQ方式は、実際の変動や継続的な流れに適切に対応できるカンバン方式やジャストインタイム方式といった、より堅牢なシステムに取って代わられています。
EOQの実例（ウィルソン）
例1（典型例）：年間生産量10.000個の企業が、1.000kgの原材料を仕入れます。1回の注文につき200ユーロ、年間保管費用が合計2.000ユーロの場合、Q = √(2·D·K/G) の式にD=1.000、K=200、G=2.000を代入すると、Q ≈ 14,14となります。これは、1バッチあたり14kg、年間約71回の注文を示唆しています。これは、小規模な数値で、バッチサイズが注文と在庫のバランスをどのように取るかを示すための例示です。
例2：Sillas Grandes World SL社は6.000脚の椅子（D）を販売しており、1回の注文につき300ユーロ（K）、1脚あたりの年間保管費用は5ユーロ（G）です。この式を適用すると、Q ≈ 848,52となり、同社は年間約7,07回の注文を行うことになります。このロットサイズであれば、同社はより効率的な在庫レベルに近づき、注文準備コストを大幅に増加させることなく保管コストを削減できます。
数式そのものに加えて、リードタイムを考慮して発注点を計算し、安全在庫を維持することが推奨されます。なぜなら、純粋なモデルでは不確実性が考慮されていないからです。また、大量購入による割引の影響も推定されていません。大量購入の場合、割引によって在庫コストが相殺されることがあります。
ウィルソンの定理（数論）と混同しないように注意する
ウィルソンの定理はモジュラー算術に属し、本質的には、整数 n > 1 が素数であるのは (n − 1)! ≡ −1 (mod n) が成り立つ場合のみである、と述べている。「n が素数ならば (n − 1)! ≡ −1 (mod n)」という含意は、通常厳密には「ウィルソンの定理」と呼ばれ、その逆もまた真である。歴史的には、エドワード・ウォーリングはこの結果をジョン・ウィルソン (1770 年) に帰属させたが、最初に知られている証明はラグランジュ (1771 年) によって与えられ、その定式化自体は実際には 11 世紀のアルハゼンにまで遡る。
具体的な例：p = 11 の場合、集合 {1, 2, …, p − 1} の各要素をその乗法逆元とグループ化すると、合計積は ≡ −1 (mod p) になります。1 と p − 1 を除いて、すべての因数はペアごとに打ち消し合い、g·g^{-1} ≡ 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) を考えるものです。f(x) が零多項式でない場合、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 を計算するのはコストがかかり、より高速な判定法 (ミラー・ラビン判定法や特定のランクに対する決定論的判定法など) が存在するからです。それでも、有用な性質を導き出すために使うことができます。例えば、p = 2n + 1 が素数であれば、∏_{j=1}^{n} j^2 ≡ (−1)^{n+1} (mod p) が得られます。また、部分的な系として、p ≡ 1 (mod 4) であれば −1 は p を法とする平方剰余となります。これは、p = 4k + 1 のときに−1 をZ/pZ で二乗すると、積 1·2···2k の二乗として表せるためです。
実用的な「逆」もあります。任意の合成数 n > 5 に対して、n は (n − 1)! を割り切ります。n = 4 の場合は典型的な例外です (3! は 4 の倍数ではありません)。これを確認する 1 つの方法は、n を割り切る素数 q のべき乗を数えることです。(n − 1)! には、n に現れるべき乗をカバーするのに十分な q の倍数がありますが、前述の例外を除いて、n = 4 の場合を除いて、次の結果が得られます。
ガウスはこの定理を一般化し、n を法とするすべての単位の積 ∏_{1≤a<n, (a,n)=1} a は、p が奇素数である n ∈ {4, p^k, 2p^k} の場合、≡ −1 (mod n) であり、それ以外の場合は ≡ 1 (mod n) である。有限アーベル群の観点からは、位数 2 の要素がちょうど 1 つ存在する場合を除き、すべての要素の積は恒等式であり、その場合は積はその位数 2 の要素となる。
n = 2…30 の場合の (n − 1)! mod n の表
次の表は、2 から 30 までの n の具体的な値を示しています。素数の場合、(n − 1)! を n で割った余りは n − 1 (≡ −1 mod n) になります。合成数の場合、余りは 0 になることがよくあります。比較のために −1 mod 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 |
アプリケーション、制限、推奨事項
偏りのない迷路を生成したい場合は、ウィルソンのアルゴリズムを使用してください。ループ消去を伴うランダムウォークを基本としているため、均一なツリーが保証されます。在庫管理においては、需要、価格、コストが安定していて正確に分かっている場合にウィルソンモデルが役立ちます。変動の激しい環境では、カンバン、ジャストインタイム、高度な計画ソフトウェアなどの手法の方が適している場合があります。また、数学においては、ウィルソンの定理は（二次残差などの）興味深い導出を含む理論的な宝ですが、大きな数の素数判定には実用的ではありません。
発注および保管コストを計算するための単一の公式はありません。各企業は、作業時間、工程、輸送、受入、人件費、賃料、エネルギー、保険、財務コストを個別に分析する必要があります。多くの専門家は、作業ごとの作業時間を見積もり、時間単価を適用して収益化を図っています。このようなカスタマイズは、算出された発注量（Q）が有用であることを保証するために重要であり、適切な発注点と安全在庫と併せて、在庫切れや過剰在庫を回避するのに役立ちます。
検索において「ウィルソンのアルゴリズム」という用語は通常迷路生成器を指し、「ウィルソンモデル」または「EOQ」は在庫管理を、「ウィルソンの定理」は数論を指すことを覚えておくと良いでしょう。これらを最初から区別することで混乱を避け、それぞれの手法をより有効に活用できます。例えば、バイアスのない迷路、現実的な仮定の下での最適なバッチ、そして実用的な素数証明ではないものの、数学的なパズルの貴重なピースとなる素数の洗練された特徴付けなどです。
