启发式算法设计中的骨架分析与应用

骨架是描述NP-难解问题特征的强有力手段。基于骨架的启发式算法具有简单灵活、易于实现、性能提升显著等的优点。故此，骨架成为启发式算法研究的前沿热点。.目前骨架研究还存在众多亟待解决的问题：在理论上缺少计算复杂性分析成果，在应用中难以高效逼近骨架、难以应对小规模骨架实例。针对上述问题，本课题围绕骨架研究的各层面进行探索：1）理论基础：骨架的多尺度计算复杂性分析，分析典型NP-难解问题的完整骨架和部分骨架的计算复杂性；2）应用基础：骨架的高效逼近，通过多种不同途径来近似全局最优解以获取高纯度近似骨架；3）骨架应用：小规模骨架实例的启发式算法设计，通过提高骨架规模以提升基于骨架的启发式算法性能。.课题的成功实施，有望显著提高基于骨架的启发式算法的性能，拓展计算复杂性理论的研究范畴，从而有力提升我国在该前沿领域的研究水平和影响力。