检索结果-内蒙古大学图书馆

东北大学学报（自然科学版） 2022年第4期43卷 463-469页

作者：韩淑婷赖永刘杰吉林大学计算机科学与技术学院吉林长春130012 吉林大学符号计算与知识工程教育部重点实验室吉林长春130012

模型计数是求给定命题公式的模型数,是人工智能领域的一个基本问题.在贝叶斯网络、有界模型检测、精确集合覆盖等众多实际问题中,存在许多exactly-one约束.常见的处理方法是将exactly-one约束编码为CNF公式,再调用模型计数器求解.这种... 详细信息

模型计数是求给定命题公式的模型数,是人工智能领域的一个基本问题.在贝叶斯网络、有界模型检测、精确集合覆盖等众多实际问题中,存在许多exactly-one约束.常见的处理方法是将exactly-one约束编码为CNF公式,再调用模型计数器求解.这种方法扩大了命题公式的规模,容易导致求解时间过长.本文分别提出从CNF公式中还原exactly-one约束的ECR算法和处理exactly-one约束的ECP算法.ECR算法能明显提高C2D编译器的求解效率.基于最新的模型计数器ExactMC,本文改进了能识别和单独处理exactly-one约束的模型计数器ECMC.实验结果表明,ECMC的时间效率相比ExactMC有显著提高.

关键词： exactly-one约束模型计数二元约束传播合取范式 C2D

来源：评论

学校读者我要写书评

暂无评论

基于扩展规则的模型计数与智能规划方法

引用

计算机研究与发展 2009年第3期46卷 459-469页

作者：赖永欧阳丹彤蔡敦波吕帅吉林大学计算机科学与技术学院长春130012 吉林大学符号计算与知识工程教育部重点实验室长春130012

提出命题扩展规则方法ER的一种高效实现.在此基础上,研究了扩展规则方法在3个领域的应用:提出一次性求解一系列相近SAT问题的快速算法nER;提出基于扩展规则的模型计数算法#ER,同时结合#ER和#DPLL的优点提出算法#CDE;设计基于扩展规则方... 详细信息

提出命题扩展规则方法ER的一种高效实现.在此基础上,研究了扩展规则方法在3个领域的应用:提出一次性求解一系列相近SAT问题的快速算法nER;提出基于扩展规则的模型计数算法#ER,同时结合#ER和#DPLL的优点提出算法#CDE;设计基于扩展规则方法的Conformant规划系统.实验结果表明:使用nER算法一次性求解的时间远小于使用ER方法单独求解每个问题的总时间;对于互补因子较高的问题,#ER优于#DPLL;#CDE融合了#ER和#DPLL的优点.研究表明扩展规则方法对于互补因子较高的问题具有较大的优势,具有广阔的应用前景.

关键词：自动推理扩展规则命题可满足问题模型计数 Conformant规划

来源：评论

学校读者我要写书评

暂无评论

基于格局检测的并行模型计数方法

引用

吉林大学学报（工学版） 2020年第4期50卷 1443-1448页

作者：李壮刘磊张桐搏吕帅吉林大学计算机科学与技术学院长春130012

在经典的可满足性问题求解中,针对处理模型数较少的实例,SWcc迭代法和SWcc优化增量法与完备的模型计数方法相比,求解适用性更高,但SWcc迭代法和SWcc优化增量法均为串行求解方法,没有对解空间进行剪枝、化简等处理。本文基于此设计了基... 详细信息

在经典的可满足性问题求解中,针对处理模型数较少的实例,SWcc迭代法和SWcc优化增量法与完备的模型计数方法相比,求解适用性更高,但SWcc迭代法和SWcc优化增量法均为串行求解方法,没有对解空间进行剪枝、化简等处理。本文基于此设计了基于格局检测的并行模型计数算法。该算法以化简解空间和启发式为核心,将原解空间分解成为若干子空间并对原子句集进行化简后,并行处理各个子空间。实验结果表明:对于模型个数较少、公式规模较大的问题,该算法比原算法更具有适用性。

关键词：自动推理局部搜索模型计数格局检测并行框架

来源：评论

学校读者我要写书评

暂无评论

基于格局检测的模型计数方法

引用

软件学报 2020年第2期31卷 395-405页

作者：贺甫霖刘磊吕帅牛当当王强吉林大学计算机科学与技术学院吉林长春130012 符号计算与知识工程教育部重点实验室(吉林大学) 吉林长春130012 西北农林科技大学信息工程学院陕西杨凌712100

模型计数是指求出给定命题公式的模型数,是SAT问题的泛化.模型计数在人工智能领域取得了广泛应用,很多现实问题都可以规约为模型计数进行求解.目前,常用的模型计数求解器主要有Cachet与sharp SAT,它们均采用完备方法且具有高效的求解能... 详细信息

模型计数是指求出给定命题公式的模型数,是SAT问题的泛化.模型计数在人工智能领域取得了广泛应用,很多现实问题都可以规约为模型计数进行求解.目前,常用的模型计数求解器主要有Cachet与sharp SAT,它们均采用完备方法且具有高效的求解能力,但其求解效率对模型数不敏感.有理由猜测:当给定问题的模型较少时,不完备算法可能发挥其效率优势而更适合模型计数.局部搜索是求解SAT问题的高效不完备方法,Cai等人提出了格局检测策略,并将其应用到局部搜索方法中,提出了SWcc算法,具有很高的求解效率.对SWcc算法进行扩充,分别得到了迭代法与优化后的增量法两种效率较高的不完备模型计数方法,给出了两种方法的思路和具体实现.最后给出了大量测试样例的实验结果,以验证当给定合取范式的模型较少时,该迭代法与优化后的增量法的求解效率有所提升.

关键词：模型计数局部搜索格局检测

来源：评论

学校读者我要写书评

暂无评论

模型计数问题中子句简化方法研究

模型计数问题中子句简化方法研究

引用

作者：韩淑婷吉林大学

学位级别：硕士

模型计数(model counting,#SAT)问题是人工智能领域的一个基本问题,旨在求解给定命题公式的可满足赋值个数,求解难度是#P完全的。现代基于CDCL(conflict driven clause learning)框架的模型计数求解器已经能够处理具有百万条子句的大型... 详细信息

模型计数(model counting,#SAT)问题是人工智能领域的一个基本问题,旨在求解给定命题公式的可满足赋值个数,求解难度是#P完全的。现代基于CDCL(conflict driven clause learning)框架的模型计数求解器已经能够处理具有百万条子句的大型合取范式(conjunctive normal form,CNF)。然而,在诸如贝叶斯网络、规划、有界模型检测、概率推理等复杂实际应用中,仍有许多庞大的CNF公式使用目前最先进模型计数求解器也难以求解。对于大规模问题而言,简化CNF公式中的子句,是提升模型计数求解效率的有效方法。模型计数的预处理阶段能够通过使用命题公式推理规则删除冗余子句和变量,实现对命题公式中子句的简化。包含消除(subsumption elimination,SE)、重言式消除(tautology elimination,TE)、活化(vivification,VIV)、B+E算法等多种先进的预处理技术能够大大减少了命题公式的子句数。然而子句简化后的命题公式并非总能在模型计数时表现得更好,存在部分反常公式经预处理后模型计数总时间反而明显增加。本文提出衡量预处理前后命题公式模型计数求解难度的标准,通过判断预处理后命题公式是否更难求解实现对反常公式的过滤。本文提出预处理筛选算法FILTER,通过调用PMC和B+E两种成熟的预处理器,对比原公式以及两种预处理后公式的求解难度,筛选出求解难度最低的公式进行模型计数。在最新的精确模型计数求解器Exact MC上测试算法FILTER,实验结果表明本文提出的预处理筛选策略综合了PMC和B+E的好处,从整体上提高了模型计数求解效率。在许多大规模实际问题中,多值变量的出现十分常见。多值变量在命题逻辑知识库中表示为exactly-one约束,在使用模型计数解决包含多指变量的实际问题时,通常需要将exactly-one约束转换为CNF公式,这将以指数形式扩大CNF公式的子句规模,容易造成模型计数求解时间溢出的问题。为更好地解决这类问题,本文提出了从CNF公式中识别exactly-one约束的算法ECR。C2D是目前唯一能够直接处理exactly-one约束的求解器,实验结果显示算法ECR显著提升了C2D的求解效率。对于其他不能直接处理exactly-one约束的模型计数求解器,本文提出对exactly-one约束进行单独处理的算法ECP。将算法ECR和算法ECP应用于模型计数求解器Exact MC,改进得到的模型计数求解器ECMC性能优于Exact MC。综上,本文的主要研究内容是通过简化命题公式的子句,提升模型计数求解效率。在对模型计数问题中命题公式的子句进行简化时,本文采用了两种策略:一是在预处理阶段过滤反常公式的预处理筛选策略,二是在求解阶段识别和单独处理命题公式中exactly-one约束的策略。在Exact MC和C2D两种模型计数求解器上测试的实验结果表明,本文提出的两种策略都实现了命题公式的简化和模型计数求解效率的提升。

关键词：模型计数预处理 exactly-one约束 ExactMC C2D 可满足性问题

来源：评论

学校读者我要写书评

暂无评论

一种基于知识编译的模型计数方法

引用

东北师大学报（自然科学版） 2010年第4期42卷 46-50页

作者：殷明浩刘华谷文祥东北师范大学计算机科学与信息技术学院吉林长春130117

提出一种新的基于知识编译的模型计数方法——MTREE.该方法以一个否定范式(NF)作为输入,利用命题表推演过程,结合香农扩展和简化规则,将输入的否定范式编译成与之等价的R-模型树,在R-模型树上应用多项式时间算法求出其模型个数,即为原输... 详细信息

提出一种新的基于知识编译的模型计数方法——MTREE.该方法以一个否定范式(NF)作为输入,利用命题表推演过程,结合香农扩展和简化规则,将输入的否定范式编译成与之等价的R-模型树,在R-模型树上应用多项式时间算法求出其模型个数,即为原输入NF的模型个数.严格证明了该算法是完备有效的.

关键词：模型计数知识编译否定范式模型树 R-模型树香农扩展

来源：评论

学校读者我要写书评

暂无评论

可满足问题中的模型计数

引用

智能系统学报 2012年第1期7卷 33-39页

作者：谷文祥朱磊黄平殷明浩东北师范大学计算机科学与信息技术学院吉林长春130117

模型计数问题是指计算给定问题的解的个数,这是一类比决策更困难的问题,也是人工智能领域研究的一个热点问题.对模型计数问题的研究不仅可以提高算法的求解效率,更能促进对问题困难本质的了解.以可满足问题(命题可满足(SAT)和约束可满... 详细信息

模型计数问题是指计算给定问题的解的个数,这是一类比决策更困难的问题,也是人工智能领域研究的一个热点问题.对模型计数问题的研究不仅可以提高算法的求解效率,更能促进对问题困难本质的了解.以可满足问题(命题可满足(SAT)和约束可满足问题(CSP))为例,从精确算法和近似求解两方面综述了模型计数问题的研究现状,重点介绍了相关概念以及各个算法之间的优缺点,并提出了有待解决的开放性问题,对模型计数问题的研究予以了总结和展望.

关键词：人工智能约束可满足问题命题可满足问题模型计数

来源：评论

学校读者我要写书评

暂无评论

伪布尔约束的一种模型计数方法

引用

计算机科学 2024年第S2期51卷 150-154页

作者：郑苏豪牛秦洲陶小梅桂林理工大学信息科学与工程学院广西桂林541006 广西师范大学计算机科学与工程学院、软件学院广西桂林541006

伪布尔约束问题是一类与布尔约束问题相似的组合优化难题。解决这类问题的核心在于以不同的数学形式对伪布尔约束进行编码,例如线性规划、整数规划以及其他形式的组合优化。当前流行的解决方法是将问题转化为布尔公式,然后运用冲突导向... 详细信息

伪布尔约束问题是一类与布尔约束问题相似的组合优化难题。解决这类问题的核心在于以不同的数学形式对伪布尔约束进行编码,例如线性规划、整数规划以及其他形式的组合优化。当前流行的解决方法是将问题转化为布尔公式,然后运用冲突导向的子句学习(CDCL)类SAT求解器对这些布尔公式进行求解。提出了一种新的方法来解决伪布尔约束问题中的模型计数问题。首先,介绍了知识编译和扩展规则的相关概念,随后详细阐述了如何利用知识编译将伪布尔约束问题转化为二元决策图(BDD),并着重探讨了BDD结构的特性,最后采用基于扩展规则的模型计数方法来处理伪布尔约束问题中的模型计数问题。实验结果表明,该方法在处理互补因子较高的子句集时表现出更为优越的性能。

关键词：伪布尔约束 SAT问题模型计数知识编译子句

来源：评论

学校读者我要写书评

暂无评论

知识编译下的伪布尔公式模型计数研究

知识编译下的伪布尔公式模型计数研究

引用

作者：郑苏豪桂林理工大学

学位级别：硕士

伪布尔(Pseudo-Boolean,PB)约束是一种用于描述离散决策问题的数学形式,通常用于在离散领域中建模和求解各种问题。伪布尔约束具有较高的表达能力和灵活性,能够有效地描述各种问题中的逻辑关系和约束条件。与传统的命题公式相比,伪布尔... 详细信息

伪布尔(Pseudo-Boolean,PB)约束是一种用于描述离散决策问题的数学形式,通常用于在离散领域中建模和求解各种问题。伪布尔约束具有较高的表达能力和灵活性,能够有效地描述各种问题中的逻辑关系和约束条件。与传统的命题公式相比,伪布尔约束表达能力更强,形式更简洁。由于其优秀的表达能力,伪布尔约束在实际应用中常用于描述各种离散决策问题,如电路设计自动化、自动规划和调度、人工智能和模式识别等。伪布尔公式的模型计数是伪布尔约束问题的一类扩展,对于部分伪布尔约束相关问题,仅是判断公式是否可满足是不够的,还需要求解出可满足赋值的个数。概率推理、一致性概率规划等问题都与伪布尔公式的模型计数问题相关联。虽然针对伪布尔约束的编码方法和技术在近年来得到了广泛的研究和应用,不断涌现出新的方法和算法为解决大规模和复杂的伪布尔约束问题提供了更加有效和高效的求解手段。但相比于布尔可满足性计数问题(#SAT),伪布尔公式的模型计数方法却没有得到深入研究,因此本文将从模型计数相关角度对伪布尔公式进行深入研究,提出了求解两类伪布尔约束模型计数相关问题的方法。 1.针对伪布尔公式的模型计数问题,提出了一种基于知识编译技术的求解方法。首先将伪布尔公式转换为二元决策图(Ordered Binary Decision Diagrams,OBDD),这一步骤利用知识编译技术将复杂的逻辑约束转化为更容易处理的形式。OBDD能够表示伪布尔公式,并且可以得到与其等价的子句集。接着利用扩展规则对子句集进行扩展,将其转化为极大项集合。最后根据解空间的性质得到子句集的可满足解个数,进而得到伪布尔公式的模型个数。 2.针对布尔变元在概率分布下的伪布尔公式的可满足概率计算,提出了一种基于知识编译技术和加权模型计数的求解方法。在通过OBDD得到与伪布尔公式等价的子句集后,利用知识编译技术将其编译为具有平滑性和确定性的可分解否定范式(Smooth Decision Diagrams in Decomposable Negation Normal Form,sdDNNF)。根据sd-DNNF的结构性质构造相应的算术回路,算术回路能够同时表示布尔变元之间的逻辑关系和变量的概率分布,保证逻辑推理过程的完整性和准确性。最后利用加权模型计数方法对算术回路计算得到概率分布下的伪布尔公式可满足概率。通过将所提出方法与现有算法在相应的测试集上进行对比实验,验证了其可行性和有效性,为研究伪布尔约束的模型计数相关问题提供了新思路。

关键词：伪布尔约束模型计数知识编译布尔可满足问题算术回路

来源：评论

学校读者我要写书评

暂无评论

基于局部搜索的模型计数方法研究

基于局部搜索的模型计数方法研究

引用

作者：贺甫霖吉林大学

学位级别：硕士

模型计数问题是指求解出给定命题公式的模型数,是自动推理领域的重要难题。模型计数在人工智能领域取得了广泛应用,许多现实问题都可以规约为模型计数问题进行求解。目前常用的完备的模型计数求解器具有高效的求解能力,但其求解效率对... 详细信息

模型计数问题是指求解出给定命题公式的模型数,是自动推理领域的重要难题。模型计数在人工智能领域取得了广泛应用,许多现实问题都可以规约为模型计数问题进行求解。目前常用的完备的模型计数求解器具有高效的求解能力,但其求解效率对模型数不敏感。有理由猜测:当给定问题的模型较少时,不完备算法可能发挥其效率优势而更适合模型计数。本文旨在利用不完备方法的求解优势,设计出新的求解能力更强的模型计数求解方法。其中求解能力以正确求出给定合取范式模型的求解时间长短来衡量。局部搜索是求解SAT问题的高效的不完备方法,Cai等人提出了格局检测策略,并将其应用到局部搜索方法中提出了SWcc算法。格局检测策略定义了邻居变量,很好地解决了变量翻转过程中容易遇到的局部最优问题,具有很高的求解效率。本文对SWcc算法进行扩充分别得到了迭代法与增量法两种效率较高的不完备模型计数方法,给出了两种方法的思路和具体实现。SWcc算法每完成一次局部搜索的迭代计算过程,便可以得到一个可满足的全值指派。迭代法采用添加子句的方法,将刚刚得到的可满足指派的否定形式添加到原合取范式,解决了解的重复性问题,使得算法在每次迭代过程中都可以得到一个不同的可满足指派,并记录下可满足指派数目。增量法同样采用添加子句的方法,与迭代法不同的是,增量法在每次迭代结束后会计算相关变量的邻居信息,下一次翻转操作仍在当前指派上进行,从而减少了许多变量的初始化计算过程。为了进一步提升不完备算法的求解能力,本文提出了两种启发式策略,并将他们分别应用于迭代法与增量法。在迭代法的基础上添加了加速求解策略,给出了该策略的详细描述,理论上该算法适用于求解模型数目较多的合取范式,并且当求解可满足指派中有部分文字正负形式相同的合取范式时,求解效率会进一步提升。在增量法的基础上添加了解的优化策略,尽可能减少添加子句的变量数目,从而发挥了格局检测的优越性。最后,给出了大量测试样例的实验结果,实验结果表明,当给定合取范式的模型较少时,本文提出的迭代法与增量法的求解效率有所提升。本文提出的两种启发式策略在求解部分特定实例时,也会得到较好的求解效果。

关键词：模型计数局部搜索格局检测启发式策略自动推理

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：