• 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03
    • / 30
    • 下载费用:30 金币  

    重庆时时彩大小单双稳赚: 获取路网上单反向最远邻居的层次分区方法及系统.pdf

    摘要
    申请专利号:

    重庆时时彩单双窍门 www.4mum.com.cn CN201310279130.9

    申请日:

    2013.07.04

    公开号:

    CN103365983A

    公开日:

    2013.10.23

    当前法律状态:

    授权

    有效性:

    有权

    法律详情: 授权|||实质审查的生效IPC(主分类):G06F 17/30申请日:20130704|||公开
    IPC分类号: G06F17/30 主分类号: G06F17/30
    申请人: 上海交通大学
    发明人: 姚斌; 邢昊原; 李飞飞
    地址: 200240 上海市闵行区东川路800号
    优先权:
    专利代理机构: 上海思微知识产权代理事务所(普通合伙) 31237 代理人: 郑玮
    PDF完整版下载: PDF下载
    法律状态
    申请(专利)号:

    CN201310279130.9

    授权公告号:

    ||||||

    法律状态公告日:

    2016.09.07|||2013.11.20|||2013.10.23

    法律状态类型:

    授权|||实质审查的生效|||公开

    摘要

    本发明提供了一种获取路网上单反向最远邻居的层次分区树方法及系统,包括:将层次分区树的所有分区压入一遍历队列,从所述遍历队列依次弹出每个分区或子分区SGi,判断每个子分区SGi,是否使得若是,则SGi中的结点将该子分区从队列中排除,若否,将该未排除的子分区的子分区SGi或无子分区的子分区自身压入所述遍历队列,从所述遍历队列依次弹出每个子分区的子分区SGi,并重复上述判断,直至从所述遍历队列里只剩下无子分区的分区或子分区,并检查每一个未排除的分区中的节点d∈P的最远邻居是不是q,如果是,则确定d为p,p∈MRFN(q,P)。本发明能够在路网上快速搜索到查询点的单反向邻居。

    权利要求书

    权利要求书
    1.  一种获取路网上单反向最远邻居的层次分区方法,其特征在于,包括:
    步骤一:对于给定路网G上的某一结点p和路网G上的所有结点VG,如果路网G上存在结点q,q与p的路网距离||q-p||不小于p到VG当中任何点p’的距离||p′-p||,则定义q为p相对于VG的最远邻居,记为fn(p,VG);
    步骤二:对于给定路网G上的所有结点VG,定义q的单反向最远邻居是VG中以q作为最远邻居点的集合即MRFN(q,VG)={p|p∈VG,fn(p,VG∪{q})=q};
    步骤三:使用自顶向下的方法构造路网G的层次分区树,路网G中的结点划分为m个分区SGi,并且将每个分区递归的划分为若干个子分区SGi,直至达到所需的分区数量与层数;
    步骤四:定义路网G上每一个分区或子分区SGi的边界结点为其中edge(d,d′)表示d与d′之间的边,表示分区SGi的所有结点;
    步骤五:将某结点q到某分区或子分区SGi的上界和下界分别定义为q到内的任何结点的最大和最小距离,记为和分区或子分区SGi的直径定义为类似的定义结点q到结点d的上界和下界分别为和
    步骤六:将某分区或子分区SGi的最远上界和最远下界分别定义为任意到它在路网G上最远邻居的距离最大值和最小值,记为和,类 似的定义一个结点u到它路网G上最远邻居的距离为fubu和flbu;
    步骤七:预计算某分区SGi内子分区SGi的边界结点间的距离,同时预计算所有边界结点在路网G上各自的最远邻居f和所有边界结点各自在所在分区和子分区SGi内的最远邻居;
    步骤八:选择所述路网G上的多个结点L作为地标,使用Dijkstra算法预计算每个结点L到所述剩下无子分区的分区或子分区上所有结点的距离;
    步骤九:估计每个分区或子分区SGi内的结点d到其路网G上的最远邻居距离的下界,对于∀d∈VSGi,∀b∈bdSGi,∀f∈VG,]]>||b-f||-ubSGib||d-fn(d,VGi)||,]]>其中计算每个分区或子分区SGi中g(b,f)的最大值作为该分区或子分区SGi的
    步骤十:将层次分区树的所有分区压入一遍历队列,从所述遍历队列依次弹出每个分区或子分区SGi,判断每个子分区SGi,是否使得若是,则SGi中的结点将该子分区从路网G上排除,若否,将该未排除的子分区的子分区SGi或无子分区的子分区自身压入所述遍历队列,从所述遍历队列依次弹出每个子分区的子分区SGi,并重复上述判断,直至从所述遍历队列里只剩下无子分区的分区或子分区,其中,计算的步骤如下,当且时,则当时,由于任何从q通往SGi的路径必须经过SGi的边界结点使用q到的上界来估计则ubSGiq=minb∈bdSGi(ubqb+ubSGib),]]>其中,使用三角不等式估计,的定义同是从所述预计算的所 有边界结点的距离和各自在所在分区和子分区SGi内的最远邻居中获??;
    步骤十一:对于每一个所述剩下无子分区的分区或子分区上的结点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排除。

    2.  如权利要求1所述的获取路网上单反向最远邻居的层次分区方法,其特征在于,步骤八中,所述选择的地标在路网G上均匀分布。

    3.  如权利要求1所述的获取路网上单反向最远邻居的层次分区方法,其特征在于,步骤三中将每个分区递归的划分为若干个子分区SGi的步骤中,使用Erwig and Hagen算法将每个分区递归的划分为若干个子分区SGi。

    4.  如权利要求1所述的获取路网上单反向最远邻居的层次分区方法,,其特征在于,所述步骤十二包括:
    步骤十二一:将某结点d到某分区或子分区SGi的上界和下界分别定义为d到内的任何结点的最大和最小距离,记为和分区或子分区SGi的直径定义为类似的定义结点d到结点d′的上界和下界分别为和
    步骤十二二:当且时,则当时,由于任何从d通往SGi的路径必须经过SGi的边界结点使用d到的上界来估计则ubSGiq=minb&Element;bdSGi(ubdb+ubSGib),]]>其中,可以使用三角不等式估计,而是从所述预计算的所有边界结点各自在所在分区和子分区SGi内的最远邻居中获取,的定义同
    步骤十二三:建立一个将分区SGi和结点d′的和以降序存储的优先队列,并将所有分区的压入队列中;
    步骤十二四:每次从所述优先队列里弹出第一个或如果弹出的是则转到步骤直十二六,如果弹出的是如果则d的最远邻居不可能是在SGi中,将该分区SGi从路网G上排除,否则,则判断该分区SGi是否有子分区,若有,则将该分区SGi的子分区的以降序压回所述优先队列,若无,则调用步骤十二五;
    步骤十二五:计算每一个对应的分区或子分区SGi中的所有结点d′至d的距离并将所有以降序压回所述优先队列,并调用步骤十二六;
    步骤十二六:从所述优先队列从弹出前几个将该前几个对应的d′确定为q,q∈fn(p,VG)。

    5.  如权利要求4所述的获取路网上单反向最远邻居的层次分区方法,其特征在于,步骤十二五中计算每一个对应的分区或子分区SGi中的所有结点d′ 至d的距离的步骤包括:
    若以d为源点进行一次Dijkstra算法以获得d到该分区或子分区SGi中的所有结点d′的距离
    若由于任何从d到的路径都必然经过该分区或子分区SGi的边界节点构造一个保留d和间距离的捷径子图G′,并在所述捷径子图G′上进行距离计算得到d到该分区或子分区SGi中的所有结点d′的距离

    6.  如权利要求5所述的获取路网上单反向最远邻居的层次分区方法,其特征在于,构造一个保留d和间距离的捷径子图G′的步骤中,使用HEPV和HiTi技术。

    7.  如权利要求5所述的获取路网上单反向最远邻居的层次分区方法,其特征在于,构造一个保留d和边界节点间距离的捷径子图G′的步骤中,预先保存所有边界节点之间的距离,使用d所在的分区SGi和预先保存的两个分区边界节点之间的距离构造捷径子图G′。

    8.  一种获取路网上单反向最远邻居的层次分区系统,其特征在于,包括:
    第一定义???,用于对于给定路网G上的某一结点p和路网G上的所有结点VG,如果路网G上存在结点q,q与p的路网距离||q-p||不小于p到VG当中任何点p’的距离||p′-p||,则定义q为p相对于VG的最远邻居,记为fn(p,VG);
    第二定义???,对于给定路网G上的所有结点VG,定义q的单反向最远邻居是VG中以q作为最远邻居点的集合即MRFN(q,VG)={p|p∈VG,fn(p,VG∪{q})=q};
    层次分区???,用于使用自顶向下的方法构造路网G的层次分区树,路网G中的结点划分为m个分区SGi,并且将每个分区递归的划分为若干个子分区SGi,直至达到所需的分区数量与层数;
    边界结点???,用于定义路网G上每一个分区或子分区SGi的边界结点为其中edge(d,d′)表示d与d′之间的边,表示分区SGi的所有结点;
    第一上下界???,用于将某结点q到某分区或子分区SGi的上界和下界分别定义为q到内的任何结点的最大和最小距离,记为和分区或子分区SGi的直径定义为类似的定义结点q到结点d的上界和下界分别为和
    第二上下界???,用于将某分区或子分区SGi的最远上界和最远下界分别定义为任意到它在路网G上最远邻居的距离最大值和最小值,记为和类似的定义一个结点u到它路网G上最远邻居的距离为fubu和flbu;
    预计算???,用于预计算某分区SGi内子分区SGi的边界结点间的距离,同时预计算所有边界结点在路网G上各自的最远邻居f和所有边界结点各自在所在分区和子分区SGi内的最远邻居;
    距离???,用于选择所述路网上的多个结点L作为地标,使用Dijkstra算法预计算每个结点L到所述剩下无子分区的分区或子分区上所有结点的距离;
    估计???,用于估计每个分区或子分区SGi内的结点d到其路网G上的最远 邻居距离的下界,对于&ForAll;d&Element;VSGi,&ForAll;b&Element;bdSGi,&ForAll;f&Element;VG,]]>||b-f||-ubSGib||d-fn(d,VGi)||,]]>其中计算每个分区或子分区SGi中g(b,f)的最大值作为该分区或子分区SGi的
    队列???,用于将层次分区树的所有分区压入一遍历队列,从所述遍历队列依次弹出每个分区或子分区SGi,判断每个子分区SGi,是否使得若是,则SGi中的结点将该子分区从路网G上排除,若否,将该未排除的子分区的子分区SGi或无子分区的子分区自身压入所述遍历队列,从所述遍历队列依次弹出每个子分区的子分区SGi,并重复上述判断,直至从所述遍历队列里只剩下无子分区的分区或子分区,其中,计算的步骤如下,当且时,则当时,由于任何从q通往SGi的路径必须经过SGi的边界结点使用q到的上界来估计则ubSGiq=minb&Element;bdSGi(ubqb+ubSGib),]]>其中,的使用三角不等式估计,的定义同是从所述预计算的所有边界结点的距离和各自在所在分区和子分区SGi内的最远邻居中获??;
    结点排除???,用于对于每一个所述剩下无子分区的分区或子分区上的结点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排除。

    9.  如权利要求8所述的获取路网上单反向最远邻居的层次分区系统,其特征在于,所述距离??檠≡竦牡乇暝诼吠鳪上均匀分布。

    10.  如权利要求8所述的获取路网上单反向最远邻居的层次分区系统,其特征在于,所述层次分区??槭褂肊rwig and Hagen算法将每个分区递归的划分为若干个子分区SGi。

    11.  如权利要求8所述的获取路网上单反向最远邻居的层次分区系统,其特征在于,所述检查??榘ǎ?BR>第一上下界单元,用于将某结点d到某分区或子分区SGi的上界和下界分别定义为d到内的任何结点的最大和最小距离,记为和分区或子分区SGi的直径定义为类似的定义结点d到结点d′的上界和下界分别为和
    估计单元,用于当且时,则当时,由于任何从d通往SGi的路径必须经过SGi的边界结点使用d到的上界来估计则ubSGiq=minb&Element;bdSGi(ubdb+ubSGib),]]>其中,可以使用三角不等式估计,而是从所述预计算的所有边界结点各自在所在分区和子分区SGi内的最远邻居中获取,的定义同
    队列单元,用于建立一个将分区SGi和结点d′的和以降序存储的优 先队列,并将所有分区的压入队列中;
    分区排除单元,用于每次从所述优先队列里弹出第一个或如果弹出的是则调用最远邻居单元,如果弹出的是如果则d的最远邻居不可能是在SGi中,将该分区SGi从路网G上排除,否则,则判断该分区SGi是否有子分区,若有,则将该分区SGi的子分区的以降序压回所述优先队列,若无,则调用计算单元;
    计算单元,用于计算每一个对应的分区或子分区SGi中的所有结点d′至d的距离并将所有以降序压回所述优先队列,并调用最远邻居单元;
    最远邻居单元,用于从所述优先队列从弹出前几个将该前几个对应的d′确定为q,q∈fn(p,VG)。

    12.  如权利要求11所述的获取路网上单反向最远邻居的层次分区系统,其特征在于,所述计算单元,用于:
    若以d为源点进行一次Dijkstra算法以获得d到该分区或子分区SGi中的所有结点d′的距离
    若由于任何从d到的路径都必然经过该分区或子分区SGi的边界节点构造一个保留d和间距离的捷径子图G′,并在所述捷径子图G′上进行距离计算得到d到该分区或子分区SGi中的所有结点d′的距离

    13.  如权利要求12所述的获取路网上单反向最远邻居的层次分区系统,其特征在于,所述计算单元使用HEPV和HiTi技术构造一个保留d和间距离 的捷径子图G′。

    14.  如权利要求12所述的获取路网上单反向最远邻居的层次分区系统,其特征在于,所述计算单元预先保存所有边界节点之间的距离,使用d所在的分区SGi和预先保存的两个分区边界节点之间的距离构造捷径子图G′。

    关 键 词:
    获取 路网 反向 最远 邻居 层次 分区 方法 系统
      专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    关于本文
    本文标题:获取路网上单反向最远邻居的层次分区方法及系统.pdf
    链接地址://www.4mum.com.cn/p-5779177.html
    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们

    [email protected] 2017-2018 www.4mum.com.cn网站版权所有
    经营许可证编号:粤ICP备17046363号-1 
     


    收起
    展开
  • 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03