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

计算机研究与发展 2025年第5期62卷 1226-1234页

作者：蒋璐宇欧阳丹彤张奇太然张立明吉林大学计算机科学与技术学院长春130012 符号计算与知识工程教育部重点实验室(吉林大学) 长春130012

极小不可满足子集(minimal unsatisfiable subset,MUS)的求解是理论计算机科学的重要问题.由于MUS的个数随问题规模呈指数级增长,现有算法致力于在合适的时间限制内求解出尽可能多的MUS.在庞大的搜索空间中,选择合适的节点来扩展可以大... 详细信息

极小不可满足子集(minimal unsatisfiable subset,MUS)的求解是理论计算机科学的重要问题.由于MUS的个数随问题规模呈指数级增长,现有算法致力于在合适的时间限制内求解出尽可能多的MUS.在庞大的搜索空间中,选择合适的节点来扩展可以大幅减小收缩和扩充操作的时间开销,从而提高算法的求解效率.提出一种基于增量信息交互的MUS求解算法MARCO-MSS4MUS,利用MUS、极小修正集(minimal correction set,MCS)和极大可满足子集(maximal satisfiable subset,MSS)之间的对偶和互补关系,在采用MARCO算法框架增量求解MSS和MUS的过程中,根据已求解的MSS的交集和并集信息辅助选择节点来扩展,即通过增量的MSS信息启发用于扩展节点选择以加速MUS枚举,这一过程同时利于算法找到更多的MSS,在枚举过程中新识别出的MSS又能辅助下一轮扩展节点的选择,从而实现了增量信息的有效交互.针对交互的增量信息提出2个定理及2个推论,从理论角度分析了MARCO-MSS4MUS算法的可行性,并通过MUS标准测试用例上的实验验证了所提算法相较于当前先进算法的优越性,在部分测试用例上的结果显示所提算法的枚举效率和枚举获胜个数较已有算法均有显著的提高.

关键词：极小不可满足子集极大可满足子集不可行分析碰集对偶性

来源：评论

学校读者我要写书评

暂无评论

融合基数约束与单次入队的基于模型诊断方法

引用

计算机研究与发展 2025年第2期62卷 408-417页

作者：青杨欧阳丹彤周慧思张立明吉林大学计算机科学与技术学院长春130012 符号计算与知识工程教育部重点实验室(吉林大学) 长春130012

基于模型诊断(MBD)方法在不同的环境中有越来越多的用途,包括软件故障定位、电子表格的调试、Web服务和硬件设计,以及生物系统的分析等.受这些不同用途的启发,近年来MBD算法改进成效显著.然而,对体系庞大、结构复杂的系统,需要对现有方... 详细信息

基于模型诊断(MBD)方法在不同的环境中有越来越多的用途,包括软件故障定位、电子表格的调试、Web服务和硬件设计,以及生物系统的分析等.受这些不同用途的启发,近年来MBD算法改进成效显著.然而,对体系庞大、结构复杂的系统,需要对现有方法进一步改进.由于求解诊断解在计算上具有挑战性,因此相继提出了一些通过压缩模型的MBD算法来提高诊断效率,如基于统治的多观测压缩模型(dominated-based compacted model with multiple observations,D-CMMO)算法.对于给定多个观测值且注入1个以上错误需要大量时间的诊断问题,提出了一个新的诊断模型CCM(cardinality-constrained compacted model)来解决.基于基数约束的压缩模型算法使用2种方法对求解过程进行优化:首先,利用系统观测的故障输出和故障组件数量之间的约束关系来限制目标解的范围;其次,通过对假设集采用单次入队方法,进而有效提升MaxSAT(maximum satisfiability)求解器的性能.此外,在ISCAS85和ITC99基准测试用例上的实验结果表明,与目前最新的MBD求解方法D-CMMO相比,上述2种优化方法有效缩小了MBD问题的求解范围,降低MaxSAT求解器搜索目标解的难度,进而能在更短的时间内返回一个诊断解.在平均状况下,CCM方法相比D-CMMO方法求解效率分别提升64.5%和92.8%.

关键词：基于模型诊断压缩模型基于基数约束的算法顶层诊断解单次入队

来源：评论

学校读者我要写书评

暂无评论

针对MUS求解问题的加强剪枝策略

引用

软件学报 2024年第4期35卷 1964-1979页

作者：蒋璐宇欧阳丹彤董博文张立明吉林大学计算机科学与技术学院吉林长春130012 吉林大学软件学院吉林长春130012 符号计算与知识工程教育部重点实验室(吉林大学) 吉林长春130012

极小不可满足子集(minimal unsatisfiable subsets,MUS)的求解是布尔可满足性问题中的一个重要子问题.对于一个给定的不可满足问题,其MUS的求解能够反映出问题中导致其不可满足的关键原因.然而,MUS的求解是一项极其耗时的任务,不同的剪... 详细信息

极小不可满足子集(minimal unsatisfiable subsets,MUS)的求解是布尔可满足性问题中的一个重要子问题.对于一个给定的不可满足问题,其MUS的求解能够反映出问题中导致其不可满足的关键原因.然而,MUS的求解是一项极其耗时的任务,不同的剪枝过程将直接影响到搜索空间的大小、算法的迭代次数,从而影响算法的求解效率.提出一种针对MUS求解的加强剪枝策略ABC(accelerating by critical MSS),依据MSS、MCS、MUS这3者之间的对偶性和碰集关系特点,提出cMSS和subMUS概念,并总结出4条性质,即每个MUS必是subMUS的超集,进而在避免对MCS的碰集进行求解的情况下有效利用MUS和MCS互为碰集的特征,有效避免求解碰集时的时间开销.当subMUS不可满足时,则subMUS是唯一的MUS,算法将提前结束执行;当subMUS可满足时,则剪枝掉此节点,进而有效避免对求解空间中的冗余空间进行搜索.同时,通过理论证明ABC策略的有效性,并将其应用于目前最高效的单一化模型算法MARCO和双模型算法MARCO-MAM,在标准测试用例下的实验结果表明,该策略可以有效地对搜索空间进行进一步剪枝,从而提高MUS的枚举效率.

关键词：极小不可满足子集极大可满足子集 MUS枚举幂集探索不可行分析

来源：评论

学校读者我要写书评

暂无评论

基于学习-推理的约束求解方法研究进展

引用

软件学报 2024年第1期35卷 220-235页

作者：邹悦赖家洋张永刚吉林大学软件学院吉林长春130012 吉林大学计算机科学与技术学院吉林长春130012 符号计算与知识工程教育部重点实验室(吉林大学) 吉林长春130012

机器学习与自动推理的融合是当前人工智能研究的新趋势.约束满足问题是人工智能研究的经典问题,现实世界中大量的调度、规划和配置等问题均可以建模为约束满足问题,高效的求解算法一直是研究热点.近年来涌现出众多将机器学习应用于约束... 详细信息

机器学习与自动推理的融合是当前人工智能研究的新趋势.约束满足问题是人工智能研究的经典问题,现实世界中大量的调度、规划和配置等问题均可以建模为约束满足问题,高效的求解算法一直是研究热点.近年来涌现出众多将机器学习应用于约束满足问题求解的新方法,这些基于“学习-推理”的新方法为约束满足问题求解开辟了新方向并展示出巨大发展潜力,方法的突出优点是适应性强、可在线优化并具有更强的可扩展性.将当前的“学习-推理”方法分为基于消息传递神经网络、基于序列到序列和基于最优化等3类进行综述,详细分析各类方法的特点和在不同的问题集上求解效果,尤其对每类方法所涵盖的相关工作进行多角度的对比分析.最后,对基于“学习-推理”的约束求解方法进行总结和展望.

关键词：约束满足问题消息传递神经网络序列到序列强化学习最优化

来源：评论

学校读者我要写书评

暂无评论

强表达描述逻辑本体的后继式公理定位研究

引用

软件学报 2023年第8期34卷 3574-3586页

作者：李静欧阳丹彤叶育鑫吉林大学计算机科学与技术学院吉林长春130012 符号计算与知识工程教育部重点实验室(吉林大学) 吉林长春130012

公理定位能够挖掘描述逻辑中可解释的缺陷,并为逻辑蕴含结果寻找隐藏的理由,因此在描述逻辑研究中引起了广泛的关注.平衡描述逻辑表达能力和推理机求解效率问题一直是公理定位研究的重点内容.基于一种后继式判定算法,从白盒和黑盒两个... 详细信息

公理定位能够挖掘描述逻辑中可解释的缺陷,并为逻辑蕴含结果寻找隐藏的理由,因此在描述逻辑研究中引起了广泛的关注.平衡描述逻辑表达能力和推理机求解效率问题一直是公理定位研究的重点内容.基于一种后继式判定算法,从白盒和黑盒两个角度将其用于公理定位.白盒方法利用修正的后继式规则(即定位规则)来追踪推理的具体过程,并引入定位公式的概念建立子句的布尔公式标签与逻辑蕴含的所有极小公理集之间的对应关系.黑盒方法则直接调用基于未修正的后继式规则的推理机,并进一步利用碰集树方法求得逻辑蕴含的所有理由.最后,基于这样的两种面向强表达描述逻辑本体的公理定位算法设计推理工具,从理论和实验两方面验证其可行性,并与已有的推理工具比较求解性能.

关键词：公理定位后继式判定算法定位规则白盒与黑盒

来源：评论

学校读者我要写书评

暂无评论

基于贡献度和数据有效性检验的共识机制

引用

东北大学学报（自然科学版） 2024年第2期45卷 160-169,178页

作者：时小虎姚鑫孙延风马德印吉林大学计算机科学与技术学院吉林长春130012 吉林大学符号计算与知识工程教育部重点实验室吉林长春130012 吉林大学商学院吉林长春130012 长春工业大学计算机科学与工程学院吉林长春130012

将区块链技术引入到分布式数据维护系统,旨在解决基于传统中心化数据库的分布式系统存在的数据维护不透明、数据易被篡改、历史记录不可追溯等问题,提出一种基于贡献度和数据有效性检验的共识机制.该算法提出一种贡献度优先的随机可验... 详细信息

将区块链技术引入到分布式数据维护系统,旨在解决基于传统中心化数据库的分布式系统存在的数据维护不透明、数据易被篡改、历史记录不可追溯等问题,提出一种基于贡献度和数据有效性检验的共识机制.该算法提出一种贡献度优先的随机可验证领导者选举机制,保证记账权分配的随机性及可验证性.进一步引入密度峰值算法对交易数据有效性进行校验,对打包区块的正确性达成共识.最后将所提出的共识机制应用于梅花鹿分布式养殖场场景,结果验证了密度峰值算法在交易数据有效性检测任务中的准确性和高效性.出块时延分析和安全性分析表明,所提出的共识机制能够满足数据有效性验证的实时性需求,能耗较小,具有很强的灾备能力.

关键词：区块链共识机制离群点检测分布式数据维护溯源

来源：评论

学校读者我要写书评

暂无评论

一种高效的FDE并行传播算法

引用

软件学报 2023年第9期34卷 4153-4166页

作者：李哲于哲舟李占山吉林大学计算机科学与技术学院吉林长春130012 符号计算与知识工程教育部重点实验室(吉林大学) 吉林长春130012

约束规划(constraint programming, CP)是表示和求解组合问题的经典范式之一.扩展约束(extensional constraint)或称表约束(table constraint)是约束规划中最为常见的约束类型.绝大多数约束规划问题都可以用表约束表达.在问题求解时,相... 详细信息

约束规划(constraint programming, CP)是表示和求解组合问题的经典范式之一.扩展约束(extensional constraint)或称表约束(table constraint)是约束规划中最为常见的约束类型.绝大多数约束规划问题都可以用表约束表达.在问题求解时,相容性算法用于缩减搜索空间.目前,最为高效的表约束相容性算法是简单表约缩减(simple table reduction, STR)算法簇,如Compact-Table (CT)和STRbit算法.它们在搜索过程中维持广义弧相容(generalized arc consistency, GAC).此外,完全成对相容性(full pairwise consistency, fPWC)是一种比GAC剪枝能力更强的相容性.最为高效的维持fPWC算法是PW-CT算法.多年来,人们提出了多种表约束相容性算法来提高剪枝能力和执行效率.因子分解编码(factor-decomposition encoding, FDE)通过对平凡问题重新编码.它一定程度地扩大了问题模型,使在新的问题上维持相对较弱的GAC等价于在原问题上维持fPWC.目前, FDE的合适STR算法是STRFDE和STR2,而不是CT.这是由于CT算法可能产生内存溢出问题.在维持相容性算法的过程中,需要将迭代地调用各个约束执行其相容性算法过滤搜索空间,这个过程称为约束传播.动态提交方案是一个并行约束传播框架,可以并行地调度约束执行传播算法.它在大规模问题中,改进效果尤为明显.改进STRFDE和动态提交传播算法.针对FDE提出了PSTRFDE算法. PSTRFDE可以嵌入到动态提交方案中,进一步提高了约束规划问题的求解效率.大量的实验表明, PSTRFDE与CT和STRbit相比,可以减少内存占用;与STRFDE和STR2相比,可以提高算法的效率.所作工作充分说明了PSTRFDE是FDE上最为高效的过滤算法.

关键词：约束规划并行约束传播相容性算法简单表缩减算法

来源：评论

学校读者我要写书评

暂无评论

基于本体指导的矿产预测知识图谱构建研究

引用

地学前缘 2024年第4期31卷 16-25页

作者：叶育鑫刘家文曾婉馨叶水盛吉林大学计算机科学与技术学院吉林长春130012 吉林大学符号计算与知识工程教育部重点实验室吉林长春130012 吉林大学综合信息矿产预测研究所吉林长春130026

在基于数据驱动范式的科学研究中,构建知识图谱已被证明是获取和表征知识的有效手段之一。然而,目前已构建的矿产资源预测领域知识图谱仍然存在诸多挑战和局限性,有待进一步解决和完善。首先,针对矿产预测的本体构建问题研究相对较少,... 详细信息

在基于数据驱动范式的科学研究中,构建知识图谱已被证明是获取和表征知识的有效手段之一。然而,目前已构建的矿产资源预测领域知识图谱仍然存在诸多挑战和局限性,有待进一步解决和完善。首先,针对矿产预测的本体构建问题研究相对较少,尤其是该领域现有知识图谱的本体层普遍缺乏时空语义,限制了对于矿产资源时空特征的有效表示与分析。其次,现有图谱构建方法主要为面向数据层面的文本抽取,而缺乏对于复杂逻辑关系的本体层建设,以及本体层与数据层之间的有效关联。以上问题会导致构建的地学知识图谱缺乏深层次的语义信息,难以满足矿产资源预测对表达复杂地学概念和关系的需求。针对上述问题,本研究以综合信息矿产预测理论为指导,旨在构建可应用于矿产预测任务的复杂语义知识图谱。具体而言,首先通过对矿产预测的理论和方法进行解析构建初始化领域本体,然后选择成熟的地质时间本体和地理空间本体对初始本体进行本体融合和扩展,通过嵌入时空语义有效表达地矿产资源的时空特征。此外,重点关注了本体层与数据层之间的关联建设,通过建立丰富的语义关系,实现知识图谱中各个节点之间的有效连接与信息共享。实验结果表明,采用本文所提出的方法构建的图谱在知识丰度和置信度等指标上均优于其他现有方法。这一研究为矿产预测领域提供了更为深入和全面的数据资源建设的方法支撑,有助于推动该领域的进一步发展和应用。

关键词：矿产资源知识图谱本体工程综合信息矿产预测理论

来源：评论

学校读者我要写书评

暂无评论

基于深度学习的两阶段实时显式拓扑优化方法

引用

吉林大学学报（工学版） 2023年第10期53卷 2942-2951页

作者：孙舒杨程玮斌张浩桢邓向萍齐红吉林大学计算机科学与技术学院长春130012 吉林大学符号计算与知识工程教育部重点实验室长春130012

针对以固体各向同性材料法(SIMP)、水平集法(Level-set)等为代表的传统连续体拓扑优化算法存在的计算代价昂贵、生成结构几何隐式等缺陷,结合深度学习与可移动变形组件法(MMC),提出一种基于深度学习的两阶段实时显式拓扑优化方法。在第... 详细信息

针对以固体各向同性材料法(SIMP)、水平集法(Level-set)等为代表的传统连续体拓扑优化算法存在的计算代价昂贵、生成结构几何隐式等缺陷,结合深度学习与可移动变形组件法(MMC),提出一种基于深度学习的两阶段实时显式拓扑优化方法。在第一阶段使用深度学习模型预测取代有限元分析的多数费时迭代计算,第二阶段对深度学习模型预测所得结构进行少量迭代微调,形成最终的带有显式几何特征的优化结构。在相对一般的数据集下定量与定性地验证了本文方法的可行性与有效性,并研究了第一阶段深度学习模型的训练程度与最终生成结构质量及总体耗费时间的关系。结果表明:与传统连续体拓扑优化算法相比,本文方法能在保证拓扑优化结构生成质量的同时节约90%以上的计算时间。

关键词：计算机应用拓扑优化深度学习可移动变形组件法计算机辅助设计

来源：评论

学校读者我要写书评

暂无评论

基于分割方法的繁体中文报纸文本检测

引用

吉林大学学报（工学版） 2023年第4期53卷 1146-1154页

作者：姜宇潘家铮陈何淮符凌智齐红吉林大学计算机科学与技术学院长春130012 吉林大学符号计算与知识工程教育部重点实验室长春130012

现阶段文本检测的研究主要面向自然场景数据集进行,针对繁体中文图像内嵌文本场景难以有效检测的问题,本文提出了一个基于分割方法的繁体中文报纸图像文本检测模型。该模型使用Resnet50和FPN作为特征提取网络,采用分割实例缩放加扩展算... 详细信息

现阶段文本检测的研究主要面向自然场景数据集进行,针对繁体中文图像内嵌文本场景难以有效检测的问题,本文提出了一个基于分割方法的繁体中文报纸图像文本检测模型。该模型使用Resnet50和FPN作为特征提取网络,采用分割实例缩放加扩展算法的方法生成用于预测文本框的二值图,并提出了周围填补、循环检测加区域覆盖的方法增强检测效果。该模型针对自建繁体中文报纸数据集的实验结果的三项指标均在0.9左右,且相比于目前文本检测效果较好的DBNet的实验结果均提升了5%~7%,针对繁体中文报纸图像文本检测任务具有一定的优越性。

关键词：计算机应用特定场景繁体中文报纸图像内嵌文本文本检测

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：