发明名称 | 获取路网上复反向最远邻居的暴力搜索方法及系统 | ||
摘要 | 本发明提供了一种获取路网上复反向最远邻居的暴力搜索方法及系统,本发明通过使用Dijkstra算法以每一个d∈VG作为源点进行一次扩展,直到Q中的所有点被访问到为止,若q在Q中的所有点被全部遍历之前被访问到,则q并非d的最远邻居,从而d不属于q的反向最远邻居;若q在Q中的其他点被全部遍历之后仍未被访问到,则确定d为p,p∈BRFN(q,Q,VG),能够在路网上快速搜索到查询点的单反向邻居。 | ||
申请公布号 | CN103336827A | 申请公布日期 | 2013.10.02 |
申请号 | CN201310280245.X | 申请日期 | 2013.07.04 |
申请人 | 上海交通大学 | 发明人 | 姚斌;邢昊原;李飞飞 |
分类号 | G06F17/30(2006.01)I | 主分类号 | G06F17/30(2006.01)I |
代理机构 | 上海思微知识产权代理事务所(普通合伙) 31237 | 代理人 | 郑玮 |
主权项 | 一种获取路网上复反向最远邻居的暴力搜索方法,其特征在于,包括:步骤一:对于给定路网G上的某一结点p和路网G上的所有结点VG,如果路网G上存在结点q,q与p的路网距离||q‑p||不小于p到VG当中任何点p’的距离||p′‑p||,则定义q为p相对于VG的最远邻居,记为fn(p,VG);步骤二:对于给定路网G上的所有结点VG和路网G上的查询集Q,定义q∈Q的复反向最远邻居是所有VG中距离q比Q中其它所有点都远的点的集合,即BRFN(q,Q,VG)={p|p∈VG,fn(p,Q)=q};步骤三:使用Dijkstra算法以每一个d∈VG作为源点进行一次扩展,直到Q中的所有点被访问到为止,若q在Q中的所有点被全部遍历之前被访问到,则q并非d的最远邻居,从而d不属于q的反向最远邻居;若q在Q中的其他点被全部遍历之后仍未被访问到,则确定d为p,p∈BRFN(q,Q,VG);步骤四:重复所述步骤三,直到获取到每一个查询点q的复反向最远邻居,即p∈BRFN(q,Q,VG)。 | ||
地址 | 200240 上海市闵行区东川路800号 |