《基於電路模擬的大規模圖同構判定算法研究》是依託復旦大學，由商慧亮擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：基於電路模擬的大規模圖同構判定算法研究
- 依託單位：復旦大學
- 項目類別：青年科學基金項目
- 項目負責人：商慧亮
項目摘要,結題摘要,
項目摘要
圖的同構判定是圖論學科中的基本問題之一，對模式識別、有機化學、機械學及電路分析等領域的系統建模具有重要作用。本項目擬在本課題組提出的電路模擬法基礎上，依據電路理論，針對圖同構判定問題中較難的對稱圖同構判定問題展開研究，分析對稱圖的分支特徵，擬建立基於分支搜尋的改進電路模擬法模型，設計對稱圖和非對稱圖都能適用的具有較好普適性的圖同構判定算法；擬採用稀疏矩陣技術對電路模擬法判定程式加以最佳化，進一步提高算法的判定效率和所能判定的圖的規模。針對一些特殊類型的圖，例如非連通圖，擬建立基於子圖劃分的改進電路模擬法模型，設計相應的最佳化算法。期望通過該項目的研究，得到一種普適的面向一般圖的同構判定算法，為相關領域的套用研究提供更為高效的方法和科學的依據。
結題摘要
圖的同構判定是圖論學科中的基本問題之一，對模式識別、有機化學、機械學及電路分析等領域的系統建模具有重要作用。對國內外已有的同構判定算法進行研究，我們發現現有同構判定算法的一個突出問題是會對特定種類的圖失效，出現指數級的計算複雜度，尤其是對於對稱圖的判定效率較低。因此，探索適用範圍更為廣泛，效率更高的圖的同構判定算法非常值得研究。 本項目在本課題組提出的電路模擬法基礎上,依據電路理論，針對圖同構判定問題中較難的對稱圖同構判定問題展開研究,分析對稱圖的分支特徵，建立了基於分支搜尋的改進電路模擬法模型，設計了對稱圖和非對稱圖都能適用的具有較好普適性的圖同構判定算法；採用稀疏矩陣技術對電路模擬法判定程式加以最佳化，進一步提高了算法的判定效率和所能判定的圖的規模。針對一些特殊類型的圖，例如非連通圖，建立了基於子圖劃分的改進電路模擬法模型，設計了相應的最佳化算法。基於稀疏矩陣技術對算法進行最佳化，進一步降低了判定算法的計算量，使算法對非對稱圖的同構判定計算複雜度降低了1個數量級。通過對電路模型的改進和激勵方法的最佳化調整，進一步將算法對非對稱圖的同構判定計算複雜度降為O(n^2) （n為待判定圖頂點數）。通過該項目的研究，得到了一種普適的面向一般圖的同構判定算法，為相關領域的套用研究提供了更為高效的方法和科學的依據。 基於理論研究成果，運用電路模擬法對化學分子同分異構判別問題展開研究，給出相應的判別算法。對分子資料庫（PubChem）進行實測研究，並與現有算法進行比對，測試結果證實電路模擬法很好地解決了高度對稱分子結構比對的問題。運用電路模擬法對運動鏈的同構判別問題展開深入研究，研究其轉化模型的構建方法，將運動鏈轉化為相應的拓撲圖，然後用本項目的判定方法加以判別，該方法效果大大優於特徵向量法。加強了和中醫信息領域的合作研究，包括四診舌像分析、知識圖譜研究、智慧型醫療等工作，為相關基礎研究工作的行業套用拓展了思路。
