改进求解约束满足问题粗粒度弧相容算法

约束满足问题在人工智能领域有着广泛的应用.研究了约束满足问题的粗粒度维持弧相容求解算法,发现在求解过程中,对于指向已赋值变量的弧存在无效的修正检查,证明了这类修正检查是冗余的.提出一种方法避免这类冗余的修正检查,给出改进后的粗粒度弧相容算法的基本框架AC3_frame_ARR,该改进框架可用于改进所有粗粒度弧相容算法.实验结果表明,经过AC3_frame_ARR改进后的算法最多可以节省80%的修正检查次数和40%的求解耗时.

基于动态值启发式的约束满足求解算法

为提高约束满足问题的求解效率,提出了一种基于动态值启发式的约束满足问题求解算法。该算法在求解过程中吸收了以往启发式算法的优点,充分利用了预处理和弧相容检查阶段的信息。不但加入了变量启发式,而且在实例化变量时,对所有值的优先级进行动态的改变,从而实现了动态值启发式。比较了静态值启发式和动态值启发式的效率,分析了该算法的优缺点。通过随机问题标准库用例测试表明,该算法比经典主流算法具有更好的效率优势。

约束满足问题中一致性算法的分析与研究

约束满足问题是人工智能领域的重要研究方向,其求解方法有三种,搜索、一致性算法和约束传播,其中一致性算法通常通过缩减问题域来提高搜索算法的效率。着重介绍了几种常用的一致性算法,并对几种常用算法进行了分析、比较和研究。

非二元条件约束满足问题求解

非二元条件约束满足问题是二元条件约束满足问题的泛化。给出了非二元条件约束满足问题模型;针对求解过程中激活性约束引起的变量空间变化,分别采用"后看"策略和嵌入不同程度非二元弧一致性的"前看"策略思想,提出一种非二元条件回溯算法和两种非二元条件前向检查算法,以有效处理约束维数的非二元性及变量依条件参与求解的动态性等问题;分析了三种算法最坏情况下的时间复杂性;通过随机生成的测试实例仿真实验比较了三种算法的求解性能。实验结果表明:在处理难问题时,两种非二元条件前向检查算法的性能均显著优于非二元条件回溯算法;而在分别处理中小规模低动态性特征与大规模高动态性特征问题时,两种非二元条件前向检查算法性能存在显著差异。

一种面向变量传播的弧一致性算法

在AC-3算法的基础上,提出了采用面向变量的约束传播机制新的弧一致性算法(Improved-AC3),算法(Improved-AC3)完全脱离附加的数据结构,使得程序的空间复杂度非常小,也避免了新算法在维护数据结构上的开销,是一种空间复杂度优先的通用弧一致性算法.新算法对于通用弧一致性算法的改进效果是明显的,是对现有弧一致性算法的提高和完善,使其实用性更好,应用前景更宽.

维持弧的唯一性优化粗粒度弧相容算法

针对人工智能领域中广泛应用的约束满足问题,本文分析了约束满足问题的粗粒度维持弧相容求解算法在弧相卷(arc corsistency,AC)执行过程中对于弧存在冗余的放回操作,并证明了这类放回是冗余的。同时提出一种改进方法 AC_AO,避免这类冗余的弧放回操作,从而保证了弧的唯一性。改进后框架可用于改进所有的粗粒度弧相容算法。实验结果表明,经过AC_AO改进后的算法最多可以少检查77%的弧,最多可以减少30%的CPU求解时间。这将大大减少修正函数的调用次数,从而提高AC的执行效率,应用在维持弧相容算法求解的过程中提高效率是非常有意义的。

基于变量传播的弧一致性算法

在AC-3算法的基础上,提出了采用面向变量的约束传播机制新的弧一致性算法(IAC3),算法(IAC3)引入了一个小型的附加数据结构,使得新算法的时间复杂度降低了一个幂次为O(ed2).以小的空间代价换取了显著时间效率.新算法对于通用弧一致性算法的改进效果是明显的,是对现有弧一致性算法的提高和完善,使其实用性更好,应用前景更宽.

基于动态度的回溯算法求解大值域约束满足问题

针对一个具有精确可满足性相变现象的大值域随机约束满足问题,提出了两种启发式动态回溯算法,即基于动态度的ddeg-MAC(dynamic degree-maintaining arc consistency)回溯算法和基于值域与动态度比值的dom/ddeg-MAC(dom/dynamic degree-maintaining arc consistency)回溯算法。这两种算法分别基于ddeg和dom/ddeg挑选变量,利用维持弧相容(MAC)技术为挑选的变量进行赋值。当赋值无法进行时,再执行动态回溯修正变量的赋值。数值实验结果表明:在控制参数非常接近理论相变点时,算法仍然能够有效地找到问题的解。与经典回溯算法相比,这两种启发式动态回溯算法具有显著的优越性。

基于帕累托优化的网络安全设备部署设计与研究

通过部署网络安全设备可以有效地提高网络的安全性,但由于网络设备种类繁多、功能复杂,如何在整个网络中最优地部署网络安全设备,从而达到安全和开销的平衡,仍是研究人员关注的焦点。将网络安全设备最优部署问题转换为帕累托优化问题,提出分布式约束优化的七元组对网络安全设备部署进行量化赋值,构建基于分支界限算法的部署方案搜索算法,在解空间内对量化的数值进行计算并求出最优解。由于基于分支界限算法的方案搜索算法需要耗费大量时间,在大型网络中运行效率较低,使用基于弧一致优化的数据预处理技术对量化数值进行预处理,实现搜索算法的优化。最后通过仿真实验测试,证明该方法的正确性和有效性。