一种基于时间戳的简单表缩减算法

表约束是一种外延的知识表示方法,每个约束在对应的变量集上列举出所有支持或禁止的元组.广义弧相容（generalized arc consistency,简称GAC）是求解约束满足问题应用最广泛的相容性.Simple Tabular Reduction（STR）是一类高效的维持GAC的算法.在回溯搜索中,STR动态地删除无效元组,降低了查找支持的开销,并拥有单位时间的回溯代价,在高元表约束上获得了广泛运用,并有大量基于STR的改进算法被提出,其中,元组集的压缩表示是目前研究较多的方法.同样基于动态维持元组集有效部分的思想,为STR提出一种检测并删除无效元组和为变量更新支持的算法,作用于原始表约束并拥有单位时间的回溯代价.实验结果表明,该算法在表约束上维持GAC的效率普遍高于现有的非基于压缩表示的STR算法,并且在一些实例上的效率高于最新的基于元组集压缩表示的STR算法.     

优化简单表缩减算法求解因子分解编码实例

表约束在约束程序（constraint programming,简称CP）中被广泛研究.目前,求解表约束问题效率最高的算法是CT （compact-table）和STRbit （simple tabular reduction bit）.它们在搜索过程中维持广义弧相容（generalized arc consistency,简称GAC）.完全成对相容（full pairwise consistency,简称fPWC）是一种强于GAC的相容性关系,目前,实现fPWC效率最高的算法是PW-CT,但是它无法直接在通用的求解器上实现.因子分解编码（factor-decomposition encoding,简称FDE）是实现fPWC的一种编码方式,通常和简单表缩减（STR）算法一起来使用.当前效率最高的STR算法使用了bitset的数据结构,用这些算法来求解FDE实例可能会造成内存溢出.提出了STRFDE算法——一种使用bitset结构来求解FDE实例的方法.它结合了CT和STRbit的优势,在保证求解效率的同时,使占用的内存尽可能小.实验结果表明,在许多存在非平凡相交的实例上,该算法是有竞争力的.     

优化求解约束满足问题的MDDc和STR3算法

广义弧相容是求解约束满足问题应用最广泛的相容性,MDDc、STR2和STR3是表约束上维持广义弧相容应用较多的算法,其中MDDc基于对约束压缩表示的思想,将表约束表示成多元决策图,对各个元组之间存在较多交叠部分的约束具有很好的压缩效果;STR3同STR2一样基于动态维持有效元组的思想,当元组集规模缩减较慢时STR3维持广义弧相容的效率高于STR2.通过深入分析发现MDDc中查找节点的有效出边和STR3中检测并删除无效元组是耗时最多的操作.本文分别对MDDc和STR3提出一种自适应查找有效出边和检测删除无效元组的方法AdaptiveMDDc和AdaptiveSTR,对于同一操作,可以根据回溯搜索不同阶段的局势自适应地选择代价最小的实现方法,得益于较低的判断代价以及回溯搜索不同阶段采用不同方法的效率差异,AdaptiveMDDc和AdaptiveSTR相比原算法速度提升显著,其中AdaptiveSTR在一些问题上相比STR3提速三倍以上.     

一种高效的FDE并行传播算法

约束规划(constraint programming, CP)是表示和求解组合问题的经典范式之一.扩展约束(extensional constraint)或称表约束(table constraint)是约束规划中最为常见的约束类型.绝大多数约束规划问题都可以用表约束表达.在问题求解时,相容性算法用于缩减搜索空间.目前,最为高效的表约束相容性算法是简单表约缩减(simple table reduction, STR)算法簇,如Compact-Table (CT)和STRbit算法.它们在搜索过程中维持广义弧相容(generalized arc consistency, GAC).此外,完全成对相容性(full pairwise consistency, fPWC)是一种比GAC剪枝能力更强的相容性.最为高效的维持fPWC算法是PW-CT算法.多年来,人们提出了多种表约束相容性算法来提高剪枝能力和执行效率.因子分解编码(factor-decomposition encoding, FDE)通过对平凡问题重新编码.它一定程度地扩大了问题模型,使在新的问题上维持相对较弱的GAC等价于在原问题...     

负表约束的简单表缩减广泛弧相容算法

广泛弧相容算法（generalized arc consistency,简称GAC）,是求解约束满足问题的核心方法.表约束理论上可以表示所有约束关系,在过去10年中,有很多应用于表约束的广泛弧相容算法被提出来.在这些算法中,表缩减算法的效率非常高.但是目前的表缩减算法只能应用于正表约束,无法直接应用于负表约束.首先,提出一种表缩减算法STR-N,可以直接应用于负表约束;然后,给出了STR-N的两个改进版本STR-N2和STR-NIC.实验结果显示,STR-N算法在负表约束上的求解效率具有明显的优势.     

一种强鲁棒性自适应活性边表算法

为提升多边形的填充效率,在分析和比较常见填充算法后,以活性边表算法为基础,深入挖掘不同扫描方向上的求交次数及多边形自交特性,提出一种强鲁棒性自适应活性边表算法。新算法引入横度和纵度的概念表示横纵扫描方向上的求交次数,并以此为标准自适应选择扫描方向。此外,通过对活性边表中相邻交点的横坐标进行检测和纠正,正确而高效地填充了自交多边形。经实验验证,新算法灵活的自适应性和高效的自交纠正方法,大大提高了时间效率和鲁棒性。     

基于ETRN具有任意压缩率的彩色加密图像有损压缩

当前大多数的先加密后压缩ETC（encryption-then-compression）方法只能够获得有限固定的压缩率,而无法获取到实际需求的任意压缩率。针对此问题提出一种具有任意压缩率的加密彩色图像有损压缩算法,该算法采用均匀下采样和随机下采样有机结合的方式对加密图像进行压缩,以获得加密图像的任意压缩率。接收方接收到加密图像的压缩序列后通过解压解密获得解密图像,随后把从解密图像有损重构原始图像的过程表征为一个结合下采样压缩方式约束的最优化问题,并设计一种基于卷积神经网络的有损ETC系统图像重构模型ETRN（ETC-oriented reconstruction network）来求解该优化问题。ETRN模型包含浅层特征提取层SFE（shallow feature extraction）、残差堆叠模块RIR（residual in residual）、残差信息补充模块RCS（residual content supplementation）、下采样约束模块DC（down-sampling constraint）。实验仿真结果表明,提出的加密彩色图像有损压缩算法能够获得优秀的加密压缩和重构性能,充分体现了该方法的可行性和有效性。     

方位关系约束满足问题的推理求解

约束满足问题（Constraint Satisfaction Problems CSP）是人工智能的一个研究领域,诸如空间查找、规划等问题都可转化为约束满足问题。方位关系是空间关系的重要组成部分,用以确定空间对象间的一种顺序。本文研究了空间方位关系模型,给出了方位关系约束的一般表示形式。在此基础上,利用组合表推理给出了方位关系约束满足问题的一个推理求解算法,该算法的时间复杂度为O（n^2）。     

基于非局部低秩和自适应量化约束先验的HEVC后处理算法

经高效视频编解码标准HEVC压缩后的视频在高压缩比、低码率的情况下存在明显的压缩效应。针对该问题,提出了一种基于非局部低秩(Non-local Low-rank,NLLR)和自适应量化约束(Adaptive Quantization Constraint,AQC)先验的HEVC后处理算法。该算法首先构造在最大后验概率框架下的优化问题,然后利用解码后的压缩视频和量化参数QP获取非局部低秩和自适应量化约束先验信息,最后利用split-Bregman迭代算法来解决所提的优化问题,从而有效去除压缩效应,提升重建视频质量。其中,非局部低秩先验通过构建基于相似块聚类的非局部低秩模型来获得;自适应量化约束先验通过联合不同量化参数QP下的约束特性与视频的DCT域块活动性来获得。实验结果表明,在同等码率的情况下,与HEVC标准相比,所提算法在帧内编码模式下可以达到平均0.2597 dB的PSNR提升,在帧间编码模式下可以达到平均0.2828 dB的PSNR提升。     

约束在序列模式挖掘中的应用研究

分析了用规则表达式表示约束的原因和目标,研究了规则表达式表示的约束在序列模式挖掘中的应用思想,利用对比的方法对SPIRIT系列算法进行研究,并介绍了算法的剪枝过程。     

STR2: optimized simple tabular reduction for table constraints

Table constraints play an important role within constraint programming. Recently, many schemes or algorithms have been proposed to propagate table constraints and/or to compress their representation. In this paper, we describe an optimization of simple tabular reduction (STR), a technique proposed by J. Ullmann to dynamically maintain the tables of supports when generalized arc consistency (GAC) is enforced/maintained. STR2, the new refined GAC algorithm we propose, allows us to limit the number of operations related to validity checking and search of supports. Interestingly enough, this optimization makes simple tabular reduction potentially r times faster where r is the arity of the constraint(s). The results of an extensive experimentation that we have conducted with respect to random and structured instances indicate that STR2 is usually around twice as fast as the original STR, two or three times faster than the approach based on the hidden variable encoding, and can be up to one order of magnitude faster than previously state-of-the-art (generic) GAC algorithms on some series of instances. When comparing STR2 with the more recently developed algorithm based on multi-valued decision diagrams (MDDs), we show that both approaches are rather complementary.     

Strong local consistency algorithms for table constraints

Table constraints are important in constraint programming as they are present in many real problems from areas such as configuration and databases. As a result, numerous specialized algorithms that achieve generalized arc consistency (GAC) on table constraints have been proposed. Since these algorithms achieve GAC, they operate on one constraint at a time. In this paper we propose new filtering algorithms for positive table constraints that achieve stronger local consistency properties than GAC by exploiting intersections between constraints. The first algorithm, called maxRPWC+, is a domain filtering algorithm that is based on the local consistency maxRPWC and extends the GAC algorithm of Lecoutre and Szymanek (2006). The second algorithm extends the state-of-the-art STR-based algorithms to stronger relation filtering consistencies, i.e., consistencies that can remove tuples from constraints’ relations. Experimental results from benchmark problems demonstrate that the proposed algorithms are quite competitive with standard GAC algorithms like STR2 in some classes of problems with intersecting table constraints, being orders of magnitude faster in some cases.     

基于改进鲸鱼优化的覆盖表生成算法

为提高组合测试中覆盖表生成效率,基于覆盖表生成的离散性,提出一种改进的鲸鱼优化算法。该算法首先利用编码转换的思想,将鲸鱼个体连续运动方式编码为适用于覆盖表的离散方式;其次,在算法的开发与搜索阶段加入迭代演化算子,以提高算法的全局搜索能力;最后,针对覆盖表生成中算法本身的局限问题,使用平均海明距离跳出局部最优,并通过约束求解器和惩罚函数法增加约束处理机制,以提高算法实际应用能力。实验结果表明,与其它已有算法相比,所提出的算法在覆盖表生成规模上具有更好的优势。     

时空推理中自动生成复合表的通用算法

时空推理是面向时间/空间问题的研究领域,在人工智能(如语义Web、机器人导航、自然语言处理、物理过程的定性模拟和常识推理等)和其他领域有着广泛的应用前景.复合推理在时空推理中具有重要作用,是约束满足问题等其他定性推理的基础.复合推理是由R(a,b)和R(b,c)决定R(a,c)的一种演绎推理.一般将关系复合结果放在复合表中备查.但目前复合表的建立需要逐个模型进行手工推导,少数模型给出了独立的复合表生成算法,没有适合多种时空关系模型、能自动生成复合表的通用算法.为此,提出了一种能自动生成复合表的通用算法.首先,给出了基于空间划分的通用时空表示模型.在此基础上,提出了基于场景检测的通用复合表生成算法.通过理论分析和对RCC、宽边界、区间代数等20余种典型时空模型的测试,证明了本算法对于所有以精确区域(或区间)为基础的确定、不确定时空模型均能正确快速地生成复合表.     

线性序约束的规范表达

文中研究了约束数据库中线性序约束关系的规范表达。提出一种线性序约束元组的表结构规约形式,增加了线性冗余和变量可约减两条新的规约原则,并给线性序元组规约算法ＬＣＴＲＡ,探讨了绝对点语义和复杂对象语言下线性序约束关系的规范型。