检索结果-南通市图书馆

A residual-based message passing algorithm for constraint satisfaction problems

Communications in Theoretical Physics 2022年第3期74卷 77-86页

作者： Chun-Yan Zhao Yan-Rong Fu Jin-Hua Zhao College of Science University of Shanghai for Science and TechnologyShanghai 200093China Guangdong Provincial Key Laboratory of Nuclear Science Institute of Quantum MatterSouth China Normal UniversityGuangzhou 510006China Guangdong-Hong Kong Joint Laboratory of Quantum Matter Southern Nuclear Science Computing CenterSouth China Normal UniversityGuangzhou 510006China

Message passing algorithms,whose iterative nature captures complicated interactions among interconnected variables in complex systems and extracts information from the fixed point of iterated messages,provide a powerful toolkit in tackling hard computational tasks in optimization,inference,and learning *** the context of constraint satisfaction problems(CSPs),when a control parameter(such as constraint density)is tuned,multiple threshold phenomena emerge,signaling fundamental structural transitions in their solution *** solutions around these transition points is exceedingly challenging for algorithm design,where message passing algorithms suffer from a large message fiuctuation far from *** we introduce a residual-based updating step into message passing algorithms,in which messages with large variation between consecutive steps are given high priority in the updating *** the specific example of model rb(revised B),a typical prototype of random CSPs with growing domains,we show that our algorithm improves the convergence of message updating and increases the success probability in finding solutions around the satisfiability threshold with a low computational *** approach to message passing algorithms should be of value for exploring their power in developing algorithms to find ground-state solutions and understand the detailed structure of solution space of hard optimization problems.

关键词： constraint satisfaction problems model rb message passing algorithms residuals of messages

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

一类SAT Benchmark的算法研究及其应用

一类SAT Benchmark的算法研究及其应用

引用

作者：王迪海电子科技大学

学位级别：硕士

SAT问题是计算机科学和人工智能研究的领域的著名问题。在实际生活中有许多问题可以转化为SAT问题,并通过SAT算法得到很好的解决。故而研究高效的SAT算法是当前重要且具有实际应用价值的研究主题。SAT问题来源非常广泛,由此构成了不同... 详细信息

SAT问题是计算机科学和人工智能研究的领域的著名问题。在实际生活中有许多问题可以转化为SAT问题,并通过SAT算法得到很好的解决。故而研究高效的SAT算法是当前重要且具有实际应用价值的研究主题。SAT问题来源非常广泛,由此构成了不同类型的SAT Benchmark。然而同一种SAT算法在不同类型的Benchmark上其效率存在较大的差异,人们普遍认为出现这种现象主要由于内部结构上的差异造成。基于这一考虑,SATzilla将众多的SAT算法整合起来,在求解过程中为不同的类型的Benchmark选择不同的算法,并且取得了成功。从中也可以看出为不同类型的Benchmark设计不同的算法将是解决SAT问题的一个重要的发展趋势之一。本文主要针对结构类似于model rb模型生成的一类SAT Benchmark设计了一种高效的算法,并将该算法成功地用于解决图着色问题。SAT算法主要分为完备算法和不完备算法两大类。完备算法与不完备性算法不同,它不仅可以保证为可满足SAT问题的给出它的一个模型,同时可以证明不可满足SAT问题的不可满足性,故而大多数SAT算法都是完备性算法。在当前的完备性算法中,大多数都是基于DPLL算法框架设计高效的SAT算法,如zChaff、Rsat等。本文也是基于DPLL框架来设计算法。本文在设计算法时,首先对该类SAT Benchmark的结构进行了分析,将变量进行分组处理,在此基础上将其等价性地转化为分别从各变量分组中选取满足条件的变量的问题,并以DPLL运算框架设计出wrbsat算法。算法使用了向量数组来存储数据,实现算法对数据的高效访问与操作。在设计分支决策时,将决策过程分为两步:首先,分组的选取,并以此实现搜索树的构建;其次,变量的选取,在该步骤中实现搜索路径的选取。该方式使得算法能够更好地选取决策变量,控制搜索树的大小,从而提高算法的效率。算法的运算框架使得在算法中的回溯层次相对较少,历史数据的存储也非常方便,从而使得整个冲突分析和回溯的效率都相对较高。本文对算法进行了测试,实验的结果表明在该类Benchmark上本文所设计的wrbsat算法具有更高效率,同时在本文中对测试的结果进行了分析。此外,本文将图着色问题转化为SAT问题,将该算法成功地用于求解图着色问题。

关键词： SAT model rb DPLL 分支决策 k-着色

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

欢迎您,

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

请选择保存的检索档案：

请选择收藏分类：

通借通还

欢迎您,

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：