现介绍一个通过对e反复求余面把e转化为质立方体z的具体方法。i从1到n重复以下步骤:
(1) 令 p = e
(2) 设 p = x1x2…xi…xn ,若xi≠X,则用X置换xi原来的取值。
(3) 若 p∩COFF=φ,则 e = p。 ( p是余面 )
采用收缩法时N中元素单调减少,节约存贮空间。而选拔法先要形成全部质立方体集合Z,当变量个数多时,Z中元素的个数可能远远大于CON中元素的个数.此后再从Z中挑选一个子集M以实现最小化覆盖,这又要花费很多时间。相比之下收缩算法运算时间要小得多。
收缩算法得到的是无冗余覆盖而不是最小化覆盖,而且所得结果和CON中元素的排列顺序有关,也和求余面时用X置换变量原来取值的顺序有关。
收缩算法是在题目很大而计算机能力有限的情况下,用选拔法有困难时退而求其次的办法。
· 降低对目标解的质量要求。
· 减小对计算机能力(存储容量,运算速度)的压力。
|