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

• 作 者: 孙吉贵 朱兴军 张永刚 高健
• 机 构: 吉林大学计算机科学与技术学院,吉林大学符号计算与知识工程教育部重点实验室
• 出 处: 小型微型计算机系统
• 发表日期: 2008年4期
• 关键词: 最先失败原则 弧相容 约束满足问题 约束传播 fail first principle arc consistency constraint satisfac

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