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

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

Summary of algorithms for solving RB model instances in constraint satisfiability

Constraint satisfaction problem is one of the most basic NP-complete problems in artificial intelligence. Over the years, with the in-depth study of constraint satisfaction problem, scholars at home and abroad have proposed a variety of case models. RB model is an example of growth domain constraint satisfaction problem with precise phase transition, which is very challenging to solve. In order to find a new efficient algorithm and promote the research of RB model algorithm for constraint satisfiability problem, firstly, this paper analyzed the model development and solving techniques of constraint satisfaction problem. Secondly, it sorted out various examples of RB model solving algorithms, and divided the solving algorithm literature into backtracking heuristic, information propagation and meta-heuristic related improved algorithms. This paper compared and summarized the algorithm principles, improved strategies, convergence and accuracy. Finally, it gave the research trend and development direction of solving RB model example algorithm.