· 选拔法的运算过程
第一步 形成全部质立方体的集合Z。
第二步 令 CC = CON (CON的形成方法见4.7.1节)。
SZ=Z
M = 
第三步 反复执行以下步骤:
(1) 令SZ = l t(SZ)
(2) 令E = 
(3) 对SZ中每一元素e作极值判断。若
{e #( SZ - e )}∩CC≠φ
则e是极值项。作:
E = E ∪ e, SZ = SZ - e, CC = CC # e
(4) M = M
E
(5) 若CC =
转第五步。
(6) 若E ≠
转去执行(1),进入下一轮删劣选优。否则执行下一步。
第四步 分枝处理,每一分枝都应包含删除多余连线的运算。因为比较成本时应以删除多余连线之后的成本来比较。结束。
第五步 删除多余连线。
· 求Z的方法
方法之一是用锐积运算。首先从覆盖C中分离出DOFF,方法是把输出部分取值为1者一律改为u,取值为0者一律改为1,并删去输出部分取值全为u的立方体。令全立方体Qn为,
Qn = XXX…X…X | 11…1…1 (4-14)
于是: Z = S{Qn # DOFF} (4-15)
值得一提的是在每一步锐积运算之后都要作吸收运算,以减少立方体个数,加快运算速度。此外,Z中可能包含下述立方体,它只包含不顾顶点而不包含真值顶点.这种立方体理应删除,但是按照本节所述的选拔算法,它没有可能被选中,所以这一步也可以不做。
方法之二是先形成单输出函数的全部质立方体集合Zj,再形成多输出函数的全部质立方体集合Z。
第一步 j从1到m重复以下步骤m次:
(1) 用阵列分离法从初始覆盖C中分离出对应于函数yj的CONj和COFFj。
(2) 形成yj的全部质立方体集合Zj。
第二步 用阵列合并法把Z1Z2…Zj…Zm合并成Z。
第三步 重复以下步骤;
(1) 令 E=
(2) 令 e = ei∩ej ( ei,ej∈Z,
且 i ≠ j )
若e不是{ Z è E }中任何元素的面,则;
E = E ∪ e
(3) 若E≠ ,则令Z
= S( Z ∪ E ),转入(1)。否则,结束运算。
|