一种有效的分层加权库编译方法

摘要

提议对加权库进行分层,一方面符合人类的思维习惯,另一方面能够提高推理效率.首先说明现有的针对非分层加权库的编译方法也适用于编译分层加权库,但是,由于存在较多冗余信息而效率不高.提出一种新的编译方法,能够在编译过程中去除冗余信息,并提出两种优化技术提高时间效率.该方法与现有方法相同,当软约束权值改变时无需重新编译.选择ROBDD为目标语言,使用随机问题对该方法进行测试.结果表明:对于非分层加权库,该方法的空间效率高于已存在方法 ;对于分层加权库,该方法的时间和空间效率均高于已存在方法,且当层数越多时,该方法的效率越高.%To be in accordance with the thinking habits of human and improve the efficiency of reasoning, this study argues to stratify weighted bases. The study shows that the existing compilation approach to non-stratified weighted bases can also be applied to COMPILE stratified weighted bases; however, its time and space costs are relatively high because of redundant information in the compilation results. The paper proposes a novel compilation approach, which can remove the redundant information in the process of compilation, and presents two optimization techniques to further improve the time efficiency. As with the existing approach, re-compiling a stratified weighted base is not required whenever the weights associated with soft constraints change with time. The approach is tested by compiling random instances into ROBDD-normal bases, and the preliminary experimental results show that the time and space costs of this approach are lower than the existing approach for most instances.