摘要：最大可满足性问题(MAXSAT)是经典的np完全问题SAT的一个扩展问题.基于分支限界设计MAXSAT完备算法时,如何有效地提高下界是设计高效算法的关键和难点.基于优先找到规模小、结构简单的冲突集的思想,在Maxsatz算法的基础上,提出了改进的算法Maxsatz2013.通过使用推理规则优先、改变单子句的传播顺序、进一步失败文字检测这3个优化策略,增加了检测到的冲突集数,从而有效地提高了下界.测试了MAXSAT 4个类别共800多个算例.实验结果表明,这3个优化冲突集的策略是可行且有效的,所提出的算法在每一类算例上均明显地提高了计算效率.

摘要：针对多约束服务质量路由问题,提出了一种基于K最短路径路由选择算法QRBKP。该算法首先计算针对各约束度量参数的K最短路径,然后在所有的最短路径中选择满足多约束的QoS路由,其中最短路径数k根据各QoS约束自适应变化。基于此,本文提出了节点对之间的路由空间再分配技术和节点对内部的路由空间再分配技术,确保总的路由表空间不会超过设计路由空间。理论分析表明,QRBKP不仅能够解决加性度量参数受约束的QoS路由问题,而且能够解决加性与非加性度量参数混合受约束QoS路由问题。仿真结果表明:在求解QoS路由问题时,在相同的计算次数下,QRBKP算法比同类算法具有更高的路由计算成功率。

摘要：点覆盖问题是最重要的np完全问题之一,也是近年来参数算法设计中研究得最多的问题之一。针对现有点覆盖近似算法的一些不足,基于点覆盖问题参数算法的进展,提出了该问题一个基于NT定理规约的2-近似算法。利用了参数算法中的核化技术对图进行化简,在剩余图上采用贪心策略来指导节点的选择,核化技术为算法提供了有效的近似度保障。为检验新算法性能,在不同类型的随机图上通过仿真实验比较了新算法和经典的基于匹配的2-近似算法。仿真实验结果表明新算法较基于匹配的2-近似算法有着明显的优势。

摘要：在赋权图中,求任意给定两点之间的最优(边权值之和最小)Hamilton路问题,简称OHP问题,是计算机领域的一个经典算法问题,它在网络路由选择和计算机的许多领域都有广泛应用。该问题是np完全的。Halin图是对树和环网络的非平凡概括,因此求赋权Halin图的OHP问题是非常有意义的。但当前仍没找到该问题的有效算法。本文通过递归压缩Halin图中的扇,设计了一个求解赋权Halin图OHP的有效算法,并给出算法的正确性证明和复杂度分析。

摘要：参数计算和复杂性是上世纪末本世纪初兴起的一门技术。该技术因具有坚实的理论基础和良好的运行效果,故仅经过短短十几年的发展,已经取得了大量的成就。从趋势上看来,参数计算已经成为理论计算机科学中越来越热门的一个分支。先简要介绍参数计算和复杂性的重要理论基础和主要思想;之后重点介绍参数计算中使用的主要技术,分析每一种技术的功能作用、基本设计原则和优缺点,并结合简单案例加以说明。

摘要：针对团图点删除问题的3-近似算法得到的近似解可能较大的问题,通过对团图点删除问题及团图特性的分析,提出了该问题的一个新的近似算法。新算法通过考察图中节点的一阶和二阶邻点来计算节点关联的P3的数目,然后优先选择P3数最大的节点加入解集,以期尽快消除图中的P3,从而最终获得较小的点删除集。为检验算法效果,设计了多组不同场景的随机实验对新算法和经典的3-近似算法进行了比较。随机实验表明,新算法较经典的3-近似算法有明显的优势。

摘要：矩形packing问题有许多工业应用,如码头货物装载,木材下料,超大规模集成电路(VLSI)布局设计,新闻排版等。国内外已提出了许多求解此问题的算法,如:遗传算法,模拟退火算法以及启发式算法等。在目前已有研究的基础上,提出了一种智能枚举算法,该算法的关键在于设计一种快速有效的枚举策略。用Hopper和Turton提出的21个矩形packing实例对所提出的算法性能进行了实算测试,平均面积未利用率为0.04%,平均计算时间为277.69 s,并求得了其中18个实例的最优解。实算结果表明:该算法对求解矩形packing问题是行之有效的。

摘要：该研究为Hamilton环路(道路)问题设计出了一个多项式时间算法,论证了它的正确性。根据该算法编制了程序,进行了大量的实例计算。文章公布了主要研究方法、过程、实验数据,以及粗略的算法步骤。详细的算法步骤和证明将在随后的论文中发表。由于Hamilton环路(道路)为著名的np完全问题,而作者认为自己已彻底解决了np复杂问题。

摘要：TSP问题是一类经典的np完全组合优化问题，传统的优化方法由于计算复杂性过大而难以求得全局最优解，遗传算法等智能优化算法在求解这类组合优化问题中表现出了强劲的潜力．作者利用遗传算法对TSP问题进行了研究分析，针对几组benchmark数据进行了仿真实验，在实验的基础上探索了遗传算子和遗传参数的优化设计，实验结果证明了遗传算法在解决TSP问题上的可行性和有效性。