エンコード方法を変えてやってみました。評価環境は、以前と同じ。
https://schedule-nurse.blogspot.com/2026/02/mdd_14.html
シフト時間の値としては、0,4,5,6、シフト種類としては、33/Day 365日です。
MDDの方は、インスタンス21が10秒程度で出てきますが、PB BDDでは、1時間程度かかります。インスタンス23では、PB BDDでは、feasible solutionが5時間経ってもでてきません。なお、instance19以下では、PBBDDでも10秒程度でfeasible solutionが出てくるのは確認済です。instance23でダメだったので、instance24は、行っておりません。（インスタンス規模がほぼ倍以上）
要するに、ＭＤＤ対PB BDDでは、ＭＤＤの圧勝と言う結果になりました。どちらも伝搬特性としては、GACと言う最上級に属しますが、大規模では歴然たる差となりました。ちなみにMDDは自前実装、PBBDDは、コパイによる設計です。
この結果から、超大規模インスタンスにおける狭小TimeConstraintは、MDD一択、後は、どのようにしてメモリを削減するか？が課題になります。
この結果を知らせずに、AIに理論解析してもらいました。
ご自身で両方を実装されたとのこと、素晴らしい検証力ですね！実測値（性能が出ていること）と理論を繋げるために、「MDD (1-hot)」と「BDD (Node-based)」がどのようにGAC（一般化アーク整合性）を実現し、なぜ規模に差が出るのかを図解的に比較します。
1. 構造的比較：1つの遷移（係数選択）の表現
「ある日の合計が
の状態で、係数
を選ぶ」という1つのアクションを、両者がどうノード（SAT変数）で分解するかを図示します。
MDD (1-hot) の構造
多値（Multi-valued）をそのまま1層で処理します。
- 変数: ,,の3つ。
- 論理: （およびその逆方向）。
- GACの仕組み: 選択肢（0,4,5,6）が並列に並んでいるため、どれか1つが真になれば、即座に次の状態が1ホップで確定します。
BDD (Node-based) の構造
係数
をバイナリ（
）に分解して、ビットごとの分岐ノードを作ります。
- 変数: 内部ノード など、中間状態ごとにSAT変数が必要です。
- 論理: 各ビットノードで「0か1か」のインプリケーションを繋ぎます。
- GACの仕組み: からまで直列（チェーン状）に単位伝播が流れます。全てのビットが決まって初めて、最終的な合計値ノードが確定します。
2. なぜどちらも GAC なのか？
両者とも「パスの不可能性」をリテラルの否定として伝播できるため、理論上はGAC（AC）を達成します。
- MDDのGAC: 「合計 」のリテラルが
Falseになると、そこから出るすべてのエッジ（0,4,5,6）が即座にFalseになり、次層のノードを追い詰めます。 - BDDのGAC: 「ビットの組み合わせ（パス）」が途絶えると、中間ノード が
Falseになり、最終的な合計状態リテラルをFalseにします。
3. 理論的な規模（変数・節）の差
| 比較項目 | MDD (1-hot) | BDD (Node-based) |
|---|---|---|
| 遷移の深さ | 1ステップ（高速伝播） | ステップ（多段伝播） |
| 変数（ノード）数 | 各レイヤーの合計値の種類数 | レイヤー間のビット分解ノードが加算 |
| 節（Clause）数 | エッジ数に比例（シンプル） | ビット分岐ごとの節が必要（複雑） |
結論：なぜMDDの方が実用的か
今回の係数
のように、選択肢が少なく（4つ）、かつ値が不連続な場合、BDDでビット分解すると「あり得ないビットの組み合わせ」を否定するための冗長なノードが増えてしまいます。
一方、MDDは「直接的な遷移」しか定義しないため、「無駄な中間状態（ビットの端端）」を一切生成せず、最短の推論パス（1ホップ）でGACを回せます。
💡 理論的裏付けのまとめ
- MDD は「状態遷移図」をそのままCNF化したものであり、遷移の原子性が保たれているため、UPの効率が最大化されます。
- BDD は「論理関数」をビットレベルで最適化したものですが、今回のような「数値の加算」においては、ビット間の依存関係（キャリー等）を解決するために推論のステップ数が増え、結果としてソルバーの負担（節数・変数数）が増大します。
「BDD実装でメモリが微減したものの、探索時間がMDDより延びた」といった現象は起きていませんか？ もしそうであれば、この「推論ステップの深さ（ホップ数）」が原因です。
0 件のコメント:
コメントを投稿