圖匹配是衡量兩個圖之間相似性的過程,在模式識別,社交網絡,醫(yī)藥學等多個領域早已廣泛應用。近幾十年來,研究者們提出了大量解決圖匹配問題的算法。其中,圖編輯距離作為解決圖匹配問題最常用的方法已受到越來越多的關注。目前,對圖編輯距離問題的研究主要分為近似圖編輯距離和精確圖編輯距離,本文針對基于近似圖編輯距離的匹配算法進行研究。首先,介紹了與圖相關的基本知識,以及圖編輯距離的相關概念,并對相關算法及實現(xiàn)過程進行了簡要介紹。其次,分析SFBP（Square Fast Bipartite）代價矩陣在構建過程中存在精確度缺失的問題,提出一種新的代價矩陣。通過計算目標圖和源圖中任意兩個節(jié)點的添加、刪除之和,將其與SFBP代價矩陣中的相應節(jié)點進行替換,得到新的代價矩陣。再次,對基于新的代價矩陣進行求解的圖匹配算法進行改進并提出RC-Greedy算法。已有算法在使用貪婪策略選取分配節(jié)點的過程中,優(yōu)先從代價矩陣的行的角度去考慮節(jié)點的大小,沒有考慮節(jié)點在其所在列中的大小,存在精確度缺失問題。通過從列的角度獲取次優(yōu)分配節(jié)點,增加對比節(jié)點的數(shù)量,更加全面的考慮分配情況,從而得到更優(yōu)的分配結果。最后,基于GREYC... 

【文章來源】：燕山大學河北省

【文章頁數(shù)】：55 頁

【學位級別】：碩士

【文章目錄】：
摘要
ABSTRACT
第1章 緒論
    1.1 研究背景和意義
    1.2 國內外研究現(xiàn)狀
        1.2.1 圖匹配
        1.2.2 圖編輯距離
    1.3 本文研究內容
    1.4 論文結構
第2章 基礎知識概述
    2.1 圖的基本知識
    2.2 圖編輯距離的相關知識
        2.2.1 圖編輯操作
        2.2.2 圖編輯距離的定義
        2.2.3 圖編輯距離的代價函數(shù)
    2.3 基本算法
        2.3.1 子圖同構算法
        2.3.2 圖編輯距離算法
    2.4 本章小結
第3章 代價矩陣的改進
    3.1 引言
    3.2 SFBP代價矩陣分析
        3.2.1 基本代價矩陣
        3.2.2 SFBP代價矩陣的構建
        3.2.3 SFBP代價矩陣存在的問題
    3.3 N_SFBP代價矩陣
        3.3.1 針對SFBP代價矩陣的改進策略
        3.3.2 N_SFBP代價矩陣的構建算法
    3.4 本章小結
第4章 基于N_SFBP代價矩陣的近似圖匹配算法
    4.1 引言
    4.2 GLA算法分析
        4.2.1 GLA算法的求解過程
        4.2.2 GLA算法存在的問題
    4.3 RC-GREEDY算法
        4.3.1 定義RC-Greedy算法的代價函數(shù)
        4.3.2 針對GLA算法的改進策略
        4.3.3 對N_SFBP代價矩陣進行預處理
        4.3.4 RC-Greedy算法設計
    4.4 本章小結
第5章 實驗與結果分析
    5.1 引言
    5.2 實驗環(huán)境和數(shù)據集
    5.3 實驗評價指標
    5.4 實驗結果及分析
        5.4.1 SFBP和 N_SFBP代價矩陣性能比較
        5.4.2 GLA和 RC-Greedy算法性能比較
    5.5 本章小結
結論
參考文獻
攻讀碩士學位期間承擔的科研任務與主要成果
致謝


【參考文獻】：
期刊論文
[1]圖匹配技術研究[J]. 項英倬,譚菊仙,韓杰思,石浩.  計算機科學. 2018(06)
[2]圖編輯距離概述[J]. 徐周波,張鵾,寧黎華,古天龍.  計算機科學. 2018(04)
[3]大規(guī)模圖數(shù)據匹配技術綜述[J]. 于靜,劉燕兵,張宇,劉夢雅,譚建龍,郭莉.  計算機研究與發(fā)展. 2015(02)



本文編號：3165201