• 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 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
    • / 9
    • 下载费用:30 金币  

    重庆时时彩个位技: 一种基于图嵌入的在道路网络中查找最优路径的方法.pdf

    关 键 词:
    一种 基于 嵌入 道路 网络 查找 最优 路径 方法
      专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    摘要
    申请专利号:

    CN201110124954.X

    申请日:

    2011.05.16

    公开号:

    CN102156756A

    公开日:

    2011.08.17

    当前法律状态:

    撤回

    有效性:

    无权

    法律详情: 发明专利申请公布后的视为撤回IPC(主分类):G06F 17/30申请公布日:20110817|||实质审查的生效IPC(主分类):G06F 17/30申请日:20110516|||公开
    IPC分类号: G06F17/30 主分类号: G06F17/30
    申请人: 复旦大学
    发明人: 孙未未; 陈楚南; 陈翀; 陈坤杰
    地址: 200433 上海市杨浦区邯郸路220号
    优先权:
    专利代理机构: 上海正旦专利代理有限公司 31200 代理人: 陆飞;盛志范
    PDF完整版下载: PDF下载
    法律状态
    申请(专利)号:

    CN201110124954.X

    授权公告号:

    ||||||

    法律状态公告日:

    2014.01.08|||2012.05.30|||2011.08.17

    法律状态类型:

    发明专利申请公布后的视为撤回|||实质审查的生效|||公开

    摘要

    本发明属于空间数据库技术领域,具体涉及一种道路网络中查找最优路径的方法。该方法的步骤为:给定路网中的n个属性的点集合M1、M2、…、Mn,以及一个起点s和一个终点t,以s为起点,根据图嵌入框架提供的上下界,以迭代查找最近邻的方法找出贪心路径Rg;然后按顺序遍历n个属性的点集合M1、M2、…、Mn,以贪心路径的长度为上界,结合上下界对存在的路径进行剪枝;最后对剩下的候选路径进行精确计算,找出最优路径。通过本发明的基于图嵌入的查找方法,大大减小了搜索空间,因而有更高的查找效率。

    权利要求书

    1.一种道路网络中的查找最优路径的方法,其特征在于具体步骤如下:(1)对于查询用户输入的n个属性的点集合M1、M2、…、Mn,以及一个起点s和一个终点t,以迭代的方法查找贪心路径;(2)以步骤(1)求出的贪心路径的长度为上界,结合图嵌入框架提供的上、下界,将不可能成为最优路径的路径直接删除;(3)对于步骤(2)剪枝剩下的候选路径,精确计算其长度,选出长度最小的作为最优路径;其中,涉及的概验定一如下:定义1.?网络(G):表示顶点之间邻接关系的拓扑结构,由顶点集合(V)以及顶点之间的边的集合(E)构成;定义2.?两点uv之间的距离:两点之间最短路径的长度,用dnet(u,?v)表示;定义3.?参照点:对于路网G?=?(V,?E),从V中选出k个点,称这k个点为参照点r1,?r2,?…,?rk;定义4.?k维属性:对于任意uV,定义uk个属性f1(u),?f2(u),?…,?fk(u),其中fi(u)?=?dnet?(ri?,?u),即u的第i个属性等于u到第i个参照点的网络距离,根据定义,每个u都有一个k维向量F(u)?=?(f1(u),?f2(u),?…,?fk(u))T;定义5.?网络距离上界:UB(u,?v)?=?min{?fi(u)?+?fi(v)?|?1?≤?i?≤?k?};定义6.?网络距离下界:LB(u,?v)?=?max{|?fi(u)?-?fi(v)|?|1?≤?i?≤?k?};定义7.?路径长度:对于查询序列(s,?M1,?M2,?…,?Mn,?t)所对应的一条路径SR(s,P1,?P2,?…,?Pn,?t),其长度定义为:;定义8.?最优路径OSR:查询序列(s,?M1,?M2,?…,?Mn,?t)所对应的所有路径中,长度最小的称为查询序列(s,?M1,?M2,?…,?Mn,?t)的最优路径OSR(s,?M1,?M2,?…,?Mn,?t);定义9.?贪心路径SR:对于查询序列(s,M1,?M2,?…,?Mn,?t)的一条路径SR(s,?P1,?P2,?…,?Pn,?t),若P1是M1中离s最近的点,且Pi+1是Mi+1中离Pi最近的点,其中2?≤?i?≤?n?-?1,则称该路径为查询序列(s,?M1,?M2,?…,?Mn,?t)的贪心路径SRg,其长度记为Lg。2.根据权利要求1所述的方法,其特征在于步骤(1)中所述查找贪心路径Rg的步骤如下:1)贪心路径初始化为空;2)以s为源点,在集合M1中找出到s点距离上界最小的点N1,将N1添加到贪心路径;3)以N1为源点,在集合M2中找出到N1点距离上界最小的点N2,将N2添加到贪心路径;4)重复类似以上的步骤,依次在集合Mi+1中找出到Ni点距离上界最小的点Ni+1,直至找出集合Mn中找出到Ni-1点距离上界最小的点Nn为止;5)最后将终点t添加到贪心路径。3.根据权利要求2所述的方法,其特征在于步骤(2)中所述查找对路径剪枝的步骤如下:1)按照求出的贪心路径Rg,其长度上界UB(Rg),对于集合M1中的点p1,如果p1到st的距离下界(LB)之和超过UB(Rg),即LB(p1,?s)?+?LB(p1,?t)?>?UB(Rg),则将所有通过p1的路径删除,否则将路径R(s,?p1)添加到候选路径集合Q;2)对于候选路径集合Q的每条路径R(s,?p1),遍历集合M2:对于集合M2中的每个点p2,若LB(R)?+?LB(p1,?p2)?+?LB(p2,?t)?>?UB(Rg),则将所有通过p2的路径删除,否则将路径R(s,?p1,?p2)添加到备份候选路径集合Q’;3)清空Q,将Q’的路径复制到Q;对集合M2,M3,…,Mn重复步骤2)和3)。4.根据权利要求3所述的方法,其特征在于步骤(3)中所述精确计算候选路径长度的方法如下:1)采用A*算法计算候选路径中每一跳的长度,并将其长度记录;2)A*算法的估值函数为图嵌入框架提供的下界函数;3)若某候选路径的某一跳的长度在之前计算过程中已经求出,则直接利用之前计算结果;4)每计算出一条候选路径的精确长度,更新最优路径的长度上界。

    说明书

    一种基于图嵌入的在道路网络中查找最优路径的方法

    技术领域

    本发明属于道路网络技术领域,具体涉及一种道路网络中的最优路径查找方法。

    背景技术

    随着无线通讯技术的发展以及移动设备的大规模应用,空间数据库技术在现实中得到了很好的应用,成为了当今的研究热点之一,其发展前景被广泛看好。作为空间数据库中最常见的查询之一,最优路径查询是,给定n个属性的点集合M1、M2、…、Mn,以及一个起点s和一个终点t,找出一条长度最小的路径R,其中R起始于s,依次经过M1、M2、…、Mn每个集合中的至少一个点,最终到达终点t。

    现有的最优路径查询方法中,大多数方法是基于欧几里得空间环境的,在欧几里得空间环境下,点与点之间的距离是直线距离,而在道路网络环境下,点与点之间的距离等于由两点在网络中的最短路径长度,因此针对欧几里得空间环境下的查询方法无法直接应用到道路网络环境下。在道路网络环境下,现有的最优路径查找方法是以起点为源点,通过迭代最近邻查找搜索路径,并将找出的候选路径用一个最小堆维护。由于该方法所维护的路径最小堆会随着最优路径查询所涉及的属性个数的增多而急剧增长,因此该方法在现实路网中效率不高,不能满足及时响应用户查询的要求。

    发明内容

    本发明的目的是针对道路网络中的最优路径查找问题,提出一种基于图嵌入框架的方法,以提高查找速度。

    本发明提出的在道路网络中查找最优路径的方法,利用图嵌入框架提供的上下界,结合上下界原理以及最优路径的特征,对存在的路径进行剪枝,达到很好的剪枝效果,最后在确认阶段找出代价最小的路径返回,既保证了找出的路径是满足条件中长度最小的,又大大减小了搜索空间,提高了查找效率。

    首先对一些基本概念进行定义:

    定义1.?网络(G):表示顶点之间邻接关系的拓扑结构,由顶点集合(V)以及顶点之间的边的集合(E)构成。

    定义2.?两点uv之间的距离:两点之间最短路径的长度,用dnet(u,?v)表示。

    定义3.?参照点:对于路网G?=?(V,?E),从V中选出k个点,称这k个点为参照点r1,?r2,?…,?rk。

    定义4.?k维属性:对于任意uV,定义uk个属性f1(u),?f2(u),?…,?fk(u),其中fi(u)?=?dnet?(ri?,?u),即u的第i个属性等于u到第i个参照点的网络距离,根据定义,每个u都有一个k维向量F(u)?=?(f1(u),?f2(u),?…,?fk(u))T。

    定义5.?网络距离上界:UB(u,?v)?=?min{?fi(u)?+?fi(v)?|?1?≤?i?≤?k?}

    定义6.?网络距离下界:LB(u,?v)?=?max{|?fi(u)?-?fi(v)|?|1?≤?i?≤?k?}

    定义7.?路径长度:对于查询序列(s,?M1,?M2,?…,?Mn,?t)所对应的一条路径SR(s,P1,?P2,?…,?Pn,?t),其长度定义为:

    定义8.?最优路径OSR:查询序列(s,?M1,?M2,?…,?Mn,?t)所对应的所有路径中,长度最小的称为查询序列(s,?M1,?M2,?…,?Mn,?t)的最优路径OSR(s,?M1,?M2,?…,?Mn,?t)。

    定义9.?贪心路径SR:对于查询序列(s,M1,?M2,?…,?Mn,?t)的一条路径SR(s,?P1,?P2,?…,?Pn,?t),若P1是M1中离s最近的点,且Pi+1是Mi+1中离Pi最近的点,其中2?≤?i?≤?n?-?1,则称该路径为查询序列(s,?M1,?M2,?…,?Mn,?t)的贪心路径SRg,其长度记为Lg。

    根据以上定义,对于输入的n个属性的点集合M1、M2、…、Mn,以及一个起点s和一个终点t,,本发明提出的最优路径查找方法是基于以下性质的:

    (1).?对于任意集合Mi的任意一点P,若LB(s,?P)?+?LB(t,?P)?>?Lg,则OSR不会经过P点。更一般的,假设OSR经过Mi集合的Pi点,对于集合Mj(j?>?i)中任意一点Pj,若LB(s,?Pi)?+?LB(Pi,?Pj)?+?LB(t,?Pj)?>?Lg,则OSR不会经过Pj。

    (2).?对于任意集合Mi的一点Pi,若对于Mi+1的所有点Pi+1都有LB(s,?Pi)?+?LB(Pi?,?Pi+1)?+?LB(t,?Pi+1)?>?Lg,则OSR不会经过Pi。

    (3).?假设对于查询序列?(s,M1,?M2,?…,?Mn,?t)的最优路径为OSR(s,?P1,?…,?Pi,?Pi+1,?…,?Pn,?t),则路径R(s,?P1,?…,?Pi-1,?Pi)一定是查询序列(s,?M1,?M2,?…,?Mi-1,?Pi)的最优路径,其中,i≥?2。

    (4).?对于Mii≥?2)集合中的某一点Pi,假设存在两条路径R1(s,?P1,?…,?Pi-1,?Pi)和R2(s,?P1’,?…,?Pi-1’,?Pi),若LB(R1)?>?UB(R2),则R1可以直接剪枝。

    基于以上性质,本发明方法利用图嵌入框架提供的上下界,查找最优路径,具体步骤是:

    (1)对于查询用户输入的n个属性的点集合M1、M2、…、Mn,以及一个起点s和一个终点t,以迭代的方法查找贪心路径;

    (2)以步骤(1)求出的贪心路径的长度为上界,结合图嵌入框架提供的上下界,将不可能成为最优路径的路径直接删除;

    (3)对于步骤(2)剪枝剩下的候选路径,精确计算其长度,选出长度最小的作为最优路径。

    本发明中,步骤(1)中所述查找贪心路径的步骤如下:

    1)贪心路径初始化为空;

    2)以s为源点,在集合M1中找出到s点距离上界最小的点N1,将N1添加到贪心路径;

    3)以N1为源点,在集合M2中找出到N1点距离上界最小的点N2,将N2添加到贪心路径;

    4)重复类似以上的步骤,依次在集合Mi+1中找出到Ni点距离上界最小的点Ni+1,直至找出集合Mn中找出到Ni-1点距离上界最小的点Nn为止;

    5)最后将终点t添加到贪心路径。

    本发明中,步骤(2)中所述查找对路径剪枝的步骤如下:

    1)按照求出的贪心路径Rg,其长度上界UB(Rg),对于集合M1中的点p1,如果p1到st的距离下界(LB)之和超过UB(Rg),即LB(p1,?s)?+?LB(p1,?t)?>?UB(Rg),则将所有通过p1的路径删除,否则将路径R(s,?p1)添加到候选路径集合Q;

    2)对于候选路径集合Q的每条路径R(s,?p1),遍历集合M2:对于集合M2中的每个点p2,若LB(R)?+?LB(p1,?p2)?+?LB(p2,?t)?>?UB(Rg),则将所有通过p2的路径删除,否则将路径R(s,?p1,?p2)添加到备份候选路径集合Q’;

    3)清空Q,将Q’的路径复制到Q;

    4)对集合M2,M3,…,Mn重复步骤2)和3)。

    本发明中,步骤(3)中所述精确计算候选路径长度的方法如下:

    1)采用A*算法计算候选路径中每一跳的长度,并将其长度记录;

    2)A*算法的估值函数为图嵌入框架提供的下界函数;

    3)若某候选路径的某一跳的长度在之前计算过程中已经求出,则直接利用之前计算结果;

    4)每计算出一条候选路径的精确长度,更新最优路径的长度上界。

    根据以上步骤进行的查找方法,在剪枝阶段删除了很大部分的路径,在确认阶段进一步精确,找出最优路径。附图2为本发明方法实验检测所采用的数据源,为一个真实路网。附图3-4为本发明方法的剪枝效果展示,从图中可以看出,本发明方法通过剪枝阶段,删除了99%左右的无效路径,大大减小了搜索空间。附图5-6为本发明方法与背景技术比较的实验结果,通过附图可以很清楚地验证本发明方法与背景技术相比在查找速度上的提高。

    附图说明

    图1显示了本发明所描述的最优路径查找方法的示例。

    图2显示了本发明实验所采用的数据源。

    图3显示了属性个数对本发明方法的剪枝效果的影响。

    图4显示了集合大小对本发明方法的剪枝效果的影响。

    图5和图6显示了本发明方法与背景技术的性能比较。

    具体实施方式

    本发明所描述的最优路径查找方法是基于图嵌入框架的,下面将通过一个例子详细描述本发明所述方法的具体实施方式:

    在由图1表示的一个道路网络中,用户输入起点s,终点t,以及两个属性集合:M1={g1,?g2,?g3,?g4},?M2?=?{b1,?b2,?b3,?b4,?b5},那么按照以下步骤进行查找:

    (1)选取参照点r1,r2,计算每个点到参照点的距离,得到2维向量并存储;

    (2)计算贪心路径为Rg?=?R(s,?g1,?b2,?t);

    (3)遍历集合M1和M2,删除无效路径,得到候选路径为R1(s,?g1,?b2,?t)和R2(s,?g1,?b3,?t);

    精确计算R1和R2的长度,比较取出长度最小的为R2(s,?g1,?b3,?t),因此最优路径为(s,?g1,?b3,?t)。

    关于本文
    本文标题:一种基于图嵌入的在道路网络中查找最优路径的方法.pdf
    链接地址://www.4mum.com.cn/p-5867940.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
  • 股票涨跌与统计学 股票涨跌幅计算公式软件 同花顺炒股软件下载 全国股票配资合作 短线股票推荐网每日 腾讯股票 股票行情大盘走势k图 2011年热门股票推荐 股票涨跌的原理 炒股有风险 股票配资送28888元体验 股票涨跌和什么有关 分析股票涨跌 股票指数期货开户 2014年上证指数预测图 海王星炒股软件下载