约束可满足性中求解RB模型实例的算法综述

摘要：

约束满足问题是人工智能领域中最基本的NP完全问题之一.多年来,随着约束满足问题的深入研究,国内外学者提出多种实例模型.其中,RB模型是一种能生成具有精确相变的增长域约束满足问题实例,其求解难度极具挑战性.为了寻找其求解的新型高效算法,促进约束可满足问题的RB模型求解算法领域的研究,首先从约束满足问题的模型发展、求解技术进行分析;其次,对各类求解RB模型实例算法进行梳理,将求解的算法文献划分为回溯启发式类、信息传播类和元启发式类相关改进算法,从算法原理、改进策略、收敛性和精确度等方面进行对比综述;最后给出求解RB模型实例算法的研究趋势和发展方向.

关键词：约束满足问题、RB模型、回溯启发式算法、信息传播算法、元启发式算法

所属期刊栏目：40

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金;宁夏青年拔尖人才资助项目

在线出版日期：2023-07-31（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：1929-1936,1946