面向參數計算的隨機技術研究

《面向參數計算的隨機技術研究》是依託中南大學，由馮啟龍擔任項目負責人的面上項目。

基本介紹

• 中文名：面向參數計算的隨機技術研究
• 項目類別：面上項目
• 項目負責人：馮啟龍
• 依託單位：中南大學

項目摘要

作為有效求解難解問題的手段，隨機方法近年來在參數計算領域受到了人們的關注。許多難解問題基於隨機方法都得到有效求解，但隨機方法在參數計算領域各個方面的研究正處於起步階段，都待進一步發展和完善。 本項目將研究面向參數計算領域的隨機技術。首先研究基於問題解空間特性的隨機技術，基於問題基本操作的隨機技術和基於隨機方法的核心化分析技術；然後研究傳統算法技術與隨機方法在參數計算領域的綜合套用；最後研究參數計算隨機方法確定化方法。本項目的研究旨在建立求解各類難解問題的相應隨機技術，為套用領域中的難解問題求解提供新的思路，繼而推動相應領域的發展。

結題摘要

在本基金的資助下，課題組針對P2-Packing、k-means聚類、最大可滿足性等一系列經典難解問題的參數算法、隨機算法、核心化算法以及近似算法展開研究，並在資源調度和生物信息等領域得到有效套用。主要成果如下：1. 深入分析難解問題解空間結構，基於操作的隨機處理與參數計算的隨機分析，提出了P2-Packing、加權P3-Packing以及Co-Path Set等問題的隨機參數算法。提出了關於受限k-means聚類問題運行時間最短的(1+ε)-近似算法；2. 研究難解問題的核心化算法。改進了最大內部節點生成樹、最大對分、最大環-Packing等一系列經典難解問題的最好核心化結果；分析局部簡化技術，並運用此技術提出了關於Co-Path Set、G7圖上的支配集和路徑收縮等問題的核心化算法；3. 研究影響難解問題的關鍵參數，提出了近似森林刪除、簇圖修改、子圖同構等一些經典圖修改問題以及可滿足性問題的改進參數算法；為系譜比較與系統發生樹等生物信息學領域中的常用工具建立參數模型，並給出有效的參數算法；4. 提出了近似森林刪除、最大內部節點生成樹以及一些調度問題的近似算法。