[發(fā)明專利]一種基于商空間覆蓋模型的最短路徑搜索方法

無效

• 申請?zhí)枺?/td>: 200810021103.0
• 申請日: 2008-07-24
• 公開（公告）號: CN101330457A
• 公開（公告）日: 2008-12-24
• 發(fā)明（設計）人: 何富貴;張燕平;張鈴;趙姝
• 申請（專利權(quán)）人: 安徽大學
• 主分類號: H04L12/56
• 分類號: H04L12/56;G08G1/00
• 代理公司: 安徽省合肥新安專利代理有限責任公司
• 代理人: 汪祥虬

1.一種基于商空間覆蓋模型的最短路徑搜索方法，首先對初始網(wǎng)絡中的節(jié)點按照一定的順序標號，根據(jù)無向無權(quán)網(wǎng)絡極大完全子圖的特征形成遞階商空間覆蓋網(wǎng)絡鏈；其特征在于：從無向無權(quán)連通網(wǎng)絡中作為粒度最細、第0級商空間覆蓋網(wǎng)絡的初始網(wǎng)絡開始，搜索網(wǎng)絡中所有的極大完全子圖，以極大完全子圖為節(jié)點，兩極大完全子圖的節(jié)點間有公共節(jié)點或邊，定義兩節(jié)點相連，得到粒度較粗的商空間覆蓋，為初始網(wǎng)絡的一級商空間覆蓋網(wǎng)絡；然后再求初始網(wǎng)絡的一級商空間覆蓋網(wǎng)絡的所有極大完全子圖，并記錄極大完全子圖對應于初始網(wǎng)絡中的節(jié)點信息，以該級的極大完全子圖為節(jié)點、兩極大完全子圖的節(jié)點間有公共節(jié)點或邊定義為兩節(jié)點相連，得到粒度較粗的商空間覆蓋，構(gòu)成初始網(wǎng)絡的二級商空間覆蓋網(wǎng)絡，求初始網(wǎng)絡的二級商空間覆蓋網(wǎng)絡的所有極大完全子圖，并記錄該級的極大完全子圖對應于初始網(wǎng)絡中的節(jié)點信息；繼續(xù)依此操作直至在商空間覆蓋網(wǎng)絡的極大完全子圖對應于初始網(wǎng)絡的節(jié)點信息中初始網(wǎng)絡的任意兩節(jié)點對都在同一個極大完全子圖中；各商空間覆蓋網(wǎng)絡按構(gòu)成先后順序排列形成一個遞階商空間覆蓋網(wǎng)絡鏈；按遞階商空間覆蓋網(wǎng)絡鏈的順序，記錄各個商空間覆蓋網(wǎng)絡的所有極大完全子圖和各個極大完全子圖對應于初始網(wǎng)絡的節(jié)點信息為商空間覆蓋模型；對于無向無權(quán)的不連通網(wǎng)絡，先求出各個連通分支，再對每個連通分支按無向無權(quán)連通網(wǎng)絡來求解其商空間覆蓋模型；從而得到一個遞階商空間覆蓋網(wǎng)絡鏈中各個商空間覆蓋網(wǎng)絡的所有極大完全子圖構(gòu)成的極大完全子圖集和極大完全子圖對應于初始網(wǎng)絡的節(jié)點信息的商空間覆蓋模型；

然后在此商空間模型基礎(chǔ)上進行路徑搜索：在商空間模型的極大完全子圖對應于初始網(wǎng)絡的節(jié)點信息中找出要搜索的起點和終點在不同商空間覆蓋網(wǎng)絡的極大完全子圖集中的對應位置的分層編號，并在分層編號前面加上附加在初始網(wǎng)絡中的標號，比較初始網(wǎng)絡起點和終點的分層編號，找出自左到右方向其編號相等的第一個位置，找到在遞階商空間覆蓋網(wǎng)絡鏈中的對應商空間覆蓋網(wǎng)絡極大完全子圖集；再從其在遞階商空間覆蓋網(wǎng)絡鏈中左邊鄰居的商空間覆蓋網(wǎng)絡開始搜索初始網(wǎng)絡起點到終點的路徑，其路徑用分層編號中該起點和終點所分別對應的編號來表示，接著再搜索初始網(wǎng)絡起點到終點在其左邊鄰居商空間覆蓋網(wǎng)絡中的路徑，其路徑的起點和終點是分層編號對應的編號，中間節(jié)點是遞階商空間覆蓋網(wǎng)絡鏈中右邊鄰居的商空間覆蓋網(wǎng)絡中得到路徑的從左到右兩節(jié)點的交集；依次類推，直到遞階商空間覆蓋網(wǎng)絡鏈中最左邊的商空間覆蓋網(wǎng)絡即為初始網(wǎng)絡，實現(xiàn)從粗粒度商空間覆蓋網(wǎng)絡逐步搜索到細粒度商空間的過程，從而得到初始網(wǎng)絡的起點到終點的最短路徑。