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

发布时间：2020-03-20 01:56

【摘要】：约束规划是人工智能领域的重要分支,在产品配置、任务调度、组合优化等问题上有广泛的应用。约束规划为实际问题提供了一种简单有效的解决方案,首先通过约束建模将实际问题抽象成统一的约束模型,然后利用约束求解技术对模型进行求解。结合相容性技术的回溯搜索算法是约束求解的主流方法之一,通过相容性技术对回溯搜索过程进行剪枝可以提高问题求解的效率。表约束是一种重要的约束的表示形式,通过枚举支持或者禁止元组将约束以表格的形式呈现。表约束处理的目的是维持约束网络的相容性,表约束处理对整个问题求解过程影响巨大。广义弧相容(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算法速度更快,效率更高。
【图文】：

-皇后问题回溯搜索片段

相容性实例图
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP18

【相似文献】

相关期刊论文 前8条

1 李金多;杨天鸿;邓文学;郑广斌;林毅斌;刘清福;;珲春曙光金铜矿地表约束对优化结果的影响分析[J];金属矿山;2018年04期

2 李宏博;梁艳春;李占山;;负表约束的简单表缩减广泛弧相容算法[J];软件学报;2016年11期

3 蔡毛毛;李占山;董学阳;;一种笛卡尔积压缩的负表约束上表缩减算法[J];吉林大学学报(理学版);2019年03期

4 杜江珊;李占山;;基于减少检索的负表约束优化算法[J];吉林大学学报(理学版);2018年02期

5 ;EDA[J];电子设计应用;2005年05期

6 孙永玉,王哲,楼荣生;信息资源词典系统及其服务接口标准[J];计算机工程;1998年07期

7 董爱迪;李占山;于海鸿;;一种基于STR算法的新表压缩方法[J];计算机研究与发展;2018年12期

8 蔡朝晖;;数据库设计中有效选择键和索引[J];牡丹江师范学院学报(自然科学版);2005年03期

相关硕士学位论文 前4条

1 蔡毛毛;基于笛卡尔积压缩的负表约束上相容性算法的研究[D];吉林大学;2019年

2 杨明奇;表约束上的约束传播算法研究[D];吉林大学;2018年

3 王瑞伟;表约束的相容性技术研究[D];吉林大学;2016年

4 周珊珊;基于流表约束的SDN组播研究[D];山东大学;2016年

，

本文编号：2591062