最小顶点覆盖问题的竞争决策算法

竞争决策算法是在分析大自然生物世界特别是人类的各种竞争机制和决策原理的基础上,利用竞争造就优化、决策左右结果的特性来达到优化目的的新型寻优算法。采用竞争决策算法原理,利用竞争决策算法的通用模型,求解图的最小顶点覆盖问题。     

最大团问题的加权分治算法

分支降阶是目前广泛用于求解组合优化领域中难题的技术之一,该技术的核心思想是将原问题分支成若干个子问题,并递归求解这些子问题。加权分治技术是算法设计和时间复杂度分析中的一种新技术。设计一个基于分支降阶的递归算法求解最大团问题。运用常规技术对该算法进行时间复杂度分析,得出其时间复杂度为[O(1.380np(n)),]其中[p(n)]表示问题规模数[n]的多项式函数。运用加权分治技术对原算法进行时间复杂度分析,将该算法的时间复杂度由原来的[O(1.380np(n))]降为[O(1.325np(n))]。研究结果表明运用加权分治技术能够得到较为精确的时间复杂度。     

加权分治与皇冠技术求解最大加权独立集

皇冠分解技术是一种算法优化技术,通过找出一个称为皇冠的特殊非空独立集,并将该独立集和它的邻接集合删除,得到一个不含皇冠的子图,从而降低原问题规模,降低算法时间复杂度。针对加权图的独立集问题相关性质设计了精确算法来找出一个权值之和最大的加权独立集。首先构造了一个二分图,并通过该图找出皇冠结构,采用皇冠分解技术分解图,针对无皇冠的子图设计了一个分支降阶递归算法,然后利用加权分治技术对算法时间复杂度进行分析,最终得到一个优于常规时间复杂度的精确算法。     

量子竞争决策算法及其在旅行商问题中的应用*

提出一种新型优化算法——量子竞争决策算法,在竞争决策的基础上,将进化博弈论中博弈者不断学习和调整来提高竞争力的思想引入到优化中,使竞争者具有自进化能力,同时充分利用量子进化计算中量子比特、叠加态等理论,增加竞争群体的多样性,缩小群体规模。通过对典型的TSP实验计算和与其他算法比较,均取得了较好的效果,算法具有较强的全局优化能力。     

图的Steiner最小树问题的降阶回溯算法

图的Steiner最小树问题是经典的组合优化问题,是一个NP难题,在不同的领域有着广泛的应用。研究该问题的部分数学性质,在此基础上给出了该问题的初步降阶方法和下界子方法,形成一个新的回溯算法。该算法具有较低的时间复杂度,还给出了应用实例及其分析。     

基于Web服务的大数据访问性能优化研究

Web服务特别适合于Internet下进行数据通信,已成为企业实现跨Internet的分布式异构系统集成和数据共享的主流解决方案。然而,基于XML的SOAP消息会将数据膨胀而增加系统传输开销,当访问大数据时问题则更为严重,会显著降低Web服务的性能。通过对Web服务调用模型进行分析以及结合作者实践开发经验,采用分页检索、格式化为二进制流、透明压缩等技术并分析各种技术的适用场合,同时采用MTOM协议重新封装SOAP消息,经实践检验证明,大大提高了Web服务的大数据访问性能。     

带惩罚的无容量设施选址问题的降阶回溯算法

无容量设施选址问题（Uncapacitated Facility Location Problem,UFLP）是组合优化中经典的NP-Hard问题之一。针对UFLP的变形问题之一,即带惩罚的无容量设施选址问题（Uncapacitated Facility Location Problem With Penalties,UFLPWP）,研究了UFLPWP的数学性质,其中包括可以批量确定某些设施一定关闭的性质,并进行了数学证明,利用这些数学性质可以对问题进行降阶,进而缩小问题的规模。在此基础上设计了基于上、下界的回溯算法来求解UFLPWP。通过一个示例分析,进一步阐述该算法的原理。     

具有偏好选择的多目标TSP竞争决策算法

多目标旅行商问题中各个日标的重要程度对不同用户足不同的。为了满足不同用户对各个目标的不同偏好并快速地提供满足用户偏好的TSP回路，利用竞争决策算法(一种能广泛应用于组合优化问题的新型算法)的通用模型，给出了一种基于竞争决策思想的快速求解方法。经过数据测试和验证，该法得到了较好的结果。     

最小生成树灵敏度分析算法研究

在最小生成树数学性质的基础上,给出最小生成树灵敏度分析算法.该算法在图的各种属性发生变化(如边的权值变化、增加或删除边或结点)的情况下,在原有最小生成树的基础上快速调整,而不是从头计算来得到新的最优解.算法还给出了每边权值在何范围内变化时,最优解不变.最后通过一个示例来说明算法的原理及应用.