论文标题：PBCounter: weighted model counting on pseudo-boolean formulas

期刊：Frontiers of Computer Science

作者：Yong LAI, Zhenghang XU, Minghao YIN

发表时间：17 Jan 2024

DOI：https://doi.org/10.1007/s11704-024-3631-1

微信链接：点击此处阅读微信文章

引用格式：

Yong LAI, Zhenghang XU, Minghao YIN. PBCounter: weighted model counting on pseudo-boolean formulas. Front. Comput. Sci., 2025, 19(3): 193402

阅读原文：

问题概述

在传统的加权模型计数问题中，问题的编码往往基于合取范式。但是在许多实际问题中，合取范式并不贴合人类的表示形式，有可能导致问题规模指数爆炸。考虑到伪布尔约束的表示能力比合取范式更强，本文作者撰写了该研究论文，提高了加权模型计数问题的求解能力。

技术步骤

通过将伪布尔约束转化为代数决策图，引入提前映射和簇划分的方法，使用动态规划的算法框架求解加权模型计数问题。并提出了两个适用于伪布尔公式的预处理化简方法。

实验结果

实验结果表明，本文提出的基于伪布尔公式的加权模型技术求解器，在多个测试数据集中，要优于传统的基于合取范式的计数器。说明了在伪布尔公式上计算加权模型数是可行的探索，本文提出的预处理方法也在求解相关问题时大大提高了求解效率。

期刊简介

Frontiers of Computer Science （FCS）是由教育部主管、高等教育出版社和北京航空航天大学共同主办，南京大学支持，SpringerNature 公司海外发行的英文学术期刊。本刊于 2007 年创刊，月刊，全球发行。主要刊登计算机科学领域具有创新性的综述论文、研究论文等。本刊主编为周志华教授，共同主编为熊璋教授。编委会及青年 AE 团队由国内外知名学者及优秀青年学者组成。本刊被 SCI、Ei、DBLP、INSPEC、SCOPUS 和中国科学引文数据库（CSCD）核心库等收录，为 CCF 推荐B类期刊；两次入选“中国科技期刊国际影响力提升计划”；入选“第4届中国国际化精品科技期刊”；两次入选“中国科技期刊卓越行动计划”（一期梯队、二期领军）。

中国学术前沿期刊网

http://journal.hep.com.cn