[1]王晓峰,庞立超,莫淳惠,等.可满足性问题的结构特征进展综述[J].郑州大学学报(工学版),2023,44(06):40-47.[doi:10.13705/j.issn.1671-6833.2023.03.013]
　WANG Xiaofeng,PANG Lichao,MO Chunhui,et al.A Review of Structural Characteristics of Satisfiability Problems[J].Journal of Zhengzhou University (Engineering Science),2023,44(06):40-47.[doi:10.13705/j.issn.1671-6833.2023.03.013]
点击复制

可满足性问题的结构特征进展综述()
分享到：

《郑州大学学报(工学版)》[ISSN:1671-6833/CN:41-1339/T]

卷:
44卷
期数:
2023年06期
页码:
40-47
栏目:
出版日期:
2023-09-25

文章信息/Info

Title:
A Review of Structural Characteristics of Satisfiability Problems
作者:
王晓峰;  庞立超;  莫淳惠;  杨 易;  赵星宇;  杨 澜
1. 北方民族大学 计算机科学与工程学院,宁夏 银川 750021;2. 北方民族大学 图像图形智能处理国家民委重点实 验室 宁夏,银川 750021
Author(s):
WANG Xiaofeng;  PANG Lichao;  MO Chunhui;  YANG Yi;  ZHAO Xingyu;  YANG Lan
1. School of Computer Science and Engineering, North Minzu University, YinChuan 750021,China; 2. Key Laboratory of Image and Graphics Intelligent Processing of State Ethnic Affairs Commission, North Minzu University, YinChuan 750021,China
关键词:
SAT 问题;  相变;  树分解;  结构熵;  DNA 折纸术
Keywords:
satisfiability problems;  phase transition;  tree decomposition;  structural entropy;  DNA origami
DOI:
10.13705/j.issn.1671-6833.2023.03.013
文献标志码:
A
摘要:
可满足性( SAT)问题是人工智能的基础问题,也是 NP 难问题,在机器学习、模式识别和自然语言处理等领 域有着实际应用。 然而,随着人工智能发展,越来越多的问题呈现出更为复杂的形态,原有的算法不再适用,需进 一步优化或者改进,这对基础研究提出了更高要求。 为了研究 SAT 问题难解的内在本质,需要研究其结构特征,进 而找出求解 SAT 问题的高效算法。 近年来备受研究人员关注的相变、树宽、结构熵、DNA 折纸术是 SAT 问题结构 特征的 4 种常用度量模型。 为了理清关于 SAT 问题结构特征的研究进展,基于上述 4 种度量模型,对 SAT 问题的 结构特征进行了综述,指出了 SAT 问题结构特征研究所面临的挑战及未来的方向。 在 SAT 问题求解中相变分析、 树分解算法、结构熵及 DNA 折纸术等方面虽已取得一定的研究成果,但在相变点精确上界的求解、结构度量模型 指导 SAT 求解器设计,以及树分解算法效率的提高等方面仍待突破,这将成为未来关于 SAT 问题结构特征研究的 重点。
Abstract:
Satisfiability ( SAT) problem is the basic problem of artificial intelligence, which is also a hard problem of NP. It has practical applications in machine learning, pattern recognition and natural language processing. However, with the development of artificial intelligence, more and more complex problems popped up. The original algorithms were no longer applicable and need to be further optimized or improved, which put forward higher requirements for basic research. In order to study the inherent nature of the difficult SAT problem, the structural characteristics of the problem were studied, and then the efficient algorithm to solve the SAT problem were found out. Phase transition, tree width, structural entropy, and DNA origami were four metric models for studying the structural characteristics of SAT problems, which attracted the attention of researchers in recent years. In order to clarify the research progress on the structural characteristics of SAT problems, based on the above four measurement models, the structural characteristics of SAT problems were summarized, and the challenges and future directions of the research on structural characteristics of SAT problems were pointed out. Although some research achievements were made in phase change analysis, tree decomposition algorithm, structural entropy and DNA origami in solving SAT problems, breakthroughs are still needed in solving the accurate upper bound of phase change points, guiding the design of SAT solvers by structural metric model, and improving the efficiency of tree decomposition algorithm, which will become the focus of future research on structural characteristics of SAT problems.

相似文献/References:

[1]郭茶秀,刘树兰..铝泡沫和石墨泡沫强化石蜡相变传热的数值模拟[J].郑州大学学报(工学版),2012,33(03):87.[doi:10.3969/j.issn.1671-6833.2012.03.022]
[2]卢红霞,毛爱霞,郝好山,等.利用纳米铝和沉淀法制备纳米α-Al2O3粉体[J].郑州大学学报(工学版),2005,26(01):83.[doi:10.3969/j.issn.1671-6833.2005.01.021]
　Lu Hongxia,Mao Aixia,Hao Haoshan,et al.Nano α-Al2O3 powder was prepared by nano-aluminum and precipitation[J].Journal of Zhengzhou University (Engineering Science),2005,26(06):83.[doi:10.3969/j.issn.1671-6833.2005.01.021]

更新日期/Last Update: 2023-10-22