表约束上的约束传播算法研究

发布时间：2022-01-22 07:34

　　表约束是一种外延的知识表示方法,每个约束包含一组变量上所有支持或禁止的元组。广义弧相容（GAC）是求解多元约束满足问题应用最广泛的相容性。简单表缩减（STR）是一类在表约束上维持GAC的算法,基于动态维持元组集有效部分的策略,在搜索的每一阶段维持相容性时,STR移除当前的无效元组,从而降低了查找支持的开销。在搜索发生回溯时,STR拥有单位时间的恢复元组集有效部分的代价。STR在高元表约束上获得了广泛运用,大量基于STR的改进算法被提出,其中元组集的压缩表示是目前研究较多的方法。本文提出的STR2*同样基于动态维持元组集有效部分的策略,但采用一种新的基于列的方式存储约束关系中的元组,并将删除无效元组以及为变量值查找支持的操作分别转化为与之对应的列操作。此外,STR2*使用时间戳标记变量和约束上的操作次序,降低了获取论域发生改变的变量的计算开销,并精简了数据结构。实验结果表明该算法在表约束上维持GAC的效率普遍高于现有的非基于压缩表示的STR算法,并且在一些实例上的效率高于最新的基于元组集压缩表示的STR算法。MDDc、STR2和STR3均是表约束上维持GAC的算法,MDDc将约束关系构建... 

【文章来源】：吉林大学吉林省 211工程院校 985工程院校 教育部直属院校

【文章页数】：53 页

【学位级别】：硕士

【部分图文】：

sparseset操作的演示图3.1sparseset操作的演示，(a)初始阶段，S为空，S.members=0，t指向的数组的下标表示S.members在t阶段的值；(b)在t=1阶段加入元素3；(c)在t=2

第 3 章 一种效率更高的 STR 算法下进行，元组集规模缩减较快，avgP<30%，STR2*优于 STR3，少数元组集缩减较慢的实例上，avgP>30%，并且表约束规模足够大时，STR3 优于 STR2*。表3.1 和图 3.2 中右图可以看出绝大多数实例上 STR2*优于 STR3，部分实例上STR2*的效率是 STR3 的 20 倍以上。

图 3.3 不同算法求解时间的对比STRbit: 在一些拓扑结构复杂且表约束规模较小 和 dubois 两种算法维持元组集有效部分的代价据结构简单维护代价较低，求解效率稍优于 S快的实例上，例如 rand-15-23、rand-8-20 和 bd超过两倍的效率提升。表 3.2 可以看出 STR2*STRbit。由于不同类问题的实例集中的实例个数的 rand-3、rand-5、crossword 三类问题的实例总图 3.3 的散点图中才会有 STRbit 在多数实例上


本文编号：3601798