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

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

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