摘要：針對(duì)計(jì)算機(jī)圖數(shù)據(jù)處理難題中的圖數(shù)據(jù)檢索匹配問(wèn)題。相比傳統(tǒng)的基于統(tǒng)計(jì)分布、模式識(shí)別等理論，該文在研究了遺傳算法的智能優(yōu)化過(guò)程的基礎(chǔ)上，對(duì)照?qǐng)D匹配過(guò)程中的對(duì)應(yīng)信息元素的查找難題進(jìn)行求解。將遺傳算法的思想理論與圖匹配方法相結(jié)合，利用智能優(yōu)化算法對(duì)解決基于內(nèi)容的圖匹配問(wèn)題探索提供新的解決方法，從智能優(yōu)化的角度來(lái)考慮和快速解決圖匹配過(guò)程中的結(jié)構(gòu)對(duì)應(yīng)檢索難點(diǎn)。通過(guò)驗(yàn)證參數(shù)和對(duì)象得出圖匹配問(wèn)題新解。

關(guān)鍵詞：圖檢索；圖匹配；遺傳算法；圖數(shù)據(jù)

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2013）01-0088-04

1 概述

信息技術(shù)地不斷發(fā)展出現(xiàn)了越來(lái)越多的以圖作為邏輯表達(dá)的數(shù)據(jù)，例如城市規(guī)劃中的建筑模型、化學(xué)分子結(jié)構(gòu)式，生物網(wǎng)絡(luò)，社會(huì)網(wǎng)絡(luò)圖中的實(shí)體關(guān)系和圖像檢索等等。從圖數(shù)據(jù)中發(fā)現(xiàn)有用的知識(shí)已成為圖數(shù)據(jù)查詢領(lǐng)域一項(xiàng)重要的研究課題。圖查詢是其中最重要的一個(gè)研究分支，因?yàn)榕c圖有關(guān)的絕大部分應(yīng)用（例如：圖查詢、圖分類、圖聚類等）都需要利用圖來(lái)管理、查詢和分析圖數(shù)據(jù)。

對(duì)于在大量累積的圖數(shù)據(jù)（即圖數(shù)據(jù)庫(kù)）上進(jìn)行查詢處理的問(wèn)題，已有的對(duì)圖數(shù)據(jù)庫(kù)查詢處理的研究工作主要包括兩大類：一類是在小尺寸圖的大規(guī)模集合（簡(jiǎn)稱為集合類圖數(shù)據(jù)庫(kù)）上處理查詢，其中包括子圖查詢處理、超圖查詢處理和相關(guān)子圖查詢處理等；一類是在一個(gè)或?yàn)閿?shù)不多的大尺寸圖（簡(jiǎn)稱為大圖類圖數(shù)據(jù)庫(kù)）上處理查詢，如子圖匹配查詢處理、可達(dá)查詢和最短路徑/距離查詢等。然而，這些方法全部針對(duì)確定圖數(shù)據(jù)，無(wú)法應(yīng)用到不確定圖數(shù)據(jù)的查詢處理中。對(duì)不確定圖數(shù)據(jù)庫(kù)中多種查詢類型（如子圖匹配查詢）的高效處理是一項(xiàng)具有挑戰(zhàn)性的工作.因此對(duì)圖數(shù)據(jù)的查詢處理方法的研究具有現(xiàn)實(shí)意義和理論價(jià)值，有待探索.

雖然遺傳算法是非常優(yōu)秀的智能優(yōu)化算法，但是目前大多數(shù)應(yīng)用都可以歸納為解決路徑問(wèn)題，比如TSP問(wèn)題，而將其與計(jì)算機(jī)數(shù)據(jù)的圖數(shù)據(jù)匹配的研究還很少[6]。

本文針對(duì)不同的拓?fù)浣Y(jié)構(gòu)圖，對(duì)兩個(gè)圖是否相似的過(guò)程采用遺傳算法進(jìn)行討論，對(duì)于種群進(jìn)化的過(guò)程思路進(jìn)行拓展研究，在算法復(fù)雜度上對(duì)比現(xiàn)有的深度優(yōu)先搜索、寬度優(yōu)先搜索等算法得出遺傳算法應(yīng)用于圖匹配問(wèn)題的新解。

2 問(wèn)題的定義

用圖表示多邊形，即用圖的節(jié)點(diǎn)表示多邊形的頂點(diǎn)，用圖的邊表示多邊形的邊，則多邊形的匹配問(wèn)題就可以用如與圖的匹配來(lái)解決。

圖匹配過(guò)程通常完成若干遍圖查詢的操作，圖匹配問(wèn)題要求判斷兩個(gè)圖是否相同或相似，并對(duì)兩圖的相似程度進(jìn)行度量，返回圖之間的相似度值。一般說(shuō)來(lái)，圖匹配可以認(rèn)為是基于模板的匹配，可定義如下：對(duì)于給定的圖，從模式集中找出一個(gè)最為相似的圖作為給定圖的相似圖。圖匹配方法要求對(duì)于平移、旋轉(zhuǎn)、比例改變等幾何變換具有不變性；兩圖的相似程度應(yīng)該是可度量且易于計(jì)算的，根據(jù)匹配算法得出的判斷應(yīng)與人的直覺(jué)相吻合。在本文中所涉及的圖都是無(wú)向標(biāo)號(hào)圖。