基于RDS技术的加权约束满足问题的符号算法研究

发布时间：2018-01-11 12:40

本文关键词：基于RDS技术的加权约束满足问题的符号算法研究　出处：《桂林电子科技大学》2015年硕士论文　论文类型：学位论文

【摘要】：计算机科学和人工智能领域中的许多问题都可以形式化为加权约束满足问题(WCSP),如地图着色、生产调度、产品配置、路由选择、物流规划、资源分配等问题。WCSP的求解目标是寻找一个使得违反约束总代价值最小的完全赋值。WCSP最基本的求解方法是深度优先分支定界(DFBB)算法,Russian Doll Search(RDS)算法是通过修改DFBB算法框架得到的,其能有效提高搜索中的上下界,但RDS算法的求解效率取决于分解后得到的各个子问题的求解效率。结构化记录是避免重复搜索的有效技术之一,通过存储已求解信息,在搜索过程中判断是否可以重用已存储的求解信息,从而提高求解效率。由于在RDS算法求解中,一次只能处理一个约束值对,不能同时处理多个约束值对,而代数决策图(ADD)能高效的表示和以集合方式处理数据,且能减缓因问题规模过大造成的组合状态爆炸问题。因此本文对加权约束满足问题的RDS符号求解算法做了相关研究,主要工作包括:(1)给出改进RDS符号ADD求解算法。基于RDS算法思想,将DFBB算法中的一次搜索用m个子问题的相继搜索来替代。通过改进最多约束变量(MCV)的变量选择法,引入RDS变量来引导原问题的子问题分解,进而减少RDS算法中分解的子问题个数。为提高各个子问题的求解效率,用桶消元算法求解非RDS变量,减少DFBB算法处理的变量个数。为了进一步提高算法的效率,借助WCSP的符号ADD表示,给出WCSP的改进RDS符号ADD求解算法。(2)给出混合RDS符号ADD求解算法。通过研究RDS变量之间的约束关系,给出RDSV-T子问题分解方法;在子问题求解中,基于子问题之间的结构关系,存储当前子问题的结构化记录,便于在后续子问题求解中重用此结构化记录。借助WCSP的符号ADD表示,给出WCSP的混合RDS符号求解算法。(3)以随机生成的WCSP问题作为测试用例,结果表明,本文给出的符号算法优于RDS算法、EDAC-FC-DFBB算法和DFBB-ADD算法。
[Abstract]:Many problems in the field of computer science and artificial intelligence can be formalized as a weighted constraint satisfaction problem (WCSP), such as map coloring, production scheduling, product configuration, route selection, logistics planning, solving.WCSP resource allocation problem is to find a violation of the constraint of minimum total cost value assignment completely.WCSP the basic method is a depth first branch and bound algorithm (DFBB), Russian Doll Search (RDS) algorithm is obtained by modifying the DFBB algorithm framework, which can effectively improve the upper and lower bounds of the search, but the efficiency of solving solution obtained after the decomposition efficiency is determined for each sub problem. RDS algorithm is one of the structured record effective technology to avoid repeated search, through storage solution has been in the process of searching information, whether can solve information reuse has been stored, so as to improve the efficiency of the algorithm. By solving the RDS algorithm That one can only handle a constraint on, cannot simultaneously handle multiple constraints on the values, and the algebraic decision diagram (ADD) can efficiently represent and to set data, and the combination of the state explosion problem slowed because of excessive size. So this paper RDS algorithm for solving constraint satisfaction problems symbol the weight was studied. The main work includes: (1) an improved RDS symbol ADD algorithm. RDS algorithm based on the idea of a search in the DFBB algorithm with successive search m sub problems instead. By improving the most constrained variable (MCV) method to select variables, sub problem decomposition into RDS to guide the variables of the original problem, and then reduce the number of decomposition of the sub problem of the RDS algorithm. In order to improve the efficiency of solution of each sub problem, eliminating non RDS variable element calculation with the bucket, reduce the number of variables in DFBB algorithm. In order to further improve the algorithm The efficiency of ADD WCSP with symbolic representation, improved RDS symbol ADD algorithm for solving WCSP. (2) are mixed RDS symbolic ADD algorithm. Through the constraint relationship between RDS variables, given the RDSV-T sub problem decomposition method; in sub problems, the relationship between the structure of sub problems based on a structured record the current storage sub problem, easy to reuse in solving sub problems in the subsequent structured records. By means of symbol ADD WCSP said the hybrid algorithm for solving RDS symbol WCSP. (3) the WCSP problem is randomly generated as a test case, the results show that the symbolic algorithm outperforms the RDS algorithm presented in this paper, EDAC-FC-DFBB algorithm and DFBB-ADD algorithm.

【学位授予单位】：桂林电子科技大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP301.6

【参考文献】