大规模路网图下关键词覆盖最优路径查询优化

游客倾向于采用个性化的旅游路线,规划这样的路线需要综合考量路径长度、路径开销和路径覆盖的兴趣点.关键词覆盖最优路径查询(KOR)就是用于规划这样的路线的一类查询,其处理过程通常包括预处理和路径拓展.由于路网图规模的不断扩大,现有算法预处理所需内存开销急剧上升,由于内存不足,导致较大规模的路网不能处理;路径拓展搜索空间快速膨胀,应用场景可扩展性与查询实时性难以保证.针对这些问题,提出一种大规模路网图下关键词覆盖最优路径查询算法KORL.KORL在预处理阶段将路网划分为若干子图,仅保存子图内路径和子图之间路径的信息,以减小预处理所需内存.在路径拓展阶段,综合运用最小代价剪枝、近似支配剪枝、全局优先拓展和关键词顶点拓展等策略对现有算法进行优化,以高效地搜索近似最优解.采用美国各地区的路网图,在16G内存环境下进行实验,突破了现有算法只能处理顶点数不超过25K路网图的限制.实验结果表明,KORL算法具有良好的可扩展性.     

In-Route Nearest Neighbor Queries

Nearest neighbor query is one of the most important operations in spatial databases and their application domains, such as location-based services and advanced traveler information systems. This paper addresses the problem of finding the in-route nearest neighbor (IRNN) for a query object tuple which consists of a given route with a destination and a current location on it. The IRNN is a facility instance via which the detour from the original route on the way to the destination is smallest. This paper addresses four alternative solution methods. Comparisons among them are presented using an experimental framework. Extensive experiments using real road map datasets are conducted to examine the behaviors of the solutions in terms of five parameters affecting the performance. The overall experiments show that our strategy to reduce the expensive path computations to minimize the response time is reasonable. The spatial distance join-based method always shows better performance with fewer path computations compared to the recursive methods. The computation costs for all methods except the precomputed zone-based method increase with increases in the road map size and the query route length but decrease with increases in the facility density. The precomputed zone-based method shows the most efficiency when there are no updates on the road map.     

一种基于道路网络层次拓扑结构的分层路径规划算法

鉴于平面最短路径算法应用于大规模网络规划中的效率不高,而分层算法引入\"分而治之\"策略,则能有效解决此难题。为了利用分层算法进行路径规划,首先研究了分层算法的数据基础——道路网络层次拓扑结构,其涉及基于道路等级的路网分层抽象、道路数据分区组织、以区域为单位的路网层次拓扑关系模型;接着提出了一种适用于LBS(基于位置的服务)的分层路径规划算法。该算法先通过距离值判断是否切换到上一层;然后利用启发式A*算法搜索入口和出口;最后使用双向策略搜索层内两点之间的最短路径。利用现实道路网络进行的实验分析结果表明,该算法能从本质上提高大规模网络中路径规划的效率。     

基于最短描述长度的序列图像运动分割

提出了一种分两个阶段的运动估计和分割方法。首先采用小块对图像做传统全局搜索的块匹配运动估计,得到每块相应搜索范围内的误差图,根据误差图判决相邻块运动的一致性将一致性好的块合并成一个区域并同时得到区域的运动矢量。进一步的区域合并在最短描述长度准则指导下进行,每对区域合并的依据是合并后新区域的描述长度小于合并前两区域描述长度之间,如此迭代合并直至所有相邻区域均不满足条件。     

Modeling Costs of Turns in Route Planning

In this paper a model that handles costs of turns in route planning is defined, investigated and discussed. Costs are traditionally attached to edges in a graph. For some important route planning problems other costs can be identified, namely costs that appear when leaving one edge and entering the next. Examples are turn restrictions, the turning angle, or the simple necessity to turn. Such costs cannot be stored as attributes of nodes or edges in the graph, and they cannot be handled correctly by shortest path algorithms without modifications. Turn costs can be represented by a pseudo-dual graph in a way that shortest path algorithms run without modifications. Although the idea is not new, it has not found much interest in the literature. The pseudo-dual graph is defined here in a new way, it is systematically investigated, and some practical applications are shown. Concentrating strictly on topology, it turns out that the pseudo-dual graph is conceptually cleaner and more efficient in route planning than alternative, currently used ways to deal with turn costs. The discussed applications are from the field of pedestrian navigation, which gave rise to this research.     

基于改进遗传算法的国内旅行交通规划研究

人们长时间、多地点的外出旅游,需要进行合理的旅行交通规划来获得最优路径和节约成本.以在国内31个省会城市旅行为研究对象,通过查阅运输系统价格表获得各城市之间交通运输所需费用,并利用遗传算法以旅行所需总费用最少为优化目标,进行巡回路径的优化.传统遗传算法容易出现早熟现象,故对个体编码后赋予年龄操作,进行多次仿真计算和实验...     

基于信息粒度的不完备信息系统空值补齐算法

在现实世界中,不完备信息系统大量存在的,信息系统中空值的存在大大增加了信息表的不确定性,信息表无法产生更多潜在的有价值规则.处理不完备信息表的一种做法是先将空值补齐再提取规则,常用的空值补齐算法通常都是根据同属性其他值出现的频率高低估计空值,但是此方法不一定能保证规则的一致性.本文提出一种基于信息粒度的空值补齐方法GRCC,首先根据定义的信息粒度选择信息粒度最大的列,然后由相容类产生空值的属性值范围,最后利用MDL准则确定遗漏项的属性值,如此逐列进行填充直到完成全部信息表的补齐.经过实验,GRCC算法补齐的信息表比其它补齐方法产生的信息表产生更多高可信度和高支持度的规则,降低了信息表的不确定性.     

基于矢量地图数据的路径规划算法研究

分析了矢量地图数据格式的特点,在进行路网拓扑信息提取和“分层分块”存储的基础上,比较了几种常用路径搜索算法;给出一种基于多级比例尺地图模型的多比例尺启发式最优路径规划算法,并对如何提高路径规划的实效性进行了探讨。     

面向驾驶员特性的路径规划算法

合理的路径规划必须充分考虑驾驶员习惯和心理特征,交叉口延误和转弯类型(如左转、直行或右转)对驾驶员的心理感受有较大影响。为此,针对城市路网密度大、交叉口间距小的特点,对经典的A*算法进行两方面的改进：将交叉口延误引入代价函数中;引入交叉口转弯系数γ以表征驾驶员对转弯类型的心理感受,并将其加入代价函数中。算例结果表明,与原算法相比,改进后的A*算法在保证路径总时间最短的前提下能避开左转弯操作,与实际的驾驶员习惯更吻合。     

基于最小描述长度准则的数字信道化接收机频谱检测方法

数字信道化接收机常采用频谱检测方法判断其分析滤波器组中的输出子带信号的存在。为解决现有基于特征值的频谱检测方法由于采用最大和最小特征值的近似值而导致采样点数较少时性能无法满足要求的问题,提出了一种适用于数字信道化接收机的基于最小描述长度(MDL)准则的子带频谱检测方法。基于子带过采样数据构建协方差矩阵,计算矩阵特征值的平均值以减少噪声带来的波动。将矩阵特征值的平均值作为MDL准则的参数估计所有子带的平均特征值中包含信号的个数,以此确定包含信号的子带。仿真实验表明,该方法比现有的频谱检查方法具有更好的检测性能,且克服了需要设置固定门限的缺点,对噪声和信号波动具有较强的适应能力。     

基于缓存的时变道路网最短路径查询算法

作为图论中的基本操作之一,最短路径查询已被广泛应用于路径规划、GPS导航和个性化推荐等基于道路网的相关应用中.针对道路网中在线最短路径查询所面临的计算成本高、查询速度慢等问题,现有方案通常采用缓存技术来优化其性能.考虑到道路网的边权重具有频繁变化的特性,现有工作未能有效地实现缓存数据的快速更新,忽略了缓存数据的时效性,从而导致缓存命中率不高.鉴于此,首先提出一种新的缓存存储结构,能够有效平衡最短路径的整体查询速度与缓存数据更新速度之间的关系;其次,结合路径共享能力及路径多样性设计了新的缓存存储策略,优化缓存收益,继而提高缓存命中率;最后,提出基于缓存的时变最短路径查询(cache-based time-varying shortest path query, CTSPQ)算法.在真实数据集上的实验结果验证了CTSPQ算法的有效性和可扩展性.     

基于分层道路网络的新型路径规划算法

为了降低路径规划算法的搜索空间,同时使得规划的结果更加合理,提出一种分层路径规划算法．该算法利用道路网络中道路的不同等级特性对路网进行分层处理,构造分层搜索策略,达到加快路径规划速度的目的．结合路径规划算法在实时车辆导航系统中的实际应用,给出了该算法的一个应用实例．实验结果表明,该算法能将路网中任意两点间的最短路径解算时间控制在1s之内．     

Learning to Predict Non-Deterministically Generated Strings

In this article we present an algorithm that learns to predict non-deterministically generated strings. The problem of learning to predict non-deterministically generated strings was raised by Dietterich and Michalski (1986). While their objective was to give heuristic techniques that could be used to rapidly and effectively learn to predict a somewhat limited class of strings, our objective is to give an algorithm which, though impractical, is capable of learning to predict a very general class. Our algorithm is meant to provide a general framework within which heuristic techniques can be effectively employed.     

Bad:基于最小描述长度的均衡离散化方法

连续数据离散化是数据挖掘分类方法中的重要预处理过程。本文提出一种基于最小描述长度原理的均衡离散化方法,该方法基于最小描述长度理论提出一种均衡的离散化函数,很好地衡量了离散区间与分类错误之间的关系。同时,基于均衡函数提出一种有效的启发式算法,寻找最佳的断点序列。仿真结果表明,在C5.0决策树和Naive贝叶斯分类器上,提出的算法有较好的分类学习能力。     

Rudimentary结构等价性及其应用研究

Bayesian网的结构学习是Bayesian网研究的难点之一．当问题中的变量较多时,通过结构学习得到的网络结构往往不具有唯一性．文中通过对Bayesian网结构等价性的研究,提出了Rudimentary结构等价性定理,并给出了该定理的证明．该等价性定理为提高结构学习的速度和优化Bayesian网的结构提供了理论依据．实验结果表明该定理具有较好的实用价值．     

一种动态路段行程时间的预测模型

动态路段行程时问的预测是ITS动态最短路线选择的关键技术之一。根据对实际交通状况的分析,将路段行程时间分为三个部分,即自由行驶时间、排队等待时间和通过交叉 口时间。模型基于路段的基本信息及实时信息分别对这三部分时间进行预测,从而实现对整段路段行程时间的动态预测,精确度明显提高。     

最小描述长度优化下的医学图像统计形状建模

统计形状模型(SSM)是有效的图像处理与分析方法。为了建立模型,需要从形状样本集中提取出具有对应关系的轮廓采样点集合,这是决定模型性能的关键。传统的手动标定这些点集来确保对应关系枯燥耗时且带有主观性,更难以向高维拓展。对形状建立逐层的多尺度参数表示,基于最小描述长度(MDL),在粗尺度上建立反映点对应程度的目标函数并最小化,提出首先确保粗尺度上具有最优意义的点对应,同时在精尺度上使用最便捷的弧长参数函数来确定特征点,完成感兴趣目标的快速统计形状建模,进而统计分析以验证模型性能,为后续图像分割或定量分析打下基础。实验对肌肉骨骼核磁共振成像(MRI)中椎骨、椎间盘以及半月板等具有临床意义的结构建立了统计形状模型,验证了本文方法与手动取点相比具有客观可重复性且更加简洁,与单一尺度下的MDL方法相比时间效率更高。基于此模型的图像分割与基于手动建模的分割相比,误差相当或有所降低。     

基于搭配对的汉语形容词—名词聚类

本文提出了一个双向分级聚类的算法同时对不同词性的词进行聚类。在聚类过程中,不同词性的词的聚类交替进行,相互影响。我们以最小描述长度的原理为基础构造了目标函数。为了减小数据稀疏的影响,又提出了修饰度的与修正距离的概念。将此算法应用于汉语形容词- 名词的搭配对,对形容词与名词进行聚类,实验结果显示该算法是有效的。