2020年3月24日火曜日

制約記述は、何故~禁止 になるか?

制約の書き方として、Pythonも含めてですが、~禁止という書き方が非常に多い ことに気付いていると思います。今日は、何故、そのような書法になってしまうのかを考えたいと思います。

結論的に言うと、「できる限り解空間を狭めないため」、別な言い方をすれば、「決め付けないことにより、可能性を残すため」であります。

例えば、禁止の反対は、強制になりますが、そのような制約は、列制約にしか許していませんし、そもそも「強制」制約を使った記述は、サンプルでもほぼ皆無と言ってもよいと思います。

例えば、そのシフトに強制してしまうと、それ以外は、許されないことになってしまいます。非常に強い制約となり最終的な記述でもあります。このほかの制約は不要である、といったときだけに使用可能です。なにしろ、他を許していないことから、発展性がない、とも言えます。
「強制」 →「これしか許さない」→「他は許さない」
これになにか付加する制約は許されない、ということになります。


一方、禁止記述ですが、
Aは禁止
Bは禁止
....
禁止条項は、空集合にならない限りいくらでも付加していけます。つまりある場面では、

Aは禁止

別な場面では、

Aは禁止
Bは禁止

さらに別な場面では、
Aは禁止
Bは禁止
Cは禁止

というように、汎用性があって柔軟な記述は、禁止により記述していく方法なのです。
これは、制約のANDで記述していることに他なりません。これをCNF(Conjunctive normal form)
と言います。SATで記述する方法そのものです。 (SAT世界でのCNFとDNFは、OR世界でのPrimal-Dual にアナロジーを感じるのは私だけでしょうか)

ところが、

Aに強制


では、他に記述のしようがありません。これ以外に許されないので、発展性のない記述になります。

<メンテナンス>
一つの月で設定した制約記述が未来永劫同じであることはありえません。多かれ少なかれ、
変更が伴うものです。そのとき、Aに強制で、記述してしまっていると、一旦その記述は削除して再度記述し直すことが必要になります。一方、禁止記述の方は、削除でなく追加で済む場合が多いです。メンテナンス性に優れているのは、禁止記述の方です。

<解空間>
よくシフトパターンで、~禁止で記述しますが、強制でも記述可能かもしれません。でも仮にそういう風に記述できたとして、果たして解空間は、どうなってしまうでしょうか?
それ以外を許さないのですから、解空間は大幅に狭まり、容易に解が空集合になってしまうでしょう。理想パターンを一つ決めて、それで解が得られる系であれば、それでもよいです。ですが、その系は、大幅にリソース(人的資源)に余裕がある職場でなけれなりません。さもないと解が空集合、解がないことになってしまいます。NSP問題は、そんな流暢なことは言っていられない、リソーストレードオフのせめぎあい、戦場が一般的です。

~禁止の背景をご理解頂ければ幸いです。



0 件のコメント:

コメントを投稿