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

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

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

【學位級別】：碩士

【文章目錄】：
摘要
ABSTRACT
第1章 緒論
    1.1 研究背景和意義
    1.2 國內(nèi)外研究現(xiàn)狀
        1.2.1 圖匹配
        1.2.2 圖編輯距離
    1.3 本文研究內(nèi)容
    1.4 論文結(jié)構(gòu)
第2章 基礎(chǔ)知識概述
    2.1 圖的基本知識
    2.2 圖編輯距離的相關(guān)知識
        2.2.1 圖編輯操作
        2.2.2 圖編輯距離的定義
        2.2.3 圖編輯距離的代價函數(shù)
    2.3 基本算法
        2.3.1 子圖同構(gòu)算法
        2.3.2 圖編輯距離算法
    2.4 本章小結(jié)
第3章 代價矩陣的改進
    3.1 引言
    3.2 SFBP代價矩陣分析
        3.2.1 基本代價矩陣
        3.2.2 SFBP代價矩陣的構(gòu)建
        3.2.3 SFBP代價矩陣存在的問題
    3.3 N_SFBP代價矩陣
        3.3.1 針對SFBP代價矩陣的改進策略
        3.3.2 N_SFBP代價矩陣的構(gòu)建算法
    3.4 本章小結(jié)
第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算法設(shè)計
    4.4 本章小結(jié)
第5章 實驗與結(jié)果分析
    5.1 引言
    5.2 實驗環(huán)境和數(shù)據(jù)集
    5.3 實驗評價指標
    5.4 實驗結(jié)果及分析
        5.4.1 SFBP和 N_SFBP代價矩陣性能比較
        5.4.2 GLA和 RC-Greedy算法性能比較
    5.5 本章小結(jié)
結(jié)論
參考文獻
攻讀碩士學位期間承擔的科研任務與主要成果
致謝


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



本文編號：3165201