李安明，孫 偉，侯 宇，黃 森

（武漢科技大學(xué)機(jī)械自動(dòng)化學(xué)院，湖北 武漢430081）

1 引言

運(yùn)動(dòng)鏈的同構(gòu)判定是機(jī)構(gòu)創(chuàng)新、再生運(yùn)動(dòng)鏈必不可少的過(guò)程，不當(dāng)?shù)耐瑯?gòu)判定方法會(huì)導(dǎo)致有價(jià)值的新運(yùn)動(dòng)鏈的丟失或造成機(jī)構(gòu)類(lèi)別的重復(fù)。尋找一種既簡(jiǎn)便有效又便于計(jì)算機(jī)執(zhí)行的同構(gòu)判定方法，成為了當(dāng)下的一大難題。

國(guó)內(nèi)外很多學(xué)者花大量時(shí)間與精力進(jìn)行了研究。文獻(xiàn)［1］提出了“規(guī)范化”鄰接矩陣來(lái)判別不含復(fù)鉸的運(yùn)動(dòng)鏈。文獻(xiàn)［2］提出了全等環(huán)路法，通過(guò)比較環(huán)路構(gòu)件度來(lái)判定是否同構(gòu)：文獻(xiàn)［3］用改進(jìn)Haming數(shù)的方法來(lái)判定同構(gòu)：文獻(xiàn)［4］提出基于鄰接矩陣的特征值特征向量法實(shí)現(xiàn)不含復(fù)鉸運(yùn)動(dòng)鏈的同構(gòu)判定：文獻(xiàn)［5］利用素?cái)?shù)鄰接矩陣構(gòu)造了判定矩陣，通過(guò)解矢量得到同構(gòu)構(gòu)件標(biāo)號(hào)的映射關(guān)系，從而判定同構(gòu)：文獻(xiàn)［6］提出了改進(jìn)環(huán)連接方法，通過(guò)關(guān)節(jié)頻率、鏈識(shí)別串等結(jié)構(gòu)恒量來(lái)判定同構(gòu)。文獻(xiàn)［7］將神經(jīng)網(wǎng)絡(luò)引入同構(gòu)判定中：文獻(xiàn)［8］用改進(jìn)混合免疫法來(lái)判定同構(gòu)，提高了遺傳算法的效率：雖然它們各有優(yōu)點(diǎn)，但也存在缺陷。有的算法原理復(fù)雜，計(jì)算機(jī)化難以實(shí)現(xiàn)，有的準(zhǔn)確性低、失效率高，尤其對(duì)于對(duì)稱(chēng)性高的運(yùn)動(dòng)鏈難以準(zhǔn)確判定。

提出了一種計(jì)算簡(jiǎn)便，準(zhǔn)確性高的同構(gòu)判定方法，對(duì)于對(duì)稱(chēng)性較高的運(yùn)動(dòng)鏈仍然有效。用特征碼表示運(yùn)動(dòng)鏈的基本特征，作為判定的必要條件。為區(qū)分復(fù)鉸、普通鉸且便于求最短距離矩陣，提出了改進(jìn)鄰接矩陣。然后利用鄰接矩陣構(gòu)造了最短距離矩陣作為判定矩陣。由運(yùn)動(dòng)鏈的特征碼、最短距離矩陣的和列陣及特征值特征向量來(lái)判定運(yùn)動(dòng)鏈?zhǔn)欠裢瑯?gòu)。

2 最短距離矩陣

如圖1（b）所示，為10桿含復(fù)鉸運(yùn)動(dòng)鏈a1對(duì)應(yīng)的雙色拓?fù)鋱D［9］。圖中黑色節(jié)點(diǎn)對(duì)應(yīng)運(yùn)動(dòng)鏈中的構(gòu)件，白色節(jié)點(diǎn)與其所連線(xiàn)段的組合對(duì)應(yīng)運(yùn)動(dòng)鏈中的復(fù)合鉸，其余線(xiàn)段則表示運(yùn)動(dòng)鏈的普通較。為區(qū)分普通鉸和復(fù)合鉸，令拓?fù)鋱D中任意兩相連黑色節(jié)點(diǎn)間的距離為1，任意兩黑白相連的節(jié)點(diǎn)間距離為0.55。此時(shí)，拓?fù)鋱D中任意兩個(gè)黑色節(jié)點(diǎn)間最短距離的整數(shù)部分，表示運(yùn)動(dòng)鏈中兩構(gòu)件之間最短路徑所經(jīng)過(guò)的關(guān)節(jié)個(gè)數(shù)，若存在小數(shù)則表明該路徑中存在復(fù)合鉸。

圖1 運(yùn)動(dòng)鏈a1結(jié)構(gòu)簡(jiǎn)圖及其雙色拓?fù)鋱DFig.1 Structural Sketch and Topological Graph of Kinematic Chain a1

為了區(qū)別復(fù)鉸并反映拓?fù)鋱D中相鄰兩黑色節(jié)點(diǎn)間的距離關(guān)系，提出了一種改進(jìn)鄰接矩陣來(lái)描述含復(fù)鉸的運(yùn)動(dòng)鏈，用A表示。改進(jìn)鄰接矩陣中若構(gòu)件與構(gòu)件通過(guò)普通鉸相連，則元素為1，不相連元素為∞。若通過(guò)復(fù)合鉸相連，則元素為1.1，并且對(duì)角線(xiàn)元素為0。運(yùn)動(dòng)鏈a1的改進(jìn)鄰接矩陣為Aa1。

定義1：矩陣中任一元素表示拓?fù)鋱D任意兩節(jié)點(diǎn)之間最短路徑距離值的矩陣稱(chēng)為最短距離矩陣，用D表示。

采用“插點(diǎn)法”求最短距離矩陣，依次構(gòu)造出n個(gè)矩陣D(0)、使最后得到矩陣為最短距離矩陣。最短距離矩陣更新原理如下：

n是最短距離矩陣。

綜上所述，求最短距離矩陣的算法流程可總結(jié)如下：

第一步：賦初值，把矩陣A賦值給初始最短距離矩陣D。

第二步：更新最短距離矩陣D(i,j)，

第三步：若k=n，則停止，否則k=k+1，轉(zhuǎn)第二步。

求得運(yùn)動(dòng)鏈a1拓?fù)鋱D對(duì)應(yīng)的最短距離矩陣為Da1。

其中，Da1()3,7=2.2在拓?fù)鋱D中表示由節(jié)點(diǎn)3到節(jié)點(diǎn)7的最短距離為2.2，在運(yùn)動(dòng)鏈中表示由構(gòu)件3到構(gòu)件7至少需要經(jīng)過(guò)兩個(gè)關(guān)節(jié)，并存在復(fù)合鉸：右側(cè)為距離之和，表示拓?fù)鋱D中任意一點(diǎn)到其余所有點(diǎn)的最短距離之和，記為和列陣Sa1。

3 同構(gòu)判定

由圖論相關(guān)理論及同構(gòu)的概念可知，要使兩運(yùn)動(dòng)鏈同構(gòu)，必須含有相同的構(gòu)件種類(lèi)、構(gòu)件數(shù)量、構(gòu)件連接關(guān)系。對(duì)于構(gòu)件之間的連接關(guān)系已由最短距離矩陣得出，而對(duì)于構(gòu)件種類(lèi)、構(gòu)件數(shù)量用特征碼表示。

定義2：表示運(yùn)動(dòng)鏈構(gòu)件種類(lèi)及數(shù)量的代碼稱(chēng)為特征碼，用M表示。

式中：nu-含有u元構(gòu)件的數(shù)量。例如，Ma1=[7,2,1]表示含有7個(gè)二元桿、2個(gè)三元桿、1個(gè)四元桿。運(yùn)動(dòng)鏈同構(gòu)判定流程，如圖2所示。

圖2 同構(gòu)判定流程圖Fig.2 Isomorphism Identification Flow Chart.

如圖3所示，為兩個(gè)含復(fù)鉸的10桿運(yùn)動(dòng)鏈，運(yùn)動(dòng)鏈a1、a2與a3的特征碼為Ma1=Ma2=Ma3=[ ]7,2,1，即三個(gè)運(yùn)動(dòng)鏈具有相同的構(gòu)件類(lèi)型和數(shù)量?？汕蟮米疃叹嚯x矩陣為Da2和Da3。

圖3 運(yùn)動(dòng)鏈a2與a3結(jié)構(gòu)簡(jiǎn)圖Fig.3 Structural Sketch of Kinematic Chain a2 and a3

表1 運(yùn)動(dòng)鏈、最短距離矩陣特征值及特征向量Tab.1 Eigenvalues and Eigenvectors of the Shortest Distance Matrices of Chain and

4 案例分析

案例1：如圖4所示，為兩個(gè)含復(fù)鉸13桿運(yùn)動(dòng)鏈結(jié)構(gòu)簡(jiǎn)圖，其特征碼Mb1=Mb2=[3,8]?？汕蟮米疃叹嚯x矩陣為Db1和Db2。

圖4 運(yùn)動(dòng)鏈b1與b2Fig.4 Kinematic Chainb1andb2

圖5 運(yùn)動(dòng)鏈c1與c2Fig.5 Kinematic Chainc1andc2

表2 運(yùn)動(dòng)鏈、最短距離矩陣特征值及特征向量Tab.2 Eigenvalues and Eigenvectors of the Shortest Distance Matrices of Chain and

5 結(jié)論

提出了一種含復(fù)鉸運(yùn)動(dòng)鏈描述和判定的新方法，并給出了通過(guò)改進(jìn)鄰接矩陣求解最短距離矩陣的算法。通過(guò)比較運(yùn)動(dòng)鏈的特征碼、最短距離矩陣的和列陣、最短距離矩陣的特征值特征向量是否相等來(lái)判定同構(gòu)。案例證明了此方法的正確性與高效性。相比其它同構(gòu)判定法，計(jì)算既簡(jiǎn)便又有效。并且對(duì)于對(duì)稱(chēng)性較高的運(yùn)動(dòng)鏈，此方法依然有效。