《啟發式算法設計中的骨架分析與套用》是依託大連理工大學,由江賀擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：啟發式算法設計中的骨架分析與套用
- 依託單位：大連理工大學
- 項目類別：青年科學基金項目
- 項目負責人：江賀
- 批准號：60805024
- 申請代碼：F0601
- 負責人職稱：教授
- 研究期限：2009-01-01 至 2011-12-31
- 支持經費：19（萬元）
項目摘要
骨架是描述NP-難解問題特徵的強有力手段。基於骨架的啟發式算法具有簡單靈活、易於實現、性能提升顯著等的優點。故此，骨架成為啟發式算法研究的前沿熱點。.目前骨架研究還存在眾多亟待解決的問題：在理論上缺少計算複雜性分析成果，在套用中難以高效逼近骨架、難以應對小規模骨架實例。針對上述問題，本課題圍繞骨架研究的各層面進行探索：（1）理論基礎：骨架的多尺度計算複雜性分析，分析典型NP-難解問題的完整骨架和部分骨架的計算複雜性；（2）套用基礎：骨架的高效逼近，通過多種不同途徑來近似全局最優解以獲取高純度近似骨架；（3）骨架套用：小規模骨架實例的啟發式算法設計，通過提高骨架規模以提升基於骨架的啟發式算法性能。.課題的成功實施，有望顯著提高基於骨架的啟發式算法的性能，拓展計算複雜性理論的研究範疇，從而有力提升我國在該前沿領域的研究水平和影響力。
