基于区间运算和组测试求解CSP以及在测试用例自动生成上的应用

摘要

CSP(Constraint Satisfaction Problem)求解部分是目前很多系统的核心部分,对其进行研究有重要作用,本文提出的算法能够解决约束为实数域上由初等函数复合而成的CSP问题。CSP的核心问题就是如何快速求出一组数据使其满足特定几个约束.目前实数域上的CSP问题的求解算法,基本上都是基于迭代或启发式的.这类算法的缺点是不能保证算法一定能够返回一组解.本文提出一种使用区间运算和组测试的方法,此算法首先使用区间运算测试在整个搜索空间内是否有解,如果不能得出确定的结论,那么将搜索空间分裂成几个子空间,并且使用相同方法对每一个子空间进行处理.并且本文提出,当某一约束表达式中所有变量出现的次数为0或1次时,程序在最坏的情况下时空复杂度为lg(V/en)=lg(V)-nlg(e)+ε ε=0,1 V为搜索空间的测度,n为变量个数,e为变量要求的精度.另外,本文提出了约束—变量关联图,并在其基础上对算法做出改进工作,同时还讨论了基于符号计算的改进.最后,本文讨论了CSP求解在测试用例自动生成上的应用。