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

Improved depth-first search algorithm for valued constraint satisfaction problem

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

Depth first search is a basic schema for valued constraint satisfaction problem (VCSP), which is an extended framework of CSP. In this paper, we introduce the basic concepts of VCSP, and give a standard depth first branch and bound (DFBB) algorithm for solving VCSP. By analysis of constraints structures, a method for improving the lower and upper bounds of DFBB is given. Based on the works above, an improved DFBB algorithm is also presented. Experimental results on random generated problems show that the improved DFBB algorithm is beneficial, especially when the problem size is large, for providing substantial saving in the computational time.