加权约束满足问题的改进深度优先搜索算法

摘要

回顾了加权约束满足问题的基本概念,给出了求解的标准深度优先搜索算法,并探讨了利用变量间的约束关系,改进标准深度优先搜索算法的搜索上下界;在此基础上,给出了一种改进的深度优先分枝定界算法.该算法的一个特点是通过循环迭代求解子问题来改进上下界.针对随机约束满足问题模型生成的测试数据的数值计算结果显示,改进算法可以大大缩短求解时间.