计算机应用研究

作者：杨易,王晓峰,莫淳惠,庞立超,杨澜,赵星宇,

单位：北方民族大学a.计算机科学与工程学院;b.图形图像智能处理国家民委重点实验室,银川750021；

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

基金：国家自然科学基金资助项目(62062001)；宁夏青年拔尖人才资助项目(2021)；；

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

来源：2023年第7期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2023年第7期