基于受限路径相容的约束传播算法研究

发布时间：2020-06-03 23:23

【摘要】：约束程序(Constraint Programming,CP)是求解组合优化问题的一种经典方法,在交通、电信、教育等领域发挥了重要的作用。CP现在已成功用于车辆路径规划、调度、配置、生物信息等问题的求解中。CP研究的核心问题是约束满足问题(Constraint Satisfaction Problem,CSP)的建模与求解,人工智能领域中很多复杂问题都可以建模为CSP来求解,基于CSP的建模和求解方法是当前研究热点。回溯搜索结合约束传播的方法是目前公认最好的CSP求解方法,而相容性算法是约束传播过程中使用的主要算法,也是影响约束求解效率的重要因素。通常而言,CSP依靠回溯框架进行搜索,在搜索过程中,不断通过相容性算法移除不相容的值来缩减解的搜索空间,从而大大加快算法搜索解的效率。经典的相容性算法有弧相容(Arc Consistency,AC)算法、路径相容(Path Consistency,PC)算法、单弧相容(Singleton Arc Consistency,SAC)算法、受限路径相容(Restricted Path Consistency,RPC)算法和最大受限路径相容(max-Restricted Path Consistency,maxRPC)算法等,其中AC,RPC和maxRPC是三个最流行且效果最好的相容性算法。AC算法因为简单高效而被广泛使用。MaxRPC算法剪枝能力强,在解决大而难的问题上有非常好的效果,而lmaxRPC3rm(light-max RPC3-residues multidirectional,rm表示多向残差)算法是maxRPC算法中表现出众、效率较高的算法。RPC算法具有较强的剪枝能力,且不需要太多时间和空间开销。其最新最好的版本rRPC3(restricted-RPC3)被证明在求解很多问题上能够达到和AC一样的效果,甚至在部分问题上比AC好,因此rRPC3算法是一个很有前景的算法。启发式是算法求解过程中指导变量和值选择的策略。一个好的变量排序启发式(值排序启发式)能正确指导变量(值)的选择,从而大大缩短搜索时间,加快解的搜索过程。因此启发式策略在求解CSP中发挥了重要作用。本文通过对RPC和maxRPC的研究,对非常有前景的rRPC3算法和高效的lmaxRPC3rm算法进行改进。具体工作为:(1)对RPC算法进行改进:基于位操作改进相容性算法的思想已在几种重要的相容性算法中取得了不错的效果,我们利用位操作思想来改进rRPC3算法。因为算法查找AC支持、PC支持以及PC证人这一过程是算法中进行最多、消耗时间最长的一个步骤,因此加快搜索支持和证人的过程非常重要。我们根据位操作数据结构高效快速的特点,利用位操作结构对搜索AC支持、PC支持以及PC证人的过程进行改进,使算法搜索、存取相容性支持和PC证人的过程更加便捷高效,以此实现搜索解更快的效果。(2)对maxRPC算法进行改进:算法lmaxRPC3rm有很好的剪枝能力,但是时空开销较大。我们对lmaxRPC3rm从算法内容和启发式两个方面进行改进。首先对lmaxRPC3rm算法提出两种改进算法,第一种改进不使用原算法存储AC支持和PC支持的LastAC和LastPC数据结构,从而使算法高效易于实现,同时减少时间和空间消耗;第二种改进不同于lmaxRPC3rm算法同时使用AC残差支持和PC残差支持的方式,只保留一种残差支持来存储相容性支持,以此存储和查找AC支持、PC支持和PC证人,进而减少很多冗余残差支持的存取,从而使算法更加高效,同时减少了时间和空间的开销。另外我们应用改进的变量排序启发式对lmaxRPC3rm算法进行改进。结合dom/wdeg(domain/weighted degree)和ABS(Activity-Based Search)启发式提出改进启发式ADW(Activity+dom/wdeg),并将ADW启发式,应用在改进算法中,进一步提升算法效率。我们对rRPC3和lmaxRPC3rm算法分别进行改进,并通过实验评估算法改进效果。对rRPC3算法利用位操作结构对查找支持和存储支持的过程进行优化,取得了较好的效果。对lmaxRPC3rm算法利用减少冗余的残差支持存取的思想进行改进,使算法在剪枝能力和开销之间取得平衡,从而加快算法求解过程。同时将改进的变量排序启发式应用到lmaxRPC3rm的改进算法上,使改进算法有更好的效果。实验表明,我们的改进算法具有明显的效果。未来我们打算利用位操作改进lmaxRPC3rm算法,并将ADW应用于rRPC3的改进算法中。
【图文】：

皇后问题

图 2.1 n 皇后问题求解包括搜索和推理，约束推理包含很多处理约束中之一。约束传播是求解一个约束问题的中心传播包括一些推理，因为一些值或者值的组合播明确禁止这些值或者值的组合。例如，在一须是 R，从欧洲国家抛弃掉单词 NORWAY 和第二个字母必须是 R 的约束条件，不满足的选个变量1x 和2x ，取值从 1 到 10 的问题中，禁止值 5 和 6 作为1x 或者2x 来传播这个约束组合空间。

约束传播,皇后问题,约束网络,变量

图 2.2 弧相容执行前（左）后（右）的约束网络如图 2.3 是 6 皇后问题上通过回溯进行约束传播后传播失败的结果。左图在传播中维持 AC，当变量1x 赋值为 2，，通过维持 AC 可以发现填 1 的部分是不能再放皇后的，即其他变量不可以在这些位置取值。当变量2x 赋值为 5 时，通过维持 AC 发现所有填 2 的地方都不能放皇后，出现域空，从而可以判断1x 取 2，2x取 5 是无解的，从而进行回溯。右图在约束传播中不维持 AC。可以看出进行到第四个变量才能发现域空，多进行了很多约束检查。
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP18

【参考文献】