一个基于最小冲突修补的动态约束满足求解算法

约束满足问题是人工智能中一个重要的研究方向,近年来,对动态变化的约束满足问题的研究逐渐成为该领域的热点.在目前该领域最流行的LC算法基础上,引入禁忌搜索策略,提出了一个基于最小冲突修补的算法Tabu_LC.算法在每次冲突调整时将所有冲突变量看成一个整体,并采用分支定界搜索策略求解冲突变量组成的子问题,极大地提高了求解效率.同时,在约束求解系统"明月1.0"架构下给出了算法的具体实现,并针对大量随机问题进行了对比实验.结果表明,Tabu_LC算法在求解效率和解的质量上都明显优于LC算法.

A Mini-Conflict Repair Based Algorithm for Solving Dynamic Constraint Satisfaction Problems

Constraint satisfaction problems (CSPs) is an important research branch in artificial intelligence. Recently, dynamic CSP is proposed as a powerful tool for solving many real-world problems on dynamic environments. As a result, several algorithms to solve dynamic CSPs are presented. Among those algorithms, local change (LC) algorithm based on solution reuse strategy is a method for solving many kinds of dynamic CSPs and efficient for flexible planning. On the basis of LC algorithm which is widely used, the tabu search strategy is integrated and a mini-conflict repair based algorithm is proposed, which is called Tabu_ LC. The improved algorithm considers all the conflict variables as a whole, and then solves the sub-problems with branch and bound algorithm to find the best neighbor assignment, which improves the efficiency markedly. Furthermore, the Tabu_ LC algorithm is implemented in the framework of constraint solving system "Ming-yue 1.0", and compared with the LC algorithm using large amount of random CSPs. The experiment indicates that the improved algorithm has overwhelmed the LC algorithm on both the efficiency and quality of solutions.