[發明專利]獲取路網上單反向最遠鄰居的層次分區方法及系統

有效

• 申請號: 201310279130.9
• 申請日: 2013-07-04
• 公開（公告）號: CN103365983A
• 公開（公告）日: 2013-10-23
• 發明（設計）人: 姚斌;邢昊原;李飛飛
• 申請（專利權）人: 上海交通大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 上海思微知識產權代理事務所(普通合伙) 31237
• 代理人: 鄭瑋

1.一種獲取路網上單反向最遠鄰居的層次分區方法，其特征在于，包括：

步驟一：對于給定路網G上的某一結點p和路網G上的所有結點V_G，如果路網G上存在結點q，q與p的路網距離||q-p||不小于p到V_G當中任何點p’的距離||p′-p||，則定義q為p相對于V_G的最遠鄰居，記為fn(p,V_G)；

步驟二：對于給定路網G上的所有結點V_G，定義q的單反向最遠鄰居是V_G中以q作為最遠鄰居點的集合即MRFN(q,V_G)={p|p∈V_G,fn(p,V_G∪{q})=q}；

步驟三：使用自頂向下的方法構造路網G的層次分區樹，路網G中的結點劃分為m個分區SG_i，并且將每個分區遞歸的劃分為若干個子分區SG_i，直至達到所需的分區數量與層數；

步驟四：定義路網G上每一個分區或子分區SG_i的邊界結點為其中edge(d,d′)表示d與d′之間的邊，表示分區SG_i的所有結點；

步驟五：將某結點q到某分區或子分區SG_i的上界和下界分別定義為q到內的任何結點的最大和最小距離，記為和分區或子分區SG_i的直徑定義為類似的定義結點q到結點d的上界和下界分別為和

步驟六：將某分區或子分區SG_i的最遠上界和最遠下界分別定義為任意到它在路網G上最遠鄰居的距離最大值和最小值，記為和，類似的定義一個結點u到它路網G上最遠鄰居的距離為fub_u和flb_u；

步驟七：預計算某分區SG_i內子分區SG_i的邊界結點間的距離，同時預計算所有邊界結點在路網G上各自的最遠鄰居f和所有邊界結點各自在所在分區和子分區SG_i內的最遠鄰居；

步驟八：選擇所述路網G上的多個結點L作為地標，使用Dijkstra算法預計算每個結點L到所述剩下無子分區的分區或子分區上所有結點的距離；

步驟九：估計每個分區或子分區SG_i內的結點d到其路網G上的最遠鄰居距離的下界，對于∀d∈VSGi,∀b∈bdSGi,∀f∈VG,]]>有||b-f||-ubSGib≤||d-fn(d,VGi)||,]]>其中計算每個分區或子分區SG_i中g(b,f)的最大值作為該分區或子分區SG_i的

步驟十：將層次分區樹的所有分區壓入一遍歷隊列，從所述遍歷隊列依次彈出每個分區或子分區SG_i，判斷每個子分區SG_i，是否使得若是，則SG_i中的結點將該子分區從路網G上排除，若否，將該未排除的子分區的子分區SG_i或無子分區的子分區自身壓入所述遍歷隊列，從所述遍歷隊列依次彈出每個子分區的子分區SG_i，并重復上述判斷，直至從所述遍歷隊列里只剩下無子分區的分區或子分區，其中，計算的步驟如下，當且時，則當時，由于任何從q通往SG_i的路徑必須經過SG_i的邊界結點使用q到的上界來估計則ubSGiq=minb∈bdSGi(ubqb+ubSGib),]]>其中，使用三角不等式估計，的定義同是從所述預計算的所有邊界結點的距離和各自在所在分區和子分區SG_i內的最遠鄰居中獲取；

步驟十一：對于每一個所述剩下無子分區的分區或子分區上的結點d，使用三角不等式檢查距離||d-q||是否一定小于d到距離d最遠地標的距離||d-f||，若結點L中存在地標u和f，使得||d-u||+||u-q||<||d-f||，則q一定不是d的最遠鄰居，從而d一定不是q的反向最遠鄰居，將該結點d從所述剩下無子分區的分區或子分區上排除；

步驟十二：檢查每一個未排除的d∈P的最遠鄰居是不是q，如果是，則確定d為p，p∈MRFN(q,P)，如果不是，則將該d排除。