二次分配问题的骨架分析与算法设计

骨架分析是近年来NP-难解问题研究的热点，对于衡量问题的相变、难度及算法设计具有重要意义．骨架的理论分析及在算法设计方面的应用还处于起步阶段，从QAP问题入手，对QAP骨架进行了理论分析，证明寻找QAP问题的骨架属于NP．难解问题，不存在多项式时间的算法可以保证得到QAP问题的骨架，为局部最优解交叉来获得近似骨架提供了合理性解释，在此基础上，利用偏移实例构造方法，提出了基于偏移实例的近似骨架算法．其基本思想是：首先为QAP实例构造偏移实例，其最优解恰是原QAP实例的一个全局最优解；然后利用现有算法求得新实例的多个局部最优解，通过对局部最优解求交得到近似骨架；将近似骨架固定以得到规模更小的搜索空间，最后在新空间上求解，拓广了骨架理论研究的范围，所提出的算法为NP-难解问题的通用算法设计提供了一种新思路。     

图的二分问题唯一全局最优解实例与骨架计算复杂性

骨架分析是近年来理论计算机科学研究的热点, 对于NP-难解问题的启发式算法设计具有重要意义. 由于骨架计算复杂性研究十分困难, 现有的骨架分析方法多采用实验统计手段. 针对现有方法中存在的骨架规模小的缺陷, 给出图的二分问题GBP(graph bi-partitioning problem)的唯一全局最优解实例构造算法, 有效提高了骨架的规模. 同时, 利用该算法从理论上证明了寻找GBP问题的完整骨架属于NP-难解问题, 即在P≠NP的假设下, 不存在多项式时间的算法可以确保得到GBP问题的完整骨架. 本文的工作拓广了骨架计算复杂性研究的范围, 所提出的唯一全局最优解实例构造算法对于NP-难解问题启发式算法设计亦具有较高的参考价值.     

求解TSP问题的并集搜索的新宏启发算法

利用TSP问题解的概率统计模型，分析了TSP问题的局部最优解并集的性质，发现局部最优解的并集规模较小且包含了绝大多数全局最优解的边．利用该性质，将局部最优解并集作为启发集，并调用局部搜索算子在其上求解TSP问题，由此得到一种称为并集搜索的新宏启发算法．利用该算法还改进了目前广泛使用的求解TSP问题的算法ILK、LKH，在TSPLIB中典型实例上的实验结果表明，新算法在解的质量上有了较显著的提高．     

TSP问题启发集的分析及应用

建立了描述TSP问题启发集性质的概率模型,并指出了改进启发集的一般方法.进一步,利用局部最优解交集作为近似骨架,提出了一种动态改进启发集的宏启发算法--自适应可变启发集搜索.并将自适应可变启发集搜索与目前广泛使用的算法ILK、LKH相结合,TSPLIB中典型实例上的实验结果表明,改进后的算法在求解质量上有了较大的改进.