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

    重庆时时彩代理1960: 基于深度优先遍历的可达路径的查找方法与装置.pdf

    摘要
    申请专利号:

    重庆时时彩单双窍门 www.4mum.com.cn CN201510738182.7

    申请日:

    2015.11.03

    公开号:

    CN105606110A

    公开日:

    2016.05.25

    当前法律状态:

    授权

    有效性:

    有权

    法律详情: 授权|||著录事项变更IPC(主分类):G01C 21/34变更事项:申请人变更前:中兴软创科技股份有限公司变更后:浩鲸云计算科技股份有限公司变更事项:地址变更前:210012 江苏省南京市雨花台区紫?;?8号变更后:210012 江苏省南京市雨花台区宁双路28号627室|||实质审查的生效IPC(主分类):G01C 21/34申请日:20151103|||公开
    IPC分类号: G01C21/34 主分类号: G01C21/34
    申请人: 中兴软创科技股份有限公司
    发明人: 张晓飞; 刘晓华; 刘四奎; 汤夕根
    地址: 210012 江苏省南京市雨花台区紫?;?8号
    优先权:
    专利代理机构: 江苏致邦律师事务所 32230 代理人: 闫东伟
    PDF完整版下载: PDF下载
    法律状态
    申请(专利)号:

    CN201510738182.7

    授权公告号:

    |||||||||

    法律状态公告日:

    2019.03.01|||2018.09.14|||2016.06.22|||2016.05.25

    法律状态类型:

    授权|||著录事项变更|||实质审查的生效|||公开

    摘要

    本发明提供一种基于深度优先遍历的可达路径的查找方法,包括:步骤1、基于电子警察过车数据获取每个车辆的大概轨迹数据;步骤2、依据步骤1所得到的每个车辆的大概轨迹数据,采用深度优先遍历算法进行所有可能路径的查找。本发明的方法中,依据电子警察过车数据,对每辆车进行分析,得到每辆车的运行轨迹,当电子警察密度足够大时,可以直接得到车辆行驶轨迹,而不必借助GPS数据进行定位分析,同时结合路径搜索算法直接查找地图上任意两点之间的合理可达路径,可用于地图导航功能。

    权利要求书

    1.一种基于深度优先遍历的可达路径的查找方法,其特征在于,包括:步骤1、基于电子警察过车数据获取每个车辆的大概轨迹数据;步骤2、依据步骤1所得到的每个车辆的大概轨迹数据,采用深度优先遍历算法进行所有可能路径的查找。2.根据权利要求1所述的基于深度优先遍历的可达路径的查找方法,其特征在于,前述的电子警察过车数据包括:路段编号、检测时间、车牌号、车辆类型、车牌颜色、车速以及检测设备ID,每个车辆的大概轨迹数据包括:车牌号、起点交叉口以及起点时间、终点交叉口以及终点时间、所有途经路口以及途经路口时间,其中所述的途径路口时间与路口一一对应。3.根据权利要求1或2所述的基于深度优先遍历的可达路径的查找方法,其特征在于,前述步骤1的实现具体包括:步骤1-1、获取某一天的所有电子警察过车数据,并将所有的数据按车牌号分类,剔除车牌号=‘--’的这一类的所有数据,其中,这些电子警察过车数据包括:路段编号、检测时间、车牌号、车辆类型、车牌颜色、车速以及检测设备ID;步骤1-2、对剔除后的其余类数据,每一类数据按前述检测时间由小到大排序;步骤1-3、对某一类排序后的数据进行处理,假设共有n条数据,则求出相邻两个检测时间ti和ti+1的差Δti=ti+1-ti,i=1,2,…,n-1;步骤1-4、找到大于设定的时间阈值Tpre的所有tk+1,k≥0,并且找到所有对应的第k条数据和第k+1条数据;假设一共有m条数据,m≥0,将该类的第一条数据和最后一条数据加入,并去除重复数据后,对余下数据按前述检测时间排序后,将第一条和第二条数据作为一组,第三条和第四条数据作为一组,依次两两一组,若最后多余一条数据,则删除该条数据;步骤1-5、对步骤1-4中两两一组的数据中的某一组数据,将车牌号存在中间数据的车牌中,将检测时间早的数据的检测时间保存在中间数据的起点时间中,并由该条数据的路段ID,从MD_SEGMENT表中查到该路段ID的下游路口ID,保存在中间数据的起点交叉口;将检测时间晚的数据的检测时间保存在中间数据的终点时间中,并由该条数据的路段ID,从MD_SEGMENT表中查到该路段ID的下游路口ID,保存在中间数据的终点交叉口;找到该类中检测时间属于起点时间到终点时间的所有数据,由每条数据的路段ID,从MD_SEGMENT表中查到该路段ID的下游路口ID,将这些下游路口ID和起点路口,终点路口按每条数据的检测时间先后,作为一个数组存在途经路口字段;其中,前述的MD_SEGMENT表为数字路网信息存储表,该表中记录了路段ID以及对应的道路上游路口与下游路口信息;步骤1-6、将步骤1-4得到的每一组分组数据都按照步骤5处理,所有组数据处理完毕;步骤1-7、对经步骤1-2剔除数据后的所有类的数据,按步骤1-3-步骤1-6处理,最后得到并输出每个车辆的大概轨迹数据。4.根据权利要求3所述的基于深度优先遍历的可达路径的查找方法,其特征在于,前述步骤2的实现具体包括:步骤2-1:从每个车辆的大概轨迹数据中取出一条数据,对该数据的所有途经路口信息中的所有路口,从第一个开始,依次查看下一个路口是否为前一个路口的下游路口:若所有相邻路口的后一个路口都是前一个路口的下游路口,则将相应的数据保存在一跟踪数据表中;若存在某两个相邻的路口ID不是上下游路口关系,则将这两个ID中的前一个作为起点,后一个作为终点,二者时间差作为t,利用深度优选遍历算法求出从起点到终点,且时间不超过t*l的所有路径,l为时间配置系数;从路径中找到权重最小且路径特点标记=1的路径作为可能路径;若不存在路径特点标记=1的路径,则直接找到0权重路径值最小的路径作为可能路径;步骤2-2、由步骤2-1补齐所有相邻2个路口不是上下游路口的之间的路径;步骤2-3:将补齐后的路径与原来的路径合并为一条路径保存在前述的跟踪数据表内。5.根据权利要求3所述的基于深度优先遍历的可达路径的查找方法,其特征在于,前述时间配置系数l可调节,0.5≤l≤2。6.根据权利要求3所述的基于深度优先遍历的可达路径的查找方法,其特征在于,前述的时间阈值Tpre设定为3600s。7.一种基于深度优先遍历的可达路径的查找装置,其特征在于,包括:用于基于电子警察过车数据获取每个车辆的大概轨迹数据的???;以及用于依据前述所得到的每个车辆的大概轨迹数据,采用深度优先遍历算法进行所有可能路径的查找的???。8.根据权利要求7所述的基于深度优先遍历的可达路径的查找装置,其特征在于,所述基于电子警察过车数据获取每个车辆的大概轨迹数据的??榘ǎ?/claim-text>用于获取某一天的所有电子警察过车数据,并将所有的数据按车牌号分类,剔除车牌号=‘--’的这一类的所有数据的???,其中,这些电子警察过车数据包括:路段编号、检测时间、车牌号、车辆类型、车牌颜色、车速以及检测设备ID;用于对剔除后的其余类数据,按前述检测时间由小到大排序的???;用于对某一类排序后的数据进行处理的???,该??楸簧柚贸砂凑障率龇绞浇写恚杭偕韫灿衝条数据,则求出相邻两个检测时间ti和ti+1的差Δti=ti+1-ti,i=1,2,…,n-1;用于找到大于设定的时间阈值Tpre的所有tk+1,k≥0,并且找到所有对应的第k条数据和第k+1条数据以进行处理的???,该??楸簧柚贸砂凑障率龇绞浇写恚杭偕枰还灿衜条数据,m≥0,将该类的第一条数据和最后一条数据加入,并去除重复数据后,对余下数据按前述检测时间排序后,将第一条和第二条数据作为一组,第三条和第四条数据作为一组,依次两两一组,若最后多余一条数据,则删除该条数据;用于对前述分组数据进行处理的???,该??楸簧柚贸砂凑障率龇绞浇?,不再赘述。

    说明书

    基于深度优先遍历的可达路径的查找方法与装置

    技术领域

    本发明涉及车辆导航技术领域,具体而言涉及一种基于电子警察
    数据以及深度优先遍历的地图中任意两点之间的可达路径的查找方
    法与装置。

    背景技术

    现有大部分车辆的轨迹跟踪是基于GPS定位数据,进行的经纬度
    跟踪。但基于GPS的跟踪要求被跟踪车辆必须拥有GPS定位装置,
    并不断上传GPS数据,并被获取到,方能够对其进行实时的轨迹跟踪。
    此外,由于GPS数据本身都会存在一定误差,在进行路径匹配时需要
    尽量消除这种不可避免的误差,这对于导航来说是不利的。

    发明内容

    本发明目的在于提供一种可达路径的查找方法与装置,通过电子
    警察数据以及深度优先遍历算法实现地图中任意两点之间的轨迹查
    找与规划。

    本发明的上述目的通过独立权利要求的技术特征实现,从属权利
    要求以另选或有利的方式发展独立权利要求的技术特征。

    为达成上述目的,本发明提出一种基于深度优先遍历的可达路径
    的查找方法,包括:

    步骤1、基于电子警察过车数据获取每个车辆的大概轨迹数据;

    步骤2、依据步骤1所得到的每个车辆的大概轨迹数据,采用深
    度优先遍历算法进行所有可能路径的查找。

    进一步的实施例中,前述的电子警察过车数据包括:路段编号、
    检测时间、车牌号、车辆类型、车牌颜色、车速以及检测设备ID,
    每个车辆的大概轨迹数据包括:车牌号、起点交叉口以及起点时间、
    终点交叉口以及终点时间、所有途经路口以及途经路口时间,其中所
    述的途径路口时间与路口一一对应。

    进一步的实施例中,前述步骤1的实现具体包括:

    步骤1-1、获取某一天的所有电子警察过车数据,并将所有的数
    据按车牌号分类,剔除车牌号=‘--’的这一类的所有数据,其中,
    这些电子警察过车数据包括:路段编号、检测时间、车牌号、车辆类
    型、车牌颜色、车速以及检测设备ID;

    步骤1-2、对剔除后的其余类数据,每一类数据按前述检测时间
    由小到大排序;

    步骤1-3、对某一类排序后的数据进行处理,假设共有n条数据,
    则求出相邻两个检测时间ti和ti+1的差Δti=ti+1-ti,i=1,2,…,n-1;

    步骤1-4、找到大于设定的时间阈值Tpre的所有tk+1,k≥0,并且找
    到所有对应的第k条数据和第k+1条数据;假设一共有m条数据,m≥0,
    将该类的第一条数据和最后一条数据加入,并去除重复数据后,对余
    下数据按前述检测时间排序后,将第一条和第二条数据作为一组,第
    三条和第四条数据作为一组,依次两两一组,若最后多余一条数据,
    则删除该条数据;

    步骤1-5、对步骤1-4中两两一组的数据中的某一组数据,将车
    牌号存在中间数据的车牌中,将检测时间早的数据的检测时间保存在
    中间数据的起点时间中,并由该条数据的路段ID,从MD_SEGMENT
    表中查到该路段ID的下游路口ID,保存在中间数据的起点交叉口;
    将检测时间晚的数据的检测时间保存在中间数据的终点时间中,并由
    该条数据的路段ID,从MD_SEGMENT表中查到该路段ID的下游
    路口ID,保存在中间数据的终点交叉口;找到该类中检测时间属于
    起点时间到终点时间的所有数据,由每条数据的路段ID,从
    MD_SEGMENT表中查到该路段ID的下游路口ID,将这些下游路口
    ID和起点路口,终点路口按每条数据的检测时间先后,作为一个数
    组存在途经路口字段;其中,前述的MD_SEGMENT表为数字路网
    信息存储表,该表中记录了路段ID以及对应的道路上游路口与下游
    路口信息;

    步骤1-6、将步骤1-4得到的每一组分组数据都按照步骤5处理,
    所有组数据处理完毕;

    步骤1-7、对经步骤1-2剔除数据后的所有类的数据,按步骤1-3-
    步骤1-6处理,最后得到并输出每个车辆的大概轨迹数据。

    进一步的实施例中,前述步骤1-7输出的每个车辆的大概轨迹数
    据包括:车牌号、起点交叉口以及起点时间、终点交叉口以及终点时
    间、所有途经路口以及途经路口时间,其中所述的途径路口时间与路
    口一一对应。

    进一步的实施例中,前述步骤2的实现具体包括:

    步骤2-1:从每个车辆的大概轨迹数据中取出一条数据,对该数
    据的所有途经路口信息中的所有路口,从第一个开始,依次查看下一
    个路口是否为前一个路口的下游路口:若所有相邻路口的后一个路口
    都是前一个路口的下游路口,则将相应的数据保存在一跟踪数据表中;
    若存在某两个相邻的路口ID不是上下游路口关系,则将这两个ID
    中的前一个作为起点,后一个作为终点,二者时间差作为t,利用深
    度优选遍历算法求出从起点到终点,且时间不超过t*l(l为时间配置
    系数,可配置)的所有路径。从路径中找到权重最小且路径特点标记
    =1的路径作为可能路径;若不存在路径特点标记=1的路径,则直接
    找到0权重路径值最小的路径作为可能路径;

    步骤2-2、由步骤2-1补齐所有相邻2个路口不是上下游路口的
    之间的路径;

    步骤2-3:将补齐后的路径与原来的路径合并为一条路径保存在
    前述的跟踪数据表内。

    进一步的实施例中,前述时间配置系数l可调节,0.5≤l≤2。

    根据本发明的改进,还提出一种基于深度优先遍历的可达路径的
    查找装置,包括:

    用于基于电子警察过车数据获取每个车辆的大概轨迹数据的模
    块;以及

    用于依据前述所得到的每个车辆的大概轨迹数据,采用深度优先
    遍历算法进行所有可能路径的查找的???。

    应当理解,前述构思以及在下面更加详细地描述的额外构思的所
    有组合只要在这样的构思不相互矛盾的情况下都可以被视为本公开
    的发明主题的一部分。另外,所要求?;さ闹魈獾乃凶楹隙急皇游?br />本公开的发明主题的一部分。

    结合附图从下面的描述中可以更加全面地理解本发明教导的前
    述和其他方面、实施例和特征。本发明的其他附加方面例如示例性实
    施方式的特征和/或有益效果将在下面的描述中显见,或通过根据本
    发明教导的具体实施方式的实践中得知。

    附图说明

    附图不意在按比例绘制。在附图中,在各个图中示出的每个相同
    或近似相同的组成部分可以用相同的标号表示。为了清晰起见,在每
    个图中,并非每个组成部分均被标记。现在,将通过例子并参考附图
    来描述本发明的各个方面的实施例,其中:

    图1是根据本发明某些实施例的可达路径查找方法的流程示意
    图。

    图2是根据本发明某些实施例的基于电子警察数据来获得车辆
    大概轨迹数据的流程图。

    图3是根据本发明某些实施例的深度优先搜索过程的示意图。

    图4是根据本发明某些实施例的深度优先遍历递归算法的示意
    图。

    具体实施方式

    为了更了解本发明的技术内容,特举具体实施例并配合所附图式
    说明如下。

    在本公开中参照附图来描述本发明的各方面,附图中示出了许多
    说明的实施例。本公开的实施例不必定意在包括本发明的所有方面。
    应当理解,上面介绍的多种构思和实施例,以及下面更加详细地描述
    的那些构思和实施方式可以以很多方式中任意一种来实施,这是因为
    本发明所公开的构思和实施例并不限于任何实施方式。另外,本发明
    公开的一些方面可以单独使用,或者与本发明公开的其他方面的任何
    适当组合来使用。

    结合图1所示,根据本发明的某些实施例,本发明提出的基于深
    度优先遍历的可达路径的查找方法,包括:

    步骤1、基于电子警察过车数据获取每个车辆的大概轨迹数据;

    步骤2、依据步骤1所得到的每个车辆的大概轨迹数据,采用深
    度优先遍历算法进行所有可能路径的查找。

    前述的电子警察过车数据包括:路段编号、检测时间、车牌号、
    车辆类型、车牌颜色、车速以及检测设备ID,每个车辆的大概轨迹
    数据包括:车牌号、起点交叉口以及起点时间、终点交叉口以及终点
    时间、所有途经路口以及途经路口时间,其中所述的途径路口时间与
    路口一一对应。

    作为实例,这样的电子警察过车数据以及最后输出的数据,将在
    下述以图表的方式示例性地进行说明。

    在一些例子中,结合图2所示,前述步骤1的实现具体包括:

    步骤1-1、获取某一天的所有电子警察过车数据,并将所有的数
    据按车牌号分类,剔除车牌号=‘--’的这一类的所有数据,其中,
    这些电子警察过车数据包括:路段编号、检测时间、车牌号、车辆类
    型、车牌颜色、车速以及检测设备ID;

    步骤1-2、对剔除后的其余类数据,每一类数据按前述检测时间
    由小到大排序;

    步骤1-3、对某一类排序后的数据进行处理,假设共有n条数据,
    则求出相邻两个检测时间ti和ti+1的差Δti=ti+1-ti,i=1,2,…,n-1;

    步骤1-4、找到大于设定的时间阈值Tpre的所有tk+1,k≥0,并且找
    到所有对应的第k条数据和第k+1条数据;假设一共有m条数据,m≥0,
    将该类的第一条数据和最后一条数据加入,并去除重复数据后,对余
    下数据按前述检测时间排序后,将第一条和第二条数据作为一组,第
    三条和第四条数据作为一组,依次两两一组,若最后多余一条数据,
    则删除该条数据;

    步骤1-5、对步骤1-4中两两一组的数据中的某一组数据,将车
    牌号存在中间数据的车牌中,将检测时间早的数据的检测时间保存在
    中间数据的起点时间中,并由该条数据的路段ID,从MD_SEGMENT
    表中查到该路段ID的下游路口ID,保存在中间数据的起点交叉口;
    将检测时间晚的数据的检测时间保存在中间数据的终点时间中,并由
    该条数据的路段ID,从MD_SEGMENT表中查到该路段ID的下游
    路口ID,保存在中间数据的终点交叉口;找到该类中检测时间属于
    起点时间到终点时间的所有数据,由每条数据的路段ID,从
    MD_SEGMENT表中查到该路段ID的下游路口ID,将这些下游路口
    ID和起点路口,终点路口按每条数据的检测时间先后,作为一个数
    组存在途经路口字段;其中,前述的MD_SEGMENT表为数字路网
    信息存储表,该表中记录了路段ID以及对应的道路上游路口与下游
    路口信息;

    步骤1-6、将步骤1-4得到的每一组分组数据都按照步骤5处理,
    所有组数据处理完毕;

    步骤1-7、对经步骤1-2剔除数据后的所有类的数据,按步骤1-3-
    步骤1-6处理,最后得到并输出每个车辆的大概轨迹数据。

    在一些可选的例子中,前述步骤4更加包括以下步骤:

    预先设定前述的时间阈值Tpre。

    优选地,前述步骤4中的时间阈值Tpre设定为3600s。

    在一些例子中,前述步骤1-1中的电子警察过车数据,每秒钟都
    有更新数据,这些数据来源于部署在道路的各个路段的电子警察设备,
    例如高清摄像头、测速设备等。在一些可选的例子中,这些过车数据
    包括下表的内容(含存储格式)。


    结合前述步骤的处理,步骤1-7输出的每个车辆的大概轨迹数据
    包括:车牌号、起点交叉口以及起点时间、终点交叉口以及终点时间、
    所有途经路口以及途经路口时间(与途径的路口一一对应)。

    在一些例子中,这些输出的大概轨迹数据包括下表的内容(含存
    储格式)。



    可见,在只有电子警察数据而没有GPS数据的情况下,利用前
    述实施例的算法可以直接跟踪车辆的行驶轨迹,实现精确的对每个车
    辆进行轨迹跟踪。

    结合图1所示,接下来将结合前述的每个车辆的大概轨迹数据以
    及深度优先遍历算法进行可达路径的查找。

    图的深度优先遍历递归是指:

    1、假设初始状态是图的所有顶点均没有被访问,则从图的某个
    点v出发,访问此顶点,然后依次从v的未被访问的邻接点出发深度
    优先遍历图,直到所有与v有通路的顶点都被访问到。

    2、若此时图中还有未被访问的顶点,则选择该未被访问的顶点
    为起点,重复上述1中步骤,直到图中所有的顶点均被访问到。

    深度优先搜索过程是指:

    设x是当前被访问顶点,在对x做过访问标记后,选择一条从x
    出发的未检测过的边(x,y)。若发现顶点y已访问过,则重新选择另
    一条从x出发的未检测过的边,否则沿边(x,y)到达未曾访问过的y,
    对y访问并将其标记为已访问过;然后从y开始搜索,直到搜索完从
    y出发的所有路径,即访问完所有从y出发可达的顶点之后,才回溯
    到顶点x,并且再选择一条从x出发的未检测过的边。

    上述过程直至从x出发的所有边都已检测过为止。此时,若x不
    是源点,则回溯到在x之前被访问过的顶点;否则图中所有和源点有
    路径相通的顶点(即从源点可达的所有顶点)都已被访问过,若图G是
    连通图,则遍历过程结束,否则继续选择一个尚未被访问的顶点作为
    新源点,进行新的搜索过程。

    结合图3所示,前述深度优先搜索的过程包括:

    1、首先访问A点,将其标为已访问,接着从其未被访问的邻接
    点C出发继续搜索。

    2、访问C点并将其标记为已访问。依次类推,继续访问顶点
    B,G,F,D。

    3、访问D后,由于D的所有邻接点均已被访问,因此回退到上
    一个访问点F,检测其有无未被访问的邻接点。若有继续深度搜索;
    若没有,继续会退到F的上一个访问点G。

    4、由于F还有未被访问邻接点E,所以继续访问E,然后依次回
    退到F,G,B,C,A。直到访问结束。

    5、得到深度优先遍历顺序为:A,C,B,G,F,D,E。

    本例中,在以下内容所采用的基于图的深度优先遍历算法的路径
    遍历包括:

    使用邻接矩阵表示无向图,如果两个顶点之间有边,对应的邻接
    矩阵相应位置的值为1,否则为0。设置有一个变量partialPath存储
    当前这一层的已经遍历的点构成的路径。当partialPath的最后一个点
    就是终点时得到一条可行路径;返回。否则,找到partialPath中最后
    一个点的可达节点,找打这些节点中不属于partialPath路径的点。从
    这些点的第一个点开始加入partialPath后得到新的partialPath,递归
    调用遍历算法。

    结合图4所示,图的邻接矩阵:Graph

    0
    1
    1
    0
    0
    0
    0
    0
    1
    0
    0
    1
    1
    0
    0
    0
    1
    0
    0
    0
    0
    1
    1
    0
    0
    1
    0
    0
    0
    0
    0
    1
    0
    1
    0
    0
    0
    0
    0
    1
    0
    0
    1
    0
    0
    0
    1
    0
    0
    0
    1
    0
    0
    1
    0
    0
    0
    0
    0
    1
    1
    0
    0
    0

    假设我们要找出结点3到结点6的所有路径,那么,我们就设结
    点4为起点,结点7为终点。我们需要的存储结构有:一个保存路径
    的栈、一个保存已标记结点的数组,那么找到结点3到结点6的所有
    路径步骤如下:

    functionpossiablePaths=findPath(Graph,[4],7,0)

    1.找到当前路径的最后一个点4。

    2.找到从4出发的所有可达点[2,8]

    3.判断若4是终点,则得到一条路径,返回。否则

    4.从[2,8]中的第一个点开始,2不是终点,且2不在当前路径中。把
    2加入到当前路径,得[4,2]。4到2的权重=1。

    5.递归调用findPath(Graph,[4,2],7,1)。

    6.当前路径的最后一个点是2,找到从2出发的所有可达点[4,5,1]

    7.2不是终点,从[4,5,1]中找到第一个开始点4,4不是终点,但是在
    当前路径中,剔除4.

    8.第二个点5,5不是终点,也不在当前路径,将5加入当前路径,得
    到[4,2,5],2到5的权重=1

    9.递归调用findPath(Graph,[4,2,5],7,2).

    10.当前路径的最后一个点是5,找到从5出发的所有可达点[2,8]

    11.5不是终点,从[2,8]中找到第一个点2,2不是终点,但2在当前路
    径中,剔除2.

    12.第二个点8,8不是终点,也不在当前路径中,将8加入当前路径,
    得到[4,2,5,8],5到8的权重=1

    13.递归调用findPath(Graph,[4,2,5,8],7,3)

    14.当前路径最后一个点是8,找到从8出发的所有可达点[5,4]

    15.8不是终点,从[5,4]中找到第一个点5,5不是终点,但是5在当前
    路径中,剔除5

    16.第二点4,4不是终点,但是4在当前路径中,剔除4.没有其余点了。
    该次findPath(Graph,[4,2,5,8],7,3)结束,返回上一层调用。

    17.上一层中除了8没有别的点了,上一层的findPath(Graph,[4,2,
    5],7,2)结束,返回上一层调用。

    18.上一层中还有第三个点1,1不在当前路径[4,2]中,且1不是终点。
    2到1的权重=1

    19.递归调用findPath(Graph,[4,2,1],7,2)

    20.当前路径的最后一个点是1,找到1出发的所有可达点[2,3]

    21.1不是终点,从[2,3]中选第一个点2,2不是终点,但2在当前路径
    中,剔除2

    22.第二个点3,3不是终点,也不在当前路径中。1到3的权重=1

    23.递归调用findPath(Graph,[4,2,1,3],7,3)

    24.当前路径的最后一个点是3,找到3出发的所有可达点[1,6,7]

    25.3不是终点,从[1,6,7]中取第一个点1,1不是终点,但1在当前路径。
    剔除

    26.取第二个点6,6不是终点,6不在当前路径,3到6的权重=1

    27.递归调用findPath(Graph,[4,2,1,3,6],7,4)

    28.当前路径最后一个点是6,找到6的所有可达点[3,7]

    29.6不是终点,从[3,7]中选第一个点3,3不是终点,但3在当前路径
    中,剔除

    30.第二点7,7是终点,得到新的路径。从6到7的权重=1.新路径为
    4,2,1,3,6,7;权重=5.

    31.没有其余可达点,该层递归结束,返回上一层

    32.上一层还有一个点7,7是终点,找到新路径,从3到7的权重=1.
    新路径为4,2,1,3,7;权重=4.

    33.没有其余的可达点,该层递归结束,返回上一层

    34.上一层没有其余可达点,该层递归结束,返回上一层

    35.上一层没有其余可达点,该层递归结束,返回上一层

    36.该层的当前路径是[4],还有一个可达点8,把8加入到当前路径,4
    到8的权重=1

    37.递归调用findPath(Graph,[4,8],7,1)

    38.重复6到35的过程得到2条新的路径:

    4,8,5,2,1,3,7;权重=6

    4,8,5,2,1,3,6,7;权重=7

    将搜索得到的路径保存在路径结果表中:


    本实施例中,所有可能路径的查找是将其中查找最后一个点的所
    有可达点,改为从路段表MD_SEGMENT中找该点做为上游路口的
    所有下游路口点,所有的下游路口所有可达点。

    两点之间的权重:由上游路口和下游路口从MD_SEGMENT中
    找到路段ID,由路段ID和当天日期,从
    AY_RESULT_SEGMENT_AVG_SPEED中查到平均行程时间,若时
    间不是-1则,用该时间作为权重,若时间=-1,用0作为权重。
    最终数据保存在mongo中的AY_RESULT_VEHICLE_TRACK

    结合图3、图4所示,本例中,前述步骤2的实现具体包括:

    步骤2-1:从每个车辆的大概轨迹数据中取出一条数据,对该数
    据的所有途经路口信息中的所有路口,从第一个开始,依次查看下一
    个路口是否为前一个路口的下游路口:若所有相邻路口的后一个路口
    都是前一个路口的下游路口,则将相应的数据保存在一跟踪数据表中;
    若存在某两个相邻的路口ID不是上下游路口关系,则将这两个ID
    中的前一个作为起点,后一个作为终点,二者时间差作为t,利用深
    度优选遍历算法求出从起点到终点,且时间不超过t*l(l为时间配置
    系数,可配置)的所有路径。从路径中找到权重最小且路径特点标记
    =1的路径作为可能路径;若不存在路径特点标记=1的路径,则直接
    找到0权重路径值最小的路径作为可能路径;

    步骤2-2、由步骤2-1补齐所有相邻2个路口不是上下游路口的
    之间的路径;

    步骤2-3:将补齐后的路径与原来的路径合并为一条路径保存在
    前述的跟踪数据表内。

    由以上技术方案可知,本发明的方案中,依据电子警察过车数据,
    对每辆车进行分析,得到每辆车的运行轨迹,当电子警察密度足够大
    (每个路口都有正常记录的电子警察)时,可以直接得到车辆行驶轨
    迹,而不必借助GPS数据进行定位分析。当电子警察密度不够大,
    再借助于路径搜索算法,找出合理的路径。此外路径搜索算法可以用
    于直接查找地图上任意两点之间的合理可达路径,用于地图导航功能。

    虽然本发明已以较佳实施例揭露如上,然其并非用以限定本发明。
    本发明所属技术领域中具有通常知识者,在不脱离本发明的精神和范
    围内,当可作各种的更动与润饰。因此,本发明的?;し段У笔尤ɡ?br />要求书所界定者为准。

    关 键 词:
    基于 深度 优先 遍历 路径 查找 方法 装置
      专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    关于本文
    本文标题:基于深度优先遍历的可达路径的查找方法与装置.pdf
    链接地址://www.4mum.com.cn/p-5886375.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