第1期 王金艳，等：扩展规则方法研究综述 5 数来判断子句集的可满足性不同，该方法直接计算 现有其他知识编译方法对偶的一种方法2]。 出不能由子句集扩展出来的相对极大项个数，然后 2)基于启发式策略的知识编译方法。 根据相对极大项个数来判断子句集的可满足性，避 在知识编译中，离线编译后生成的目标知识库 开了容斥原理的复杂性。进一步，他们在基本MC 的规模对在线查询的效率起着至关重要的作用。算 算法的基础上提出了8种优化策略，极大地提高了 法KCER在选择子句和变量进行扩展时，都采用顺 算法的求解效率。 序扩展的方式，几乎没有使用任何启发式策略。对 3)碰集方法。 于有些问题，这会导致编译后的子句集规模过大，从 Xu等[242]找出了不能被扩展出的极大项具有 而影响之后的在线推理的效率。为此，笔者提出了 的特征，以此来回避容斥原理所带来的计算量。他 2种启发式策略MCN(minimum complementary num- 们发现，若极大项与子句集Σ中的某个子句互补， ber)和MO(maximum occurrences)分别用于指导待 则该极大项不能由这个子句扩展出来。进而可知， 扩展的子句和变量的选择[]，MCN策略是优先选 如果极大项与Σ中所有子句都互补，那么该极大项 择与其他子句互补的子句数较少的子句进行扩展， 就不能由Σ扩展出来。假定存在与Σ中任意子句 MO策略是在待扩展的子句中优先选择在其他未扩 都互补的极大项C,那么由C,可以构造极大项 展子句中出现次数最多的变量进行扩展。前者使得 CM,其中C,由Cv中每个文字的补文字构成。如果 需要扩展的子句数较少，后者使得子句被扩展出的 将子句看作文字集合，Σ看作文字集合簇，那么C 子句数较少。使用随机生成的样例和处于相变区的 与Σ中任意子句的交都不为空，即C,是Σ的碰集。 Uniform Random-3-SAT标准用例进行测试，实验结 基于此，Xu等证明了子句集是可满足的，当且仅当 果表明，MCN和MO策略都能大幅度地减小编译后 该子句集存在不包含互补文字的碰集，这样就将 的子句集规模，其中MCN的效果比MO更为明显。 SAT问题转化成判定是否存在不含互补文字的碰集 同时使用MCN和MO策略，可以使扩展后的子句集 问题，并且提出了2种有效的方法CBHST(comple- mentary binary hitting set tree)RNHST(revised new 规模为算法KCER的J 3399 hitting set tree)来进行求解。这2种算法与DR相 3)新的EPCCL编译框架。 比，在效率方面都有1~2个数量级的提高。RNHST 赖永[0证明了如下定理：给定子句集∑=1∧ 算法与CBHST算法相比，RNHST更适合长子句的 ,和EPCCL编译算法f,f八∑，)Af(,VΣ2)是 情况，而CBHST更适合短子句的情况。 与Σ等价的EPCCL理论。基于该定理，他提出了一 2.1.6基于扩展规则的知识编译方法 种新的关于EPCCL理论的知识编译思想：对于给定 I)基于KCER的知识编译方法。 的子句集，首先将其划分为2个子句集三，和2，然 Lin和Sum26指出扩展规则方法可以被应用于 后对它们分别进行编译，合取编译后的结果即可得 知识编译列中，他们定义了EPCCL(each pair con- 到与原子句集等价的EPCCL理论。根据划分后 tains complementary literal)理论（任意2个子句都含 I三I、I,I的不同，存在多种划分方式。如何编译 互补对子句集)，证明了EPCCL理论是在“可满足 Σ，V,又分为2种方式。根据子句集的划分方 可控制类”和“蕴含可控制类”中，并证明对于任意 式、∑，V∑2的编译方式和将DNF(disjunctive nor- 子句集一定能找到一个与之等价的EPCCL理论，因 mal form)编译为EPCCL理论的方法的不同，给出多 此EPCCL理论可以作为知识编译的目标语言，进而 种不同的编译方法。 利用“桶删除”的思想提出将给定子句集编译成 由于编译后的EPCCL理论的规模直接影响到 EPCCL理论的算法KCER(knowledge compilation u- 在线查询效率，刘大有等3)定义了一个规约规则， sing the extension rule)。该方法与现有其他知识编 基于该规则提出了用于缩减EPCCL理论规模的算 译方法的不同之处在于：在编译阶段和推理阶段该 法，该算法具有多项式时间复杂度，然后结合基于 方法都是基于扩展规则的，而其他的知识编译方法 DPLL KCDP knowledge compilation based on 都是基于归结原理的：当互补因子较大的时候，该方 DPLL)算法，实现了C2E编译器。实验结果表明， 法得到的子句集规模相对较小，特别地，当待编译的 不论是编译效率还是编译后子句集的规模都优于基 子句集本身就是一个EPCCL理论，用该方法编译后 于KCER的编译器。在目前的基于DPLL的SAT求 的结果就是其本身，而用其他方法编译，结果可能是 解中，存在许多高效的技术，这些技术都能用于改进 指数级大的。因此，该方法被Murray教授看作是与 KCDP的编译效果，提升C2E编译器的性能。数来判断子句集的可满足性不同，该方法直接计算 出不能由子句集扩展出来的相对极大项个数，然后 根据相对极大项个数来判断子句集的可满足性，避 开了容斥原理的复杂性。 进一步，他们在基本 ＭＣ 算法的基础上提出了 ８ 种优化策略，极大地提高了 算法的求解效率。 ３）碰集方法。 Ｘｕ 等［２４⁃２５］找出了不能被扩展出的极大项具有 的特征，以此来回避容斥原理所带来的计算量。 他 们发现，若极大项与子句集 Σ 中的某个子句互补， 则该极大项不能由这个子句扩展出来。 进而可知， 如果极大项与 Σ 中所有子句都互补，那么该极大项 就不能由 Σ 扩展出来。 假定存在与 Σ 中任意子句 都互补的极大项 ＣＭ ，那么由 ＣＭ 可以构造极大项 ＣＭ ′ ，其中 ＣＭ ′ 由 ＣＭ中每个文字的补文字构成。 如果 将子句看作文字集合，Σ 看作文字集合簇，那么 ＣＭ ′ 与 Σ 中任意子句的交都不为空，即 ＣＭ ′ 是 Σ 的碰集。 基于此，Ｘｕ 等证明了子句集是可满足的，当且仅当 该子句集存在不包含互补文字的碰集，这样就将 ＳＡＴ 问题转化成判定是否存在不含互补文字的碰集 问题，并且提出了 ２ 种有效的方法 ＣＢＨＳＴ（ ｃｏｍｐｌｅ⁃ ｍｅｎｔａｒｙ ｂｉｎａｒｙ ｈｉｔｔｉｎｇ ｓｅｔ ｔｒｅｅ）和 ＲＮＨＳＴ（ｒｅｖｉｓｅｄ ｎｅｗ ｈｉｔｔｉｎｇ ｓｅｔ ｔｒｅｅ）来进行求解。 这 ２ 种算法与 ＤＲ 相 比，在效率方面都有 １～２ 个数量级的提高。 ＲＮＨＳＴ 算法与 ＣＢＨＳＴ 算法相比，ＲＮＨＳＴ 更适合长子句的 情况，而 ＣＢＨＳＴ 更适合短子句的情况。 ２．１．６ 基于扩展规则的知识编译方法 １）基于 ＫＣＥＲ 的知识编译方法。 Ｌｉｎ 和 Ｓｕｎ ［２６］指出扩展规则方法可以被应用于 知识编译［２７］ 中，他们定义了 ＥＰＣＣＬ（ ｅａｃｈ ｐａｉｒ ｃｏｎ⁃ ｔａｉｎｓ ｃｏｍｐｌｅｍｅｎｔａｒｙ ｌｉｔｅｒａｌ）理论（任意 ２ 个子句都含 互补对子句集），证明了 ＥＰＣＣＬ 理论是在“可满足 可控制类”和“蕴含可控制类”中，并证明对于任意 子句集一定能找到一个与之等价的 ＥＰＣＣＬ 理论，因 此 ＥＰＣＣＬ 理论可以作为知识编译的目标语言，进而 利用“桶删除” 的思想提出将给定子句集编译成 ＥＰＣＣＬ 理论的算法 ＫＣＥＲ（ ｋｎｏｗｌｅｄｇｅ ｃｏｍｐｉｌａｔｉｏｎ ｕ⁃ ｓｉｎｇ ｔｈｅ ｅｘｔｅｎｓｉｏｎ ｒｕｌｅ）。 该方法与现有其他知识编 译方法的不同之处在于：在编译阶段和推理阶段该 方法都是基于扩展规则的，而其他的知识编译方法 都是基于归结原理的；当互补因子较大的时候，该方 法得到的子句集规模相对较小，特别地，当待编译的 子句集本身就是一个 ＥＰＣＣＬ 理论，用该方法编译后 的结果就是其本身，而用其他方法编译，结果可能是 指数级大的。 因此，该方法被 Ｍｕｒｒａｙ 教授看作是与 现有其他知识编译方法对偶的一种方法［２８］ 。 ２）基于启发式策略的知识编译方法。 在知识编译中，离线编译后生成的目标知识库 的规模对在线查询的效率起着至关重要的作用。 算 法 ＫＣＥＲ 在选择子句和变量进行扩展时，都采用顺 序扩展的方式，几乎没有使用任何启发式策略。 对 于有些问题，这会导致编译后的子句集规模过大，从 而影响之后的在线推理的效率。 为此，笔者提出了 ２ 种启发式策略 ＭＣＮ（ｍｉｎｉｍｕｍ ｃｏｍｐｌｅｍｅｎｔａｒｙ ｎｕｍ⁃ ｂｅｒ）和 ＭＯ（ｍａｘｉｍｕｍ ｏｃｃｕｒｒｅｎｃｅｓ）分别用于指导待 扩展的子句和变量的选择［２９］ ，ＭＣＮ 策略是优先选 择与其他子句互补的子句数较少的子句进行扩展， ＭＯ 策略是在待扩展的子句中优先选择在其他未扩 展子句中出现次数最多的变量进行扩展。 前者使得 需要扩展的子句数较少，后者使得子句被扩展出的 子句数较少。 使用随机生成的样例和处于相变区的 Ｕｎｉｆｏｒｍ Ｒａｎｄｏｍ⁃３⁃ＳＡＴ 标准用例进行测试，实验结 果表明，ＭＣＮ 和 ＭＯ 策略都能大幅度地减小编译后 的子句集规模，其中 ＭＣＮ 的效果比 ＭＯ 更为明显。 同时使用 ＭＣＮ 和 ＭＯ 策略，可以使扩展后的子句集 规模为算法 ＫＣＥＲ 的 １ ３ ～ １ ３９ 。 ３）新的 ＥＰＣＣＬ 编译框架。 赖永［３０］证明了如下定理：给定子句集 Σ ＝ Σ１ ∧ Σ２ 和 ＥＰＣＣＬ 编译算法 ｆ， ｆ（Σ１ ） ∧ ｆ（ØΣ１ ∨ Σ２ ） 是 与 Σ 等价的 ＥＰＣＣＬ 理论。 基于该定理，他提出了一 种新的关于 ＥＰＣＣＬ 理论的知识编译思想：对于给定 的子句集，首先将其划分为 ２ 个子句集 Σ１和 Σ２ ，然 后对它们分别进行编译，合取编译后的结果即可得 到与原子句集等价的 ＥＰＣＣＬ 理论。 根据划分后 ｜ Σ１ ｜ 、 ｜ Σ２ ｜ 的不同，存在多种划分方式。 如何编译 ØΣ１ ∨ Σ２ 又分为 ２ 种方式。 根据子句集的划分方 式、 ØΣ１ ∨ Σ２ 的编译方式和将 ＤＮＦ（ｄｉｓｊｕｎｃｔｉｖｅ ｎｏｒ⁃ ｍａｌ ｆｏｒｍ）编译为 ＥＰＣＣＬ 理论的方法的不同，给出多 种不同的编译方法。 由于编译后的 ＥＰＣＣＬ 理论的规模直接影响到 在线查询效率，刘大有等［３１］ 定义了一个规约规则， 基于该规则提出了用于缩减 ＥＰＣＣＬ 理论规模的算 法，该算法具有多项式时间复杂度，然后结合基于 ＤＰＬＬ 的 ＫＣＤＰ （ ｋｎｏｗｌｅｄｇｅ ｃｏｍｐｉｌａｔｉｏｎ ｂａｓｅｄ ｏｎ ＤＰＬＬ）算法，实现了 Ｃ２Ｅ 编译器。 实验结果表明， 不论是编译效率还是编译后子句集的规模都优于基 于 ＫＣＥＲ 的编译器。 在目前的基于 ＤＰＬＬ 的 ＳＡＴ 求 解中，存在许多高效的技术，这些技术都能用于改进 ＫＣＤＰ 的编译效果，提升 Ｃ２Ｅ 编译器的性能。 第 １ 期 王金艳，等：扩展规则方法研究综述 ·５·