检索结果-内蒙古大学图书馆

软件学报 2019年第11期30卷 3355-3363页

作者：杨明奇李占山张家晨吉林大学计算机科学与技术学院吉林长春130012 符号计算与知识工程教育部重点实验室(吉林大学) 吉林长春130012

表约束是一种外延的知识表示方法,每个约束在对应的变量集上列举出所有支持或禁止的元组.广义弧相容(generalized arc consistency,简称GAC)是求解约束满足问题应用最广泛的相容性.Simple Tabular Reduction(STR)是一类高效的维持GAC的... 详细信息

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

关键词：约束满足问题简单表缩减表约束广义弧相容

来源：评论

学校读者我要写书评

暂无评论

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

引用

软件学报 2016年第11期27卷 2701-2711页

作者：李宏博梁艳春李占山吉林大学计算机科学与技术学院吉林长春130012 符号计算与知识工程教育部重点实验室(吉林大学) 吉林长春130012

广泛弧相容算法(generalized arc consistency,简称GAC),是求解约束满足问题的核心方法.表约束理论上可以表示所有约束关系,在过去10年中,有很多应用于表约束的广泛弧相容算法被提出来.在这些算法中,表缩减算法的效率非常高.但是目前的... 详细信息

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

关键词：约束满足问题广泛弧相容简单表缩减负表约束

来源：评论

学校读者我要写书评

暂无评论

一种基于STR算法的新表压缩方法

引用

计算机研究与发展 2018年第12期55卷 2734-2740页

作者：董爱迪李占山于海鸿吉林大学计算机科学与技术学院长春130012 符号计算与知识工程教育部重点实验室(吉林大学) 长春130012

约束传播是约束编程的关键方法,近些年来,一些约束传播算法中频繁用到简单表缩减(simple tabular reduction,STR)算法来降低约束表的空间消耗,同时提高广义弧相容(generalised arc consistent,GAC)算法的运行速度.短支持方法是在约束传... 详细信息

约束传播是约束编程的关键方法,近些年来,一些约束传播算法中频繁用到简单表缩减(simple tabular reduction,STR)算法来降低约束表的空间消耗,同时提高广义弧相容(generalised arc consistent,GAC)算法的运行速度.短支持方法是在约束传播算法中使用最广泛的一种表压缩方式,但当约束表压缩率较低时,短支持方法提高运行速度效果不明显.因此提出一种压缩约束表的新算法STRO(simple tabular reduction optimization),结合短支持压缩和位操作,在提高STR算法的运行速度的同时压缩表空间效果更好.实验结果表明:在约束表的平均大小不是特别小的情况下,STRO与ShortSTR2,STR2算法相比,速度更快、效率更高;与STRbit算法相比,在时间上可以替代STRbit算法,但STRO算法的表压缩率更大、更加节省空间.

关键词：约束传播约束编程表约束表压缩方法位操作广义弧相容简单表缩减

来源：评论

学校读者我要写书评

暂无评论

基于多核CPU的表约束并行传播模式研究

引用

软件学报 2021年第9期32卷 2769-2782页

作者：陈佳楠李哲李占山吉林大学软件学院吉林长春130012 吉林大学计算机科学与技术学院吉林长春130012 符号计算与知识工程教育部重点实验室(吉林大学) 吉林长春130012

并行传播是并行约束程序领域中的一个研究方向,其研究内容是如何并行执行在约束上的过滤算法.根据维持表约束网络广义弧相容(generalized arc consistency,简称GAC)的串行传播模式,提出了维持表约束网络临时广义弧相容(temporary genera... 详细信息

并行传播是并行约束程序领域中的一个研究方向,其研究内容是如何并行执行在约束上的过滤算法.根据维持表约束网络广义弧相容(generalized arc consistency,简称GAC)的串行传播模式,提出了维持表约束网络临时广义弧相容(temporary generalized arc consistency,简称TGAC)的并行传播模式,该模式基于多核CPU,由并行传播算法和并行过滤算法两部分组成;之后,给出了并行传播模式的可靠性证明,而且通过对并行传播模式的最坏时间复杂度分析,可以认为并行传播模式在平均过滤时间较长的实例上要快于串行传播模式;最终的实验结果也验证了上述结论,并行传播模式在多数实例集上取得了从1.4-3.4不等的加速比.

关键词：约束满足问题并行传播广义弧相容表约束简单表缩减

来源：评论

学校读者我要写书评

暂无评论

自适应表压缩方法优化STR算法

引用

计算机工程与科学 2018年第12期40卷 2243-2251页

作者：李少兴李占山于海鸿吉林大学计算机科学与技术学院吉林长春130012

表约束,也称为外延式约束,是约束编程领域最常见的约束形式,表压缩方法通过紧凑的表示元组集可以极大地缩减空间消耗,同时加速GAC算法。笛卡尔乘积表示和短支持是表约束中最常见的两种表压缩方法,两种表压缩方法在同一问题上的压缩率是... 详细信息

表约束,也称为外延式约束,是约束编程领域最常见的约束形式,表压缩方法通过紧凑的表示元组集可以极大地缩减空间消耗,同时加速GAC算法。笛卡尔乘积表示和短支持是表约束中最常见的两种表压缩方法,两种表压缩方法在同一问题上的压缩率是影响它们优化效果的主要原因。基于STR算法提出一种自适应表压缩方法,在求解问题时自适应选择压缩率大的表压缩方法,将自适应表压缩方法应用到STR2上提出了STR2-Adaptive算法,可以同时覆盖两种表压缩方法的优势。实验结果表明,STR2-Adaptive算法在绝大部分实例上都能自适应选择最佳的表压缩方法,有效地减少了STR2算法空间消耗和CPU运行时间。然后将自适应表压缩方法扩展到采用了高效的比特向量表示的STRbit算法上提出了STRbit-Adaptive算法。实验结果表明,STRbit-Adaptive算法效率同样普遍优于STRbit算法。

关键词：约束编程表约束简单表缩减表压缩自适应选择比特向量

来源：评论

学校读者我要写书评

暂无评论

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

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

引用

作者：杨明奇吉林大学

学位级别：硕士

表约束是一种外延的知识表示方法,每个约束包含一组变量上所有支持或禁止的元组。广义弧相容(GAC)是求解多元约束满足问题应用最广泛的相容性。简单表缩减(STR)是一类在表约束上维持GAC的算法,基于动态维持元组集有效部分的策略,在搜索... 详细信息

表约束是一种外延的知识表示方法,每个约束包含一组变量上所有支持或禁止的元组。广义弧相容(GAC)是求解多元约束满足问题应用最广泛的相容性。简单表缩减(STR)是一类在表约束上维持GAC的算法,基于动态维持元组集有效部分的策略,在搜索的每一阶段维持相容性时,STR移除当前的无效元组,从而降低了查找支持的开销。在搜索发生回溯时,STR拥有单位时间的恢复元组集有效部分的代价。STR在高元表约束上获得了广泛运用,大量基于STR的改进算法被提出,其中元组集的压缩表示是目前研究较多的方法。本文提出的STR2*同样基于动态维持元组集有效部分的策略,但采用一种新的基于列的方式存储约束关系中的元组,并将删除无效元组以及为变量值查找支持的操作分别转化为与之对应的列操作。此外,STR2*使用时间戳标记变量和约束上的操作次序,降低了获取论域发生改变的变量的计算开销,并精简了数据结构。实验结果表明该算法在表约束上维持GAC的效率普遍高于现有的非基于压缩表示的STR算法,并且在一些实例上的效率高于最新的基于元组集压缩表示的STR算法。MDDc、STR2和STR3均是表约束上维持GAC的算法,MDDc将约束关系构建成多元决策图,当元组之间存在较多交叠部分时,对应的多元决策图压缩效果显著,遍历多元决策图获取支持的代价降低,进而提升了维持GAC的效率。STR2将约束关系表示为表,在维持GAC时检测当前表中所有元组获取有效元组集,然后对有效元组集投影更新变量值的支持。STR3将约束关系表示为对偶表,每个变量值维护一个包含该值的所有元组的副本,在维持GAC时更新所有值维护的当前有效元组。STR2与STR3维持相容性的效率与元组集有效部分的缩减速度有关,当缩减较慢时,STR3的效率高于STR2,反之,STR2的效率高于STR3。分析发现,MDDc中查找节点的有效出边和STR3中删除无效元组是整个求解过程中最密集且耗时最多的操作。为此,本文提出一种采用自适应查找有效出边的MDDc算法——AdaptiveMDDc,以及一种采用自适应删除无效元组的STR算法——AdaptiveSTR。在回溯搜索的不同阶段,AdaptiveMDDc可以根据当前多元决策图有效部分的规模自适应地选择效率最高的查找有效出边的方法,而AdaptiveSTR可以根据当前对偶表有效部分的规模自适应地选择效率最高的删除无效元组的方法,得益于较低的判断代价以及回溯搜索不同阶段采用不同方法的效率差异,AdaptiveMDDc和AdaptiveSTR相比原算法速度提升显著,其中AdaptiveSTR在一些问题上相比STR3提速三倍以上。

关键词：约束满足问题广义弧相容自适应多元决策图表约束简单表缩减

来源：评论

学校读者我要写书评

暂无评论

基于笛卡尔积压缩的负表约束上相容性算法的研究

基于笛卡尔积压缩的负表约束上相容性算法的研究

引用

作者：蔡毛毛吉林大学

学位级别：硕士

约束规划是人工智能领域的重要分支,在产品配置、任务调度、组合优化等问题上有广泛的应用。约束规划为实际问题提供了一种简单有效的解决方案,首先通过约束建模将实际问题抽象成统一的约束模型,然后利用约束求解技术对模型进行求解。... 详细信息

约束规划是人工智能领域的重要分支,在产品配置、任务调度、组合优化等问题上有广泛的应用。约束规划为实际问题提供了一种简单有效的解决方案,首先通过约束建模将实际问题抽象成统一的约束模型,然后利用约束求解技术对模型进行求解。结合相容性技术的回溯搜索算法是约束求解的主流方法之一,通过相容性技术对回溯搜索过程进行剪枝可以提高问题求解的效率。表约束是一种重要的约束的表示形式,通过枚举支持或者禁止元组将约束以表格的形式呈现。表约束处理的目的是维持约束网络的相容性,表约束处理对整个问题求解过程影响巨大。广义弧相容(GAC)是目前应用最为广泛的相容性,其简单高效性在大多数问题实例上有良好的效果。简单表缩减算法(STR算法)及其优化(STR2算法和STR3算法)是在表约束上维持广义弧相容的高效算法,STR算法通过动态维持有效支持元组来保证约束网络的相容性。STR2算法对STR算法做出两点改进,一方面如果两次相容性检查过程中变量论域未发生改变,则跳过该变量上值的有效性检查。另一方面如果某变量论域中的值均存在有效支持,则停止为该值继续寻找支持。STR3算法将表约束的表示形式变为对偶表,在对偶表上维持约束网络的相容性。然而随着问题中变量个数的增加,表约束规模可能呈指数阶上升,表约束处理的效率将会下降。有学者使用笛卡尔积压缩方法对正表约束进行压缩,并提出压缩正表上维持广义弧相容的方法STR2-C算法和STR3-C算法,在压缩率较高的问题实例上,其空间规模和时间效率均优于STR2算法和STR3算法。负表是正表的互补表示形式,负表是约束上所有禁止元组的集合。当负表规模较小时,直接处理负表效率更高。STR-N算法是针对负表约束提出的简单表缩减算法,可以直接在负表上维持约束网络的相容性。STR-N算法计算有效元组与有效禁止元组的差值,根据差值是否为零判断论域中的值是否满足广义弧相容,从而进一步检查整个约束网络的相容性。但STR-N算法维持约束网络相容性时需要遍历负表中的所有元组,当负表规模较大时算法效率较低。因此,受STR2-C算法和STR3-C算法的启发,本文对STR-N算法进行了优化,首先使用笛卡尔积压缩方法将负表进行压缩得到压缩负表,并提出在压缩负表上维持广义弧相容的方法STRC-N算法。STRC-N算法同样是通过计算有效元组与有效禁止元组的差值来检查约束网络的相容性,但是STRC-N算法统计有效禁止元组数的方法却有所不同。STRC-N算法直接处理有效压缩禁止元组,有效压缩禁止元组上一次遍历可以统计多个有效标准禁止元组。经过笛卡尔积压缩后,压缩负表的空间规模更小,STRC-N算法更加节省空间。得益于压缩负表规模的减小,STRC-N算法相对于STR-N算法速度更快,效率更高。

关键词：人工智能约束规划表约束简单表缩减笛卡尔积压缩

来源：评论

学校读者我要写书评

暂无评论

约束程序的搜索技术研究

约束程序的搜索技术研究

引用

作者：陈佳楠吉林大学

学位级别：硕士

维持表约束网络广义弧相容(generalized arc consistency,简称GAC)的串行传播模式是约束程序搜索技术研究的一个重要分支,该模式由串行传播算法和串行过滤算法两部分组成,串行传播算法会依次执行在表约束上维持GAC的串行过滤算法。为了... 详细信息

维持表约束网络广义弧相容(generalized arc consistency,简称GAC)的串行传播模式是约束程序搜索技术研究的一个重要分支,该模式由串行传播算法和串行过滤算法两部分组成,串行传播算法会依次执行在表约束上维持GAC的串行过滤算法。为了进一步提升串行传播模式的效率,本文关注到了并行计算。并行计算是在不改变预期结果的情况下,同时对问题的多个部分进行处理的能力。随着计算机并行处理能力的发展,约束程序与并行计算的结合研究已成为被关注的领域,即并行约束程序。针对并行约束程序的研究大致可分为以下几类:并行传播、搜索空间分割、组合算法和问题分解等。其中,并行传播是指并行执行在约束上的过滤算法,其研究意义在于利用并行计算提高约束传播的效率。本文提出了维持表约束网络临时广义弧相容(temporary generalized arc consistency,简称TGAC)的并行传播模式。该模式基于多核CPU,由并行传播算法和并行过滤算法两部分组成,并行传播算法利用线程池并行调用维持表约束TGAC的并行过滤算法。本文给出了并行传播模式的可靠性证明,即并行传播模式也维持表约束网络GAC。并行传播模式的最坏时间复杂度也得到了分析,经过与串行传播模式最坏时间复杂度的对比,我认为并行传播模式在平均过滤时间较长的实例上要快于串行传播模式。最终的实验结果也验证了上述结论。对照实验在22组实例集上进行,使用回溯搜索算法分别测试了串行传播模式和并行传播模式。在串行传播模式下,串行过滤算法分别使用CT和STRbit;在并行传播模式下,并行过滤算法分别使用PCT和PSTRbit,线程池的并行度依次被置为2、4和6。最终的实验结果表明,在17组实例集上,并行传播模式要快于串行传播模式,而且在其中的多数实例集上取得了从1.4至3.4不等的加速比。

关键词：约束满足问题并行传播广义弧相容表约束简单表缩减

来源：评论

学校读者我要写书评

暂无评论

自适应表压缩方法优化STR算法的研究

自适应表压缩方法优化STR算法的研究

引用

作者：李少兴吉林大学

学位级别：硕士

约束编程(CP)是用于建模和求解组合约束问题的通用且灵活的框架。表约束(也称为扩展约束)明确表示它们所涉及的变量的值的允许组合作为元组序列,称为表。表约束理论上可以编码任何类型的约束,并且是约束编程中最有用的约束之一。这些约... 详细信息

约束编程(CP)是用于建模和求解组合约束问题的通用且灵活的框架。表约束(也称为扩展约束)明确表示它们所涉及的变量的值的允许组合作为元组序列,称为表。表约束理论上可以编码任何类型的约束,并且是约束编程中最有用的约束之一。这些约束可以从已经从配置问题中的数据库读取的数据生成,或者可以编码用户的偏好以及其他应用程序。表约束将任意约束明确定义为一组解(元组)或非解。因此,表约束的空间与元组的数量成比例。简单表缩减(STR)通过维护有效元组的表来动态地缩减表大小,已被证明可以有效地维持广义弧一致性(GAC)。基于STR改进的STR2和STR3算法是当前主流的广义弧一致性算法,STR2和STR3在不同类型的实例下各有优势。该领域最近的一个重大改进是在表约束中使用比特向量来表示元组的有效性,在为变量值寻找支持时使用高效的比特并行操作。算法STRbit和Compact-Table都是结合了STR和比特向量操作的优点,已经显示出比过去十年中开发的最佳GAC算法快一个数量级。表约束有一个主要的缺点:存储它们所需的内存空间可能会随着约束元数而呈指数增长,为了解决这个问题,相继提出各种表压缩方法。当表约束规模很大时,恰当的表压缩方法不仅能极大的减少空间消耗,同时可能极大提高广义弧一致性算法时间开销。短支持和笛卡尔乘积表示是表约束上最常见的两种表压缩方法,约束表可以采用笛卡儿乘积表示进行压缩,这种压缩方法最早应用在对称破除和nogood学习中.使用元组的笛卡尔乘积表示来压缩表约束,称其为c-tuple。短支持允许元组中存在由符号*表示的通用的值,这意味着一些变量可以取论域中任意值。采用这两种压缩方法改进主流的广义弧相容算法STR2分别得到表压缩算法shortSTR2和STR2-C,在不同问题上的优化效果存在很大的差异,我们发现两种表压缩方法在同一问题上的压缩率是影响优化效果的主要原因.本文提出一种自适应表压缩方法,通过比较两种表压缩方法的压缩率来选择压缩率大的表压缩算法,将自适应表压缩方法应用到算法STR2上我们提出了STR2-Adaptive算法,同时覆盖两种表压缩方法的优势.实验结果表明STR2-Adaptive在绝大部分问题上都能自适应的选择最佳的表压缩方法,额外时间开销仅占1%左右,从而最大化压缩表约束空间并优化STR2算法。进一步,我们将自适应表压缩方法扩展到结合了高效的比特向量按位操作的STRbit算法上提出了STRbit-Adaptive算法,实验表明STRbit-Adaptive算法同样在绝大部分问题上有效的提高STRbit算法运行速度。

关键词：约束编程表约束简单表缩减表压缩自适应选择比特向量

来源：评论

学校读者我要写书评

暂无评论

表约束的相容性技术研究

表约束的相容性技术研究

引用

作者：王瑞伟吉林大学

学位级别：硕士

对于约束可满足问题,在回溯搜索的过程中应用相容性进行剪枝是最高效的完备求解算法之一。在非二元约束上,广义弧相容是目前被应用最广的相容性,同时简单表缩减算法(STR)及其优化的算法(STR2)是在表约束上维持广义弧相容最高效的算法之... 详细信息

对于约束可满足问题,在回溯搜索的过程中应用相容性进行剪枝是最高效的完备求解算法之一。在非二元约束上,广义弧相容是目前被应用最广的相容性,同时简单表缩减算法(STR)及其优化的算法(STR2)是在表约束上维持广义弧相容最高效的算法之一。最近,新的约束表示形式dual表被提出,同时学者们给出了在dual表上维持广义弧相容的路径最优算法STR3,在不同类型的约束可满足问题实例上,STR3和STR2各有优势。在本文中,我们提出了更加高效的比特表,比特表采用比特向量来表示约束的dual表,同时我们给出在比特表上维持广义弧相容的高效算法STRbit。然后,我们通过结合比特表和笛卡尔积压缩表提出比特笛卡尔积压缩表,在许多实例上,比特笛卡尔积压缩表具有很高的压缩效率,甚至能够达到1000倍的压缩效果。接着我们给出在比特笛卡尔积压缩表上维持广义弧相容的高效算法STRbit-C。在许多问题实例上,我们的算法(STRbit和STRbit-C)要比当前主流的广义弧相容算法快,主流的算法是指STR2,STR3,MDDc及其它们的压缩表版本STR2-C和STR3-C,甚至在一些问题上能够快70多倍。最近,许多关于完全成对相容(full pair-wise consistency)的算法被提出,其中e STR算法是在表约束上维持的完全成对相容的高效算法之一,e STR算法通过扩展利用STR的算法框架和维护ctr计数器使得检测约束元组的pair-wise支持的时间复杂度为O(1),在许多问题实例上,e STR算法要比STR算法快。e STR算法中存在许多冗余的检测,约束的元组只需要检测可能失去pair-wise支持的相邻约束,我们维护数据结构PWsup来记录可能失去pair-wise支持的相邻约束,相应在算法中我们只需要检测在PWsup中的相邻约束。此外,约束元组检测PW支持以后,约束范围中一些变量的有效性便不需要再次检测,相应我们利用极小约束范围来记录需要被检测的变量。通过利用这两种数据结构,我们能够避免许多冗余的检测,在许多问题实例上,优化后的算法比原始的e STR算法具有更好的空间和时间效率。

关键词：约束可满足问题广义弧相容成对相容简单表缩减比特向量

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：