 |
 |
 |
ZDD |  |
 |
|
|
|
|
ZDD | |
|
|
以下では、本マニュアルで利用する専門用語について解説する。 巻末の参考文献で使われている用語と異なることもあるので注意されたい。
本パッケージでは、集合の要素を「アイテム」と呼び、 アイテムを要素に持つ集合を「アイテム集合」と呼ぶ。 スーパーマーケットにおける商品をアイテム、商品の組み合せをアイテム集合と考えれば分かりやすい。 そしてアイテム集合に重みを与えた「項」を要素としてもつ集合を「重み付き積和集合」と呼ぶ。 例えば、3つのアイテムa,b,cについての重み付き積和集合は「abc+3ab+4bc+7c」のように 表記する(この表記形式を「重み付き積和形式」と呼ぶ)。 これは、abc,3ab,4bc,7cの4つの項からから成り立ち、3abは、重みが3のアイテム集合{a,b}であることを意味する。 スーパーマーケットで言えば、3つの商品a,b,cを同時に購入した顧客が1人いて、 a,bを同時に購入した顧客が3人いて、といった意味付けをすると分かりやすいであろう。
要素のないアイテム集合のことを「空アイテム集合」と呼ぶ。 重み付き積和集合「abc+3ab+4bc+7c+3」について考えると、 最後の項3は空アイテム集合の重みが3であることを示している。 スーパーマーケットの例で言えば、何も買わなかった人が3人いたと考えればよい。 また空アイテム集合のZDDオブジェクトのことを特に「ZDD定数オブジェクト」と呼ぶ。
ZDDは2分決定木を縮約した2分決定グラフと呼ばれる構造を持つが、 その2分決定木のレベル(深さ)がアイテム対応している。 そしてそのレベル、すなわち根から葉に向かうアイテムの順序は「アイテム順序表」と呼ばれる表によって管理されている。 このような管理が必要になるのは、アイテムの順序によってZDDのサイズ(節点数)が大きく影響を受けるからである。 ZDDのサイズが大きくなるということは、それに対する演算速度も低下することを意味する。 アイテム順序表はsymbol関数によって随時登録されることになる。 組み合わせ数が極端に大きくなる場合には、登録順序を考慮する必要があるかもしれない。
|
|
|
ZDD | |
|
|