【摘 要】
:
随着现代科学技术的不断进步,基于位置的服务已经与我们的日常生活形成了密不可分的关系。路径规划是基于位置服务中最重要的功能之一,它对资源分配,行车路线规划,交通拥堵的缓解有着重要的作用。给定一个起始节点,目标节点,寻找一条最小代价的路径被称为最短路径查询。不同于传统的最短路径查询算法,标签约束最短路径查询在用户指定的道路类型的条件下找到一条最短路径。但是,现有的关于标签约束最短路径查询的算法较少,而
论文部分内容阅读
随着现代科学技术的不断进步,基于位置的服务已经与我们的日常生活形成了密不可分的关系。路径规划是基于位置服务中最重要的功能之一,它对资源分配,行车路线规划,交通拥堵的缓解有着重要的作用。给定一个起始节点,目标节点,寻找一条最小代价的路径被称为最短路径查询。不同于传统的最短路径查询算法,标签约束最短路径查询在用户指定的道路类型的条件下找到一条最短路径。但是,现有的关于标签约束最短路径查询的算法较少,而且存在的一定的不足,不能够在大型路网数据集中进行高效的查询。基于上述所存在的问题,本文提出了标签约束最短路径的查询算法,并在现实生活中选取了六个不同城市路网的真实数据集,执行了大量的实验,最终证明了本文所提出的算法的高效性。具体地,本文的主要贡献包括如下几个部分:(1)提出了一个基于网格的索引GBPI,根据划分的网格对部分节点之间的路径进行存储,同时对网格中的标签类型进行划分,使得查找过程中可以快速判断节点之间是否可以根据指定的标签到达。(2)提出了一个基础的标签约束最短路径查询算法BLCSP(Basic Label Constrained Shortest Path Query)。算法以给定的起始点为中心,在约束条件下不断的对外进行拓展。在拓展的过程中,计算当前节点到目的节点的直线距离,从而给算法规定了一个拓展的方向,避免访问部分无关节点,加速查询效率。(3)在BLCSP算法的基础上提出了改进的标签约束最短路径查询算法ILCSP(Improved Label Constrained Shortest Path Query)。该方法主要包括格间约束最短路径查找和标签约束最短路径调整两个过程。首先,根据GBPI索引找到一条从起始节点到目标节点的满足网格间约束的最短路径,这条路径由网格内部不考虑约束的最短路径和网格间的标签约束路径组成。之后在调整过程中,对网格内部不符合给定标签类型的路径进行微调,得到算法最终所需的精确路径。(4)进行了详细的对比实验,证明了本文提出的两个算法的高效性,相比于当前最优的算法EDP,基础算法BLCSP和提高算法ILCSP在六个真实数据集中的查询时间分别比EDP加快了12%~17%和20%~22%。
其他文献
区块链是一种集P2P网络、分布式存储、加密算法、共识机制等多种计算机技术于一体的分布式账本,具有去中心化、可溯源、不可篡改等特点。然而,面对强大的应用需求,区块链技术的可扩展性就成为当今亟待攻关的核心技术难题。为此,研究者们提出了很多解决方案,其中分片技术是实现链上扩容最可行的解决方案,也是目前研究的热点。为扩容而引入的分片技术,又带来了新的挑战,其中之一就是跨分片交易。因此,状态分片下处理好复杂
随着空中交通和空域使用量的增加,导致航空网络出现拥挤、航班延误等问题。各种动态的恶劣天气对飞行安全构成极大威胁,同时也是导致航班延误的主要原因。因此,避开恶劣天气区域对飞行安全是至关重要的。此外,在空域中存在一些静态限制区域,被称为限制区、危险区、禁飞区,统称为“三区”,为了飞行安全也需要避开它们。在避开恶劣天气和“三区”的同时寻找一条安全有效的航线成为再规划航线需要解决的问题。为此,我们做了以下
膝关节软骨局部性缺损是一种严重的骨关节炎疾病,膝关节软骨局部性缺损的程度不同,也会使软骨病灶区域的形态、体积和表面积不同。因此,对膝关节软骨缺损区域进行量化,可辅助医生制定手术方案。MRI图像的组织分辨率良好,可使组织及病变成像,是诊断骨关节炎的主要成像方式。但是在膝关节MRI图像中骨头与软骨和周围肌肉、韧带等组织的对比度低,不能有效的分割目标组织和背景;而且缺损病灶目标小且受周围组织影响,分割时
水下图像退化是水下成像普遍存在的问题,主要有两方面原因:第一,水中的悬浮粒子会造成水体的通透性变差,使得水下场景的反射光在到达相机之前会被悬浮的粒子吸收和散射,从而使生成的水下图像呈现对比度低和模糊现象。第二,当光在水中传播时,不同颜色光会因水的吸收和散射效应而呈指数衰减,造成不同程度的颜色失真。这种退化的水下图像严重影响了水下相关工作的开展。为了解决水下图像颜色失真、对比度低和模糊的问题,本文主
随着网络信息技术的飞速发展,用户评论内容的爆炸性增加,使得文本分类和整理工作变得越来越重要。面对海量的用户评论数据,只依靠单纯的传统技术进行计算和大数据分析已经无法解决实际应用的问题。因此,本文基于深度学习技术,利用双向门控循环单元和卷积神经网络的联合网络模型,提出了针对句子级文本情感分析和方面级文本情感分析的改进方案。针对句子级文本情感分析,本文构建了融合文本去噪和分段池化的句子级情感分析模型。
随着深度学习技术的快速发展,大量敏感的数据被用于神经网络模型的训练。因此,如何有效确保训练数据集的隐私性面临着严峻的挑战。本文针对深度学习模型的成员推理攻击和防御问题展开研究。通过执行成员推理攻击,攻击者可以推断出特定的数据记录是否在目标模型的训练数据集中。目前,现有的攻击方法大多假设攻击者拥有大量与目标模型训练集分布相同的数据样本,攻击者以这些背景知识为前提执行成员推理攻击。然而,在现实场景下,
随着通信技术和移动互联网的发展,数字图像也逐渐成为重要的数据载体。如何确保信息的安全传输,是一个严峻而紧迫的挑战。因此,结合不同混沌系统的图像加密算法逐渐成为了研究热点。由于时空混沌系统具有较大的参数空间,产生的混沌序列较多,混沌性强等优点,所以结合时空混沌的图像加密算法被越来越多的研究者提出。但是,经典的耦合映射格子(Coupled map lattice,CML)由于采用固定相邻的耦合方式以及