最先失败原则的约束传播算法

Fail First Principle for Constraint Propagation

约束满足问题是人工智能研究领域的重要问题.而弧相容算法是求解约束满足问题的重要工具.在弧相容算法中应用启发式规则已经证明是一种很有效的方式.本文提出一个基于最先失败原则的约束传播算法,该算法在搜索过程中更早地发现含有空域的变量并提前进行回溯,从而提高问题求解效率.同时,在"明月1.0"架构下实现了该算法,实验结果表明使用最先失败原则的弧相容算法要比原来的算法效率上提高了约40%.

constraint satisfaction problems play a very important role in the area of artificial intelligence, while arc consistency is the key technique in solving such problems, and using heuristic rules can improve the algorithm＇s efficiency. In this paper a new constraint propagation algorithm based on fail first principle is proposed, which improves the practical time efficiency through backtracking in advance due to the earlier found of variables which contain null values, when implemented under the platform of ＂Mingyue1. 0＂, the experiments showed the practical time efficiency is increased by 40 percent through using fail first principles compared with the original one.