[發(fā)明專利]獲取路網上復反向最遠鄰居的暴力搜索方法及系統(tǒng)

有效

• 申請?zhí)枺?/td>: 201310280245.X
• 申請日: 2013-07-04
• 公開（公告）號: CN103336827B
• 公開（公告）日: 2016-11-30
• 發(fā)明（設計）人: 姚斌;邢昊原;李飛飛
• 申請（專利權）人: 上海交通大學
• 主分類號: 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和路網G上的查詢集Q，定義q∈Q的復反向最遠鄰居是所有V_G中距離q比Q中其它所有點都遠的點的集合，即BRFN(q,Q,V_G)={p|p∈V_G,fn(p,Q)=q};

步驟三：使用Dijkstra算法以每一個d∈V_G作為源點進行一次擴展，直到Q中的所有點被訪問到為止，若q在Q中的所有點被全部遍歷之前被訪問到，則q并非d的最遠鄰居，從而d不屬于q的反向最遠鄰居；若q在Q中的其他點被全部遍歷之后仍未被訪問到，則確定d為p，p∈BRFN(q,Q,V_G)；

步驟四：重復所述步驟三，直到獲取到每一個查詢點q的復反向最遠鄰居，即p∈BRFN(q,Q,V_G)。

2.一種獲取路網上復反向最遠鄰居的暴力搜索系統(tǒng)，其特征在于，包括：

第一定義模塊，用于對于給定路網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和路網G上的查詢集Q，定義q∈Q的復反向最遠鄰居是所有V_G中距離q比Q中其它所有點都遠的點的集合，即BRFN(q,Q,V_G)={p|p∈V_G,fn(p,Q)=q};

搜索模塊，用于獲取每一個查詢點q的復反向最遠鄰居，即p∈BRFN(q,Q,V_G)，獲取每一個查詢點q的復反向最遠鄰居包括：使用Dijkstra算法以每一個d∈V_G作為源點進行一次擴展，直到Q中的所有點被訪問到為止，若q在Q中的所有點被全部遍歷之前被訪問到，則q并非d的最遠鄰居，從而d不屬于q的反向最遠鄰居；若q在Q中的其他點被全部遍歷之后仍未被訪問到，則確定d為p，p∈BRFN(q,Q,V_G)。