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

    重庆时时彩胆码意思: 基于颜色索引平衡二叉树的相邻车辆的查询算法.pdf

    摘要
    申请专利号:

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

    申请日:

    2016.10.18

    公开号:

    CN106570079A

    公开日:

    2017.04.19

    当前法律状态:

    实审

    有效性:

    审中

    法律详情: 实质审查的生效IPC(主分类):G06F 17/30申请日:20161018|||公开
    IPC分类号: G06F17/30 主分类号: G06F17/30
    申请人: 电子科技大学
    发明人: 周世杰; 罗嘉庆; 贺雅琪; 黄文; 李志鹏
    地址: 611731 四川省成都市高新区(西区)西源大道2006号
    优先权:
    专利代理机构: 代理人:
    PDF完整版下载: PDF下载
    法律状态
    申请(专利)号:

    CN201610906427.7

    授权公告号:

    |||

    法律状态公告日:

    2017.05.17|||2017.04.19

    法律状态类型:

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

    摘要

    基于颜色索引平衡二叉树的相邻车辆的查询算法。本发明提出了颜色索引二叉树存储结构及基于颜色索引二叉树的邻车查询算法,该结构与平衡二叉树不同的是,还需要维护同色结点的前驱结点和后继结点的动态索引。不论是否在同一车道,两辆邻近的车辆始终保持父子关系,而结点着色又能维持同车道车辆的近邻索引。通过该算法车辆查询同车道前后相邻车辆的时间复杂度达到了O(1)、查询相邻车道的相邻车辆的时间复杂度达到了O(logn)。通过实验对本发明提出的邻车查询算法与经典的现有主流邻车查询算法进行了比较,表明本算法能够有效提高相邻车辆的查询效率。

    权利要求书

    1.提出了基于颜色索引平衡二叉树的相邻车辆的查询算法,其特征在于:采用颜色索
    引平衡二叉树的结构来存储路网中的车辆,赋予结点一个动态内部索引结构。由于平衡二
    叉树的查找时间复杂度为O(logn),可以提供较快的查询速度,同时考虑到在同一车道中的
    前后车辆有着前后相邻的关系。因此,加入了同色结点的前驱结点和后继结点的动态索引。
    不论是否在同一车道,两辆邻近的车辆始终保持父子关系,而结点着色又能维持同车道车
    辆的近邻索引。通过该索引,车辆可以在O(1)的复杂度的情况下查询同一车道前后车辆的
    信息。
    2.如权利要求1所述的基于颜色索引平衡二叉树的相邻车辆的查询算法的时间复杂
    度,具体包括相同车道前后相邻车辆的查询,左右相邻车辆的查询,车辆结点删除算法,车
    辆结点插入算法、车辆节点转移算法等,单个车辆每仿真一步所需要的平均时间由车道中
    车辆的数目、行驶方向车道的数目、车辆行驶换道率、车辆的行驶速度4个参数仿真得出。
    3.如权利要求2所述的车辆行驶换道率,是指系统的一辆车在一个仿真步中进行换道
    的概率,这与设定每个车道中车辆的数量、车道的数量、车辆的行驶速度相关。
    4.如权利要求2所述的相同车道前后相邻车辆的查询的时间复杂度为O(1),左右相邻
    车辆的查询时间复杂度为O(logn),车辆结点删除算法的时间复杂度为O(logn),车辆结点
    插入算法的时间复杂度为O(logn),车辆结点转移算法的时间复杂度为O(logn)。

    说明书

    基于颜色索引平衡二叉树的相邻车辆的查询算法

    技术领域

    本发明提出了颜色索引二叉树的存储结构,并利用该结构存储同一车道的邻近车
    辆?;谘丈饕钠胶舛媸鞯慕岬阌桑撼盗拘畔⒂?、父结点索引、左孩子索引、右孩子索
    引、动态颜色索引域组成。并提出了一个基于颜色索引二叉树的邻车查询算法,并将该结构
    和算法应用到微观交通仿真系统中,通过实验对本发明提出的邻车查询算法与经典的现有
    主流邻车查询算法进行了比较,表明本算法能够有效提高相邻车辆查询的效率。

    背景技术

    随着我国社会经济的发展以及城市的改造和扩张,国内城市机动车保有量迅速增
    长,路网状况变化节奏加快,交通拥堵日益严重。交通拥堵给市民的工作和生活带来极大的
    不便,同时交通拥堵带来的环境污染问题也越来越严重,需要大量人力财力去做统计分析
    和改造优化,由于交通情况复杂,长期的调查和测量使得信息不具有时效性,从而导致改造
    结果不甚理想。随着计算机技术的发展以及智能交通系统的大规模应用,在线交通仿真以
    其高经济性、高实时性等特点成为了评估交通规划和管理的重要方法。使用在线交通仿真
    技术,可以与真实交通管理同步,并对交通流进行模拟预测,给交通路网规划与优化、交通
    流控制等提供强有力的支持。

    在线微观交通仿真中车辆在作出行为状态的改变之前,需要获取其周围环境的数
    据。这些数据包括:交通信号灯、标识以及相关相邻车辆的状态信息,这些信息的准确高效
    的获取直接影响到整个仿真的精确性和真实性,对于一条比较长的道路,该道路上的车辆
    会出现很多的时候,特别是针对大规模在线交通仿真,当出现拥堵时,道路上的车辆会非常
    多,在此情况下如果不采用高效的车辆查询结构和算法,则会降低查询的速度从而影响到
    整个交通仿真系统的仿真效率和仿真实时性。

    发明内容

    本发明提出了基于颜色索引二叉树的存储结构,并利用该结构存储同一车道的邻
    近车辆,其中颜色索引域是一个动态结构,数量根据道路上同向车道数量来决定。该结点颜
    色索引域有三个索引结构,每个索引结构由前驱索引(Prev)和后继索引(Next)组成。该结
    点结构中,Lchild域存放在道路上行进距离比其小的车辆结点,Rchild域存放车道路上行
    进距离比其大的车辆结点。若该车辆前面没有车,则其Parent域为空。

    本发明提出了基于颜色索引二叉树的邻车查询算法,使用平衡二叉树作为基础数
    据结构,对常规平衡二叉树结点作特殊处理,赋予结点一个动态内部索引结构,既保持了二
    叉排序树在顺序查询时的优势,又有链式结构简单的结点存储方式。通过该算法车辆查询
    同车道前后相邻车辆的时间复杂度达到了O(1)、查询相邻车道的相邻车辆的时间复杂度达
    到了O(logn)。该算法运用在在线微观交通仿真平台的相邻车辆的查询中,取得了较好的效
    果。

    通过实验对本发明提出的基于颜色索引二叉树的邻车查询算法和现有微观交通
    仿真中的邻车查询算法在四种不同条件下进行了比较,设定的不同条件分别为:路网中车
    流量不同、车辆换道比例不同、车辆速度不同、路段中车道数不同。结果表明基于颜色索引
    二叉树结构的查询算法能够提高系统的仿真效率和实时性。进一步分析,在规模较大的仿
    真中本算法多数情况优于其他算法。

    附图说明

    图1常见交通场景;

    图2基于颜色索引二叉树结点数据结构;

    图3车辆位置关系图;

    图4按序列插入构建颜色索引二叉树过程;

    图5完整的颜色索引二叉树结构。

    具体实施方式

    下面结合附图对本发明的技术方案作详细说明。

    以一个基础交通场景为例,该场景描述了一个车辆(Query)在尝试进行状态改变
    (加速、换道)之前,发起的邻车查询操作。路段中共8辆车,当目标车辆(Query)需要加速时,
    车辆(Query)将会发起查询其直接前驱车辆的请求,即向前找到车辆E,根据车辆E的状态,
    判断是否可以加速,即在一个仿真周期中不会发生碰撞。当目标车辆(Query)需要向左(车
    道3)或向右(车道1)换道时,车辆(Query)需要分别查询车辆A、车辆B或车辆F、车辆G的行驶
    状态,借此判断是否能够换道,如图1所示。

    基于颜色索引的平衡二叉树的结点将由:车辆信息域(Vehicle Info)、父结点索
    引(Parent)、左孩子索引(Lchild)、右孩子索引(Rchild)、动态颜色索引域(Color Index),
    如图2所示。其中颜色索引域是一个动态结构,数量根据道路上同向车道数量来决定,由于
    以图1场景为例,可以看见该结点颜色索引域有三个索引结构,每个索引结构由前驱索引
    (Prev)和后继索引(Next)组成。该结点结构中,Lchild域存放在道路上行进距离比其小的
    车辆结点,Rchild域存放车道路上行进距离比其大的车辆结点。若该车辆前面没有车,则其
    Parent域为空。若将图1场景中车辆按距离映射到一维,可以更加直观的看出车辆位置之间
    的关系,如图3所示。

    按照车辆已经走过的距离排序,可以得到序列(车辆E、车辆H、车辆B、车辆G、车辆
    Query、车辆F、车辆A、车辆C)。下面构建颜色索引二叉树,以下简称CIAVL,该树的构建与经
    典普通二叉树构建过程相似,结点的Lchild域存储关键字小的结点,Rchild域存储关键大
    的结点。该过程与平衡二叉树构建不同的是,还需要维护同色结点的前驱结点和后继结点
    的动态索引结构。假设颜色索引二叉树构建过程按上述顺序插入,构建过程如图4所示。最
    终,待车辆A和车辆C插入该树后,可得到完整的基于颜色索引的平衡二叉树结构,红色箭头
    表示颜色相同结点的前驱后继关系,如图5所示。

    关 键 词:
    基于 颜色 索引 平衡 二叉 相邻 车辆 查询 算法
      专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    关于本文
    本文标题:基于颜色索引平衡二叉树的相邻车辆的查询算法.pdf
    链接地址://www.4mum.com.cn/p-6092739.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