基于圖編輯距離的圖匹配算法研究.pdf

1、圖編輯距離在圖匹配中是一種靈活有效的方法,在圖模式識別及相關(guān)領(lǐng)域有多種用途,然而,它不同于其它圖匹配算法,圖編輯距離使得原圖的每個節(jié)點都可以與另一個圖的節(jié)點進(jìn)行匹配,這種特點使得圖編輯距離算法更適用于噪聲數(shù)據(jù),但在另一方面相對于簡單圖匹配模型它增加了計算復(fù)雜度。圖編輯距離的空間復(fù)雜度與所匹配的兩個圖的節(jié)點數(shù)目呈指數(shù)關(guān)系。這意味著對于大圖其編輯距離的計算是很困難的。
　　在本文中,構(gòu)造出了一種優(yōu)化的EGED(Exactgraphed

2、itdistance)算法,它利用貪心算法外加代價復(fù)雜度剪枝對EGED算法中的搜索樹進(jìn)行了剪枝,同時采用歐氏距離對代價函數(shù)進(jìn)行優(yōu)化。在實驗部分分別對改進(jìn)的EGED算法,原EGED算法和AGED(Approximategrapheditdistance)算法這三種算法的分類精確度和算法的運行時間進(jìn)行了效能測試。實驗結(jié)果證明,首先,本文構(gòu)造的EGED優(yōu)化算法相比于原EGED算法和AGED算法顯著提高了算法運行速度并降低了編輯操作的代價,使得