基于路网的路径查询问题的研究

38/392基于路网的路径查询问题的研究1引言1.1研究背景随着经济和技术的飞速发展，越来越多的人们购置私家车作为交通工具。这大大提高了人们出行的自主性和舒适度。人们不再局限于公共交通的时间和空间限制，可以自由选择出行时间和路线。与此同时道路设施也在迅猛发展中，用以保障人们出行的畅通并且为人们出行提供多重选择。庞大繁复的城市道路系统和多变的路况情况使得地图应用成为人们日常生活中非常重要的服务与应用。在地图服务中，不同的用户对于路径有着不同的要求。随着路径查询问题研究的不断深入，解决各种路径查询问题的新算法不断涌现。在线地图应用和基于位置的服务（LBS：locationbasedservices）的迅猛发展，使得地图上的信息进一步丰富。人们可以通过移动设备的GPS定位对生活中的建筑和商店信息加入到地图应用中，如百度旅游，大众点评网等等。这些基于用户的兴趣点信息（PoI：PointofInterest）的丰富使得之前一度被忽略的基于关键字的路径查询问题再次获得了研究者的青睐，有了进一步的进展。这种查询与普通路径查询的不同在于用户可以通过关键字说明他们对于路径的兴趣点。基于关键字的路径查询问题不断细化出各种变种，解决各种变种问题的新算法也层出不穷。然而，城市交通的发展中的一个新的问题是由于汽车的井喷式增长城市的交通拥堵情况日益严重，人们常常并不能根据地图应用规划的最短路径按时到达指定终点，大大降低了人们的出行舒适度。智能交通（ITS：IntelligentTransportSystem）被公认为是解决交通拥堵问题的重要手段。目前大部分大中城市在高速路段的各个路段设有线圈测速以及事件记录装置。基于这些历史数据有越来越多的研究致力于改善人们的出行质量。研究包括对车辆进行实时导航，为用户进行出行前的路径查询和对路径的时间进行估计预测等等。1.2研究内容基于关键字的路径查询问题研究的经典问题为空间数据库中的TPQ问题（TripPlanQuery）。在TPQ问题（TripPlanQuery）中，用户可以指定一组关键字，TPQ搜索从起始点到终点最短的覆盖所有关键字的路径。这是一个NP难问题。OSR（OptimalSequencedRoute）查询用以找到一条以某一顺序经过某些给定节点的路径，这条路径使他行走的距离或者花费的时间最短。和TPQ问题同时的MTNN（Multi-typeNearestNeighbor）查询提出了解决问题解决的精确算法。基于OSR查询的MSPSR（Multi-rulePartialSequencedRoute）查询可以个性化指定一些顺序的要求，如先经过加油站再经过咖啡馆和电影院而不要求经过咖啡馆和电影院的顺序。考虑到用户输入关键字有时与相应PoI上的关键字不同的情况，文献[]提出了MARK（Multi-appropriate-keyword）查询。文献[]提出的KOR（Keyword-awareoptimalroute）查询可以找到一条覆盖用户指定关键字，满足预算条件（比如，时间，花费）并使得总共的受欢迎程度最高。Skyline查询是找到至少有一个属性优于其他所有元素的skyline对象。即Skyline查询是找到不能被其他对象支配的对象。这在数据库中有着广泛的应用。如，Branch-and-BoundSkyline算法是一个Skyline查询中的渐进最优算法。文献[]研究了如何找到不被到查询起点的距离和到已有路径的迂回路径长度支配的兴趣点。文献[]提出了两个空间Skyline查询算法，基于R树的BS和基于Voronoi图的VS。MPP（Multi-preferencePathPlanning）问题是基于路网的路径Skyline查询，属性包括距离，行驶时间，路过的交通灯等等。在路网上的多目标优化路径查询研究中，优化目标为边上的不同参数，如花费，长度，时间和可信度等等[]。MSPP（Multi-objectiveShortestPathProblem）研究路网上不被支配的路径，也称为ParetoPath。意为对于查询结果的对象如果不降低其中一个对象的任何一个参数那么就不能得到另外一个处于查询结果的对象。这被证明在最坏情况下可能有指数级个数的解[]。标号算法研究了这个问题的精确全集解[]。算法基于路段排名[]和Mote算法[]。MSPP是一个总和最优或者最小值最大的优化问题。智能交通系统包括车辆控制系统、交通监控系统、运营车辆高度管理系统和旅行信息系统等。研究包括基于实时数据和定位的车辆导航、基于历史数据和实时数据通过预测的车辆导航、基于动态网络的最短路径算法的改进与近似。基于实时数据和定位的车辆导航通过汽车定位、实时路况信息和用户输入的终点给出一条最短路径。文献[]基于历史数据进行多步时间预测和动态Dijkstra最短路径算法求得由起始位置到终点的动态最短路径，并且在车辆行进过程中对路径进行修正。1.3本文工作本文从两个方面进行研究即基于关键字的支配路径查询问题的研究和基于短时交通预测的动态路径查询问题的研究本文提出一种带关键字的、多查询点的空间査询,叫带关键字的聚集路径查询,是一类空间关键字的匹配查询。本文分布从多路径与树结构的角度出发定义了该查询。与其他空间关键字查询不一样,该查询关注多用户的行程规划。带关键字的聚柴路径查询问题是NP-hard。为了获取查询结果,本文提出一种基于树状索引的精确算法。该精确算法需要重复进行查找分配和任务完成两个阶段的工作。查找分配阶段的主要工作有三点:获取聚集点、确定候选任务点集合、给查询点分配任务。查找分配阶段首选通过增量式算法按序获取聚集点,避免访问不必要的点。为了减少任务点集的大小,算法使用了椭圆范围查询确定候选点。本文根据最小包围矩形与椭圆的关系改进了椭圆范围查询的算法。接下来,算法开始迭代式给查询点分配相应的任务。为了加快査询处理,查找分配阶段始终维护着结果的上下界。到任务完成阶段时,精确算法使用一种启发式的算法,利用最小堆维护拓展的路径。通过动态规划的方法维护一张路径的表格,算法减少了最小堆的大小并且过滤了不必要的路径。利用空间换取时间的方法,算法保存得到的最优路径以减少重复的查询。接下来,本文验证了精确算法的正确性。对于查询点或者关键字个数庞大的情况下,精确算法难以在可接受时间内返回结果。针对这种情况,本文提出了查询的近似算法。基于中心分配的算法考虑到用户聚集的地点通常距离其中心点很近,可以在中心点附近顺便完成任务。该算法主要使用基础的查询算法,因此速度非常快。而扩展树算法则基于查询的另外一种关于树的定义方式,在结果偏差率中有较稳定的表现。为了避免聚集点选错后影响结果偏差率,本文还分别对两个近似算法进行拓展。最后,本文使用了真实数据集验证了算法的效率。1.4文章结构本文一共分成6章,内容与章节安排如下：第1章“引言”,该部分介绍空间关键字查询的背景知识,还有空间关键字查询的研究内容,并介绍了本文的主要工作内容。第2章“相关工作”,该部分首先介绍了传统的数据库的主要索引技术,例如R-tree、kd-tree,和一些预处理技术,比如Voronoi图、TEDI树,还有传统空间查询,比如最近查询、聚集最近邻查询等。接下来,该部分介绍了空间关键字查询的索引技术,如R2-tree、IR-tree等,还有一些空间关键字匹配查询还有排序查询。第3章“背景知识”,该部分首先引入了多关键的路径查询,说明了研究精确关键字匹配的目的所在。接着正式介绍了本文所研究的主要问题-带关键字的聚集路径查询问题,给出了该问题的两种定义方式,最后证明了该问题是NP-hard的。第6章“总结与展望”,该部分总结了本文的主要工作与成果,并给出了下一步的主要工作。

2支配路径查询问题研究2.1相关工作在基于关键字的路径查询问题的变种中，研究比较成熟的主要有TPQ、OSR、KOR等问题，这些变种的定义与性质不尽相同，适用的算法也不一样。下面分别论述TPQ、OSR和KOR问题以及解决每类变种的算法。2.1.1TPQ问题概述在TPQ问题（TripPlanQuery）中，用户可以指定一组关键字，TPQ搜索从起始点到终点最短的覆盖所有关键字的路径。TPQ的概念最早诞生于空间数据库领域。近几十年，空间数据库受到各大数据库生产厂商与科研机构的追捧，大量科研人员对其进行了深入研究。在这一研究热潮中，大量新的数据模型、空间索引技术和查询处理基础等新技术不断涌现。然而，这些新的索引以及查询技术往往仅限于简单的维度，大部分都可以视为最近邻查询或者其变种，这些技术无法满足新的现实空间模型以及新型空间数据库发展的需求。TPQ即诞生于此背景之下。TPQ概念如下：假定一个数据库存储的是各种空间对象的位置信息，这些位置信息都取自一个固定的类别集合C。指定空间中的任意两点（起点S和终点T）、类别集合C的一个子集R，TPQ的目标是查询自起点S出发，经过R集合中的所有点并最终到达终点T的最优路径。比如复旦大学的一名学生计划从复旦大学张江校区去往复旦大学杨浦校区，他希望途中经过一个理发店理发、一个餐馆吃饭和一个书店买书。针对这一特定场景，TPQ会输出起点为复旦大学张江校区，终点为复旦大学杨浦校区，途经理发店、餐馆和书店的最优路径。当然，最优不同最优路径标准的不同可能会导致最终输出路径的不同，比如最短距离路径或者最短时间路径。TPQ查询问题可以被视为旅行售货员（TSP）问题的一般化。由于TSP问题是NP难的，TSP问题又可以规约为TPQ查询问题，所以TPQ查询问题也是NP难的。TSP问题向TPQ查询问题规约的过程如下：假定每个类别只包含唯一的一个点，TSP问题约定遍历所有的点，由于每个类别只包含一个点，此时TSP问题等价于约定遍历所有的类别，显然满足TPQ问题的约定条件，TSP问题是TPQ问题的特例。TPQ问题类似连续最近邻查询问题，然而，用于解决连续最近邻查询问题的算法并不能产生很好的TPQ路径。专门处理TPQ问题的算法研究工作非常必要。由于TPQ查询问题是NP难的，不存在多项式复杂度之内的算法，有效地解决TPQ查询问题主要依靠近似算法，近似比率的依据主要是类别的数量m和类别的最大维度p，因此TPQ查询问题的近似算法主要包括基于类别数量m的近似算法和机遇类别最大维度p的近似算法。基于类别数量m的近似算法主要有最近邻算法（ANN）和最小距离算法（AMD）。最近邻算法的思想非常简单，从起点开始，每次访问距离当前已经访问节点最近的类别中的邻居节点，并且保证该最近邻居节点尚未被访问。形式化定义如下：给定部分路径Tk,(k<m)，Tk+1是通过访问距离当前节点vtk最近的尚未被访问过的类别中的节点vtk+1获得的。最终，最近邻算法将重点加入路径中。最小距离算法分两阶段来进行，第一阶段选取一个节点集合{v1,…vm}，每个类别取且仅取一个节点，并且保证取得的节点是该类别中保证开销c(S,vi)+c(vi,E)最小的那个节点。第二阶段以最近邻顺序来遍历第一阶段选取的节点集合，生成一条从起点E到终点E并经过每个类别中一个节点的路径。基于类别最大维度p的近似算法是一种线性规划算法。假定TPQ问题约定起点S和终点E相同，并把新的问题称为循环TPQ问题，即LTPQ问题。传统TPQ问题可以通过添加添加仅包含终点E的类别来转化为循环TPQ问题，如果可以找到解决循环TPQ问题的线性规划算法，那最终也可以通过该算法的变种来解决TPQ问题。令A=(aji)为给定图G的m*(n+1)矩阵，行m代表类别的数量，列n+1代表节点数量。矩阵A中的元素以如下顺序来安排：如果vi属于类别Rj，则aji=1，否则aji=0。在这种条件下，显然每个类别最多包含p个节点。当节点v在某一给定的路径中时，令示性函数y(v)=1，否则令y(v)=0。同理，当边e在某一给定的路径中时，令示性函数x(e)=1，否则令x(e)=0。对于任何集合S，S是V的子集，令delta(S)为割（S，V\S）中的边的集合，则LTPQ问题的线性约束如下： 在此约束条件之下，求得令取最小值的解即可解决LTPQ问题。一旦解决了LTPQ问题，自然就可以解决传统TPQ问题。2.1.2OSR问题概述 最近邻查询只在找到距离给定点最近的邻居节点，比如查询距离某人所处位置最近的饭店、书店等等。最近邻查询的重要性显而易见，然而，更多时候用户更关心的是能不能找到一条以某一顺序经过某些给定节点的路径，这条路径使他行走的距离或者花费的时间最短。此类查询不仅在导航系统、在线地图服务等应用甚广，在只能防御系统等要求快速响应的系统中也有重要应用。 假定以如下顺序驾车穿过一个城镇：第一步离开车库前往加油站给汽车加油，第二步前往书店买一本需求已久的书，最后一步前往邮局邮递一个包裹。当然，每个驾驶员都希望途经这些目的地所行驶的距离最短或者花费的时间最短。换句话说，要找到一条经过加油站、书店、邮局的路径，这条路径的距离或者花费的时间最短。寻找此类路径的问题即OSR查询问题。 OSR查询问题的算法主要分为基于向量空间的算法和基于矩阵空间的算法，最基本的算法为基于Dijkstra的算法。假设在给定起点p，顺序M和节点集合{Um1,Um2…Umn}的网络中做OSR查询。首先根据给定的网络构建一个加权有向图G，图G的节点集合，图G的边按如下规则生成：起点p有指向集合Um1中所有点的边，对于1<=i<m-1，任意Umi集合中的点都有指向Umi+1集合中的所有点的边，如图：图G中每条边的权重是根据连接该边的两个节点之间的距离来分配的，该图其实枚举了在给定顺序M和集合U的条件下所有可能的路径。根据OSR的定义，OSR路径其实是使得开销最小的那条路径。具体到图G而言，OSR查询其实就是查询从起点p到集合Umm中所有节点的最短路径，返回所有路径中开销最短的路径即可。Dijkstra算法可以找到起点p到集合Umm中所有节点的最短路径，辅之以线性复杂度的搜索算法即可找到所有路径中开销最短的一条，即OSR路径。2.1.3KOR问题概述KOR（Keyword-awareOptimalRoute）查询为了提高用户在查询中的灵活性，可以找到一条覆盖用户指定关键字，满足预算条件（比如，时间，花费）并使得总共的受欢迎程度最高。比如，可以通过KOR查询查找一条经过电影院和书店的不超过3小时的最受欢迎的路径。其中每个PoI（Pointofinterest）都有一个自己的用户评分，来源可以是TripAdvisor，FourSquare等等。KOR查询问题是NP难问题，不存在多项式时间复杂度之内的精确算法。暴力搜索解空间可以解决KOR查询问题，但是其时间复杂度为指数级，在实际应用中价值甚微。要想在合理的时间限制之内解决KOR查询问题，只能依靠近似算法。近似算法的思想很简单，大都是以当前所获路径为基础，根据近似策略选取剩余节点中最适合的节点作为下一节点，将这一节点添加到路径中，直到终点也被添加到路径中。不同的近似算法往往具有不同的精度和效率。一般而言，近似算法相对查询空间的偏差越大，算法的效率越高，但是所获结果的精度越低；近似算法相对查询空间的偏差越小，所获结果的精度越高，但是算法的效率越低。在实际应用中，必须权衡算法的精度和效率，针对特定的需求选择特定的近似算法。KOR查询问题是NP难问题，不存在多项式时间复杂度之内的精确算法。暴力搜索解空间可以解决KOR查询问题，但是其时间复杂度为指数级，在实际应用中价值甚微。要想在合理的时间限制之内解决KOR查询问题，只能依靠近似算法。近似算法的思想很简单，大都是以当前所获路径为基础，根据近似策略选取剩余节点中最适合的节点作为下一节点，将这一节点添加到路径中，直到终点也被添加到路径中。不同的近似算法往往具有不同的精度和效率。一般而言，近似算法相对查询空间的偏差越大，算法的效率越高，但是所获结果的精度越低；近似算法相对查询空间的偏差越小，所获结果的精度越高，但是算法的效率越低。在实际应用中，必须权衡算法的精度和效率，针对特定的需求选择特定的近似算法。KOR查询问题是NP难问题，不存在多项式时间复杂度之内的精确算法。暴力搜索解空间可以解决KOR查询问题，但是其时间复杂度为指数级，在实际应用中价值甚微。要想在合理的时间限制之内解决KOR查询问题，只能依靠近似算法。近似算法的思想很简单，大都是以当前所获路径为基础，根据近似策略选取剩余节点中最适合的节点作为下一节点，将这一节点添加到路径中，直到终点也被添加到路径中。不同的近似算法往往具有不同的精度和效率。一般而言，近似算法相对查询空间的偏差越大，算法的效率越高，但是所获结果的精度越低；近似算法相对查询空间的偏差越小，所获结果的精度越高，但是算法的效率越低。在实际应用中，必须权衡算法的精度和效率，针对特定的需求选择特定的近似算法。2.2KDR查询2.2.1引言一个KOR查询只返回将所有关键字的重要程度同样对待的一条路径。然而，用户可能有着对于关键字不同的重视程度。比如一个用户可能认为电影院的受欢迎程度更重要，而另外的一个用户认为书店的评分更重要。KOR查询不能个性化对待不同的用户。假设用户想要找到一条“从所住宾馆到机场，经过电影院，咖啡馆和书店的一条行程时间不超过6个小时”的路径，并且希望所经过的电影院咖啡馆和书店在大众点评上评分较高。图一：找到从s到t的个性化偏好路径如图所示，s和t表示起始点和目的的。每个结点上的数字表示大众点评上的评分。每条实线上的数字表示这条路径需要的时间。结点的不同形状代表他们不同的关键字，即不同类型的店铺。从上一个需求来看，路径查询的要求是：始于s，目的地是t，经过电影院，咖啡馆和书店。这里有三条路径，route1,2,3均满足这些必要条件。如果这个用户更重视书店的评分，Route2对她来说是最好的选择。如果用户相比于书店更重视咖啡馆，Route3则更好。然而，KOR查询只会返回Route2作为最优路径。为了解决这个问题，一个直接的解决方法是要求用户是输入每个关键字的权重。但是，这样降低了用户友好型，因为偏好本身并不容易被直接量化。另外一种解决方法是，找到用户可能想要的所有路径，如找到Route2和route3作为最终的结果。这样用户可以根据自己的喜好在结果在进行进一步的选择。这是一种新型的路径查询方法，我们称之为支配路径查询（keyword-awaredominantroute）。支配路径查询的定义是（1）可行路径需要满足要求的起始结点和目的节点，经过制定的关键字，不超过该制定的预算限制。（2）在所有的可行路径中，KDR返回其中的一个支配路径的子集，即子集中的任何一条路径不被剩余的可行路径所支配。这样，可以保证用户需要的路径一定在此子集中。与KOR问题类似，KDR也是NP难问题。对于KDR问题，具体以精确算法DR和启发式算法FDR进行实现并实验验证。2.2.2支配路径查询定义我们使用有向图表示路网[1]，其中V表示结点的集合，即PoI。表示边的集合。虽然本文中G为有向图，但是可以通过简单的更改适应于无向图中。边E表示两个结点的一条直接的路径，其中从到的路径表示为。表示这条路径的预算值，如时间花费，路径长度。路径表示顺序经过到的一条路径。路径R的预算值BS定义为R上所有边上的预算分数的总和，即 每一个结点表示一个包含关键字集合（）的结点，包含一个评分表示该结点的受欢迎程度。路径R覆盖的关键字集合可以表示为一个KDR（Keyword-awareDominantRoute）查询可以表示为一个四元组Q=(s,t,,)，其中s为源点，t是目标点，为关键字集合，是预算值限制。我们用Rs,t表示从s到t点的所有路径的集合。如果一条路径属于Rs,t并且预算值小于预算值限制，覆盖了所有指定的关键字，我们可以将其视为一条可行路径，可行路径的集合使用表示。为了定义基于关键字的路径支配，先进行目标向量的定义。定义一：目标向量给定一条路径和一个关键字集合,的目标向量表示针对于的路径评分。路径R的目标向量的每一项表示每一个关键字覆盖的R上的结点对应的最大目标值，即,，其中表示查询关键字集合的大小,表示根据字母序的第i个关键字。图：路网G如图所示，这是一个路网示例图G，其中有五种关键字，t1,t2,……t5，每个用不同的形状代表。为了简化，每个节点有一个关键字和一个评分（标示与每个结点旁边的括号中）。每条边上有一个数字标示这段路径的预算值。则对于和有和。定义二：可行路径间的支配关系给定一个KDR查询，可行路径和的目标向量分别为和。我们认为被支配（）如果1)对所有成立并且存在使得；或者2)构成和的目标向量的结点是相同的，即和相同，并且。KDR查询是在可行路径中筛选支配路径。定义三：已知关键字的支配路径给定一个KDR查询,支配路径满足不存在且的可行路径。我们用表示查询Q对应的支配路径集合，同样的，被支配的路径集合使用表示。如图所示，给定一个KDR查询，支配路径为和。其中目标向量和，预算值分别为和。证明：KDR问题是NP难问题这个问题可以从GTSP（generalizedtravelingsalesmanproblem）问题推导得到。其中GTSP属于NP难问题。GTSP问题是从起始点到终点找到一条经过了所有组的路径，其中所有的结点都被分组。如果我们将KDR问题中的结点评分设为一个固定值，则这个问题就被转化为GTSP问题。故而KDR问题是NP难问题。2.3DR算法传统的路径查询算法一般基于深度优先遍历和广度优先遍历。从初始结点出发，不停的在路径的末端增加相邻的结点，直到到达终点。经过所有的遍历之后，从所有的可行路径中选出支配路径作为最终的结果。然而，这种查询对于路网对应的图而言计算量太大，时间和空间复杂度太高。为了在保证准确性的情况下，降低算法的时间和空间复杂度，KDR问题可以用一种新的方案解决，我们称之为DR算法。在DR算法中，初始的路径为从初始结点到终点的最短路径，再不停的向路径中添加带有关键字的结点从而得到最终的支配路径。下面在介绍DR算法之前，先进行一些必要的定义。定义四：关键字结点给定一个KDR查询,我们用表示对应的关键字集合，中的每一个结点被称为一个关键字结点。每一条路径可以用关键字结点分割为小段。比如，中为关键字结点，可以被分为和。定义五：关键字结点路径给定一个KDR查询,关键字结点集合为,如果一条路径被其关键字结点分割后的子路径均为从其起始结点到终点的最短路径，我们称之为关键字结点路径。中所有的关键字结点路径组成一个集合我们使用表示。如果一条路径为支配路径，那么很明显，这一条路径一定是一条关键字结点路径。如果一条关键字结点路径所经过的关键字结点是确定的，那么这条路径是确定的。比如，路径可以被表示为关键字结点序列(KN-sequence)。定义六：潜在路径如果一条路径满足,and，那么这条路径可以被称为一条潜在路径。我们用表示从到的最短路径。对于一个关键字路径R，其关键字结点序列为，其关键字结点序列预算值可以计算为目标向量为：,关键字结点序列KS的预算值是序列中所有连续的两个结点的最短距离的总和，和R的预算值相等。KS的目标向量的计算方法和R类似。如，给定一个KDR查询，是一条对应着关键字序列为初始路径。其中对应着关键字序列为的路径的目标向量为。定义七：路径修正操作我们使用路径修正操作来将关键字结点插入到关键字结点路径R中，通过调整已有的关键字结点的顺序来得到最小的预算分数。对于一条属于KR的路径且关键字结点序列为和关键字结点v,,,，(=0表示结点)经过一些路径修正操作，一个潜在路径R可能成为一个可行路径。定义八：潜在路径祖先对于属于KR的路径和,如果，则我们认为路径是的父母路径如果可以由通过一系列的路径修正操作得到，即,，我们认为是的祖先路径。给定一个KDR查询,最终提供的结果路径必须覆盖所有的关键字。最初的路径的关键字结点序列由初始结点和结束结点构成，然后不停的添加关键字结点到路径中直至覆盖到所有的关键字。在插入关键字结点的过程中，我们暂时不考虑两个相邻的关键字结点中间经过的结点（两点间的最短路径）。在得到支配路径的关键字结点序列之后，我们使用最短路径算法算出相邻结点间的最短路径[4]。为了减少路径修正的计算量，我们找到了几个有效的剪枝策略。（a）剪枝策略一KDR问题的一个约束是预算限制——如果一条路径的预算分数超出了预算限制，那么这条路径需要被删除并且不能够继续进行修正因为他的子孙路径一定也违背了这个要求，证明如下。证明：如果且,则.将路径和的关键字结点序列分别表示为和。因为是经过的最短路径。路径（）满足。的预算分数可以计算为由此可得（b）剪枝策略二在一些特定的情况下，一个潜在路径可以被可行路径剪枝。如果这个潜在路径已匹配关键字部分对应的目标向量被对应的可行路径支配，且此可行路径在未匹配关键字部分对应的目标向量是全图最大值。对于一个潜在路径,如果存在可行路径使得在上，且对于是全图最大值,那么被支配。基于这些策略的DR算法伪代码见下图。在DR算法中，首先新建一个以关键字结点序列为元的队列Q，向队列Q插入关键字结点序列。然和，当Q不为空的时候，不断的从Q中提取潜在路径并且用一个没有被覆盖的关键字的相应结点插入到序列中（6-9行）。如果这条新的路径满足预算值限制并且不被已有的可行路径支配（FdominatePR(F,R)值为假），则将此路径添加到队列中（8-9行）。否则，如果这条路径是可行路径，通过FdominatePR(F,R)函数检验是否R被路径F所支配，从而筛选掉队列中所有被R支配的可行路径（13-14行）。在队列Q为空之后，我们输出所有的可行路径，此时的可行路径即为支配路径。算法的复杂度为，其中n是拥有最多数量的关键字对应的结点数目，k是关键字的个数。证：DR算法的正确性由于支配路径必为关键词节点路径，所以整个搜索空间应该等价于不尽兴任何剪枝操作的关键词节点全排列。不管引理2和引理3采用的剪枝策略，DR算法的搜索空间是满足如下条件的关键词节点的组合：在具有相同关键词节点的路径之中，潜在路径拥有最小的开销。根据定义2，开销不是最小的路径应该被别的路径支配，这些路径应当在改进之后被删除。因此，得证。2.3FDR算法FDR算法是基于DR算法的启发式算法。FDR算法的基本思路来源于现实生活中人们在路径设定中会朝着一个方向走而不会折返。FDR算法的对已有的不完全路径的扩充方法是在最后一个结点后面添加一个更接近于终点的结点。即，每一次扩充都使得这条路径的最终结点距离终点更近。具体说来就是，当我们选择一个未被覆盖的关键字结点作为下一个结点时，这个结点到终点的距离小于上一个扩充的结点。基于这个策略，FDR可以迅速筛选掉一些不需要考虑的结点。给定一个KDR查询,对于一个关键字结点序列为的关键字结点路径R，如果，则其为不完全路径。对R的一次从到的扩充，如果，则我们认为这是一次有效的前向扩充。这里表示一次严格的前向扩充。当，表示只需要满足宽松的，向后不超过的前向扩充要求即可。图：前向扩充如图所示，给定一个终点t，对于一个目前到的不完全路径R，两条平行线和将图G分为三部分。当，左侧的结点违背了前向扩充的要求，，右侧的结点是扩充的候选结点。表示的情况。对于对应关键字结点序列为的路径R，我们用来表示下一个结点是v的前向扩充。并且，R的扩充后的关键字结点序列为。基于前向扩充机制，我们选择一个未被覆盖的关键字对应的结点是的当前路径更加接近终点直到此路径覆盖所有关键字成为一条可行路径。如图所示，给定一个KDR查询，对应关键字结点序列为的路径R，的最终结点是，如果，则只有为候选扩充结点。基于这个机制，我们可以得到一个新的剪枝策略。剪枝策略（未完成路径的相互支配）对于未完成路径和，分别对应的关键字结点序列为和如果，，且，则支配。如图所示，对于分别对应于和的和，他们的最终结点均为，覆盖的关键字集合相同。且小于。这样无论下一个结点是哪个，得到的最终的可行路径一定可以支配最终的可行路径。FDR算法的伪代码的框架结构和DR算法类似。在FDR算法中，根据前向扩充机制，FDR算法不断向未完成路径添加未匹配关键字的结点从而更接近终点。与DR算法类似，我们从队列Q中获取一条未完成路径并且进行前向扩充。如果新的路径满足预算值限制并且不被已有的可行路径支配（FdominatePR(F,R)函数返回值为假）则，我们将其加入到Q中（12行）。否则，如果路径已经是可行路径，我们使用FdominateFR（F,R）来监测可行路径之间有木有互相支配的情况。如果没有，将此路径加入到F中。如果F中的任何一条路径被新的可行路径支配，则将其从F中删除（16行）。FDR算法在最坏情况下的时间复杂度和DR相同，但是实际情况中，FDR需要的运算量远小于DR。2.4实验评估为了检验算法，我们使用openstreetmap中的真实路网数据进行实验。数据集采用上海市的路网数据，包括6050个有着经纬度信息的PoI。这些PoI被标记为9个不同的类别包括饮食，娱乐等等。从中抽取出3个数据集分别包含2000个PoI，4000个PoI和6000个PoI，分别用Node2000，Node4000，Node6000表示。使用距离大小作为图中边上的预算值。PoI的评分我们随机从1到5的数字对其进行赋值。这些评分代表着目标分值，分值越大表示受欢迎程度越高。我们使用不同的预算分数限制，关键字结点个数，查询关键字个数，数据集对两个算法进行性能和准确性上的评估。其中，预算分数限制从10000到50000。关键字结点个数从100到500。查询关键字个数从2到5。数据集从2000个点到6000个点。默认值为=20000,=200和=3。默认数据集为Node4000.。每种情况允许50个查询。初始结点和目标结点随机生成。在满足的情况下，查询关键字随机生成。程序采用VC++完成并且在Intel(R)Core(TM)i7-3770CPU@3.40GHZ平台下运行。2.4.1性能评估首先对两个算法在不同预算值限制，关键字结点数目，查询关键字数目和数据集下的性能表现进行评估。图：不同预算值比较不同的预算值限制图4表示在Node4000数据集下不同预算值限制的实验结果。即当关键字个数为3时，预算值限制分别为10,000，20,000,30,000,40,000,和50,000时查询的响应时间。随着预算值限制的增加，DR和FDR算法的运行时间越来越长，因为一个较大的预算值限制对应于更多的候选关键字结点。与DR算法相比，FDR算法的响应时间增速较慢因为FDR的前向剪枝策略使得其复杂度是线性的而DR为指数级别的。图：不同不同的关键字结点数目图5表示不同对应的不同执行时间。随着关键字个数的增长，DR算法越来越慢，但是FDR的变慢并不如此显著。这是因为DR算法的复杂度随着关键字结点个数的增长呈指数增长而FDR算法可以进行更加直接的剪枝从而降低运算量。不同的查询关键字个数图6表示查询关键字个数从2到5的情况下两个算法的执行时间对比。DR和FDR随着关键字个数的增加而执行时间变长是因为关键字个数增加而关键字结点个数不变带来了更多关键字结点的组合的数目。不同的数据集图7表示不同数据集（Node2000，Node4000，Node6000）下的执行时间的变化。可以看出，此时时间变化并没有显著的规律。执行时间的变化可能来源于不同数据集对于查询关键字，预算值限制，初始结点终止结点等选择的差异。小结这些结果表示准确算法DR在关键字和关键字结点个数较少的情况下运行良好。但是当关键字和关键字结点个数太多的情况下，启发式算法FDR更合适。FDR算法在大多数情况下可以找到一些路径供用户进行选择。两个用户对于数据集的大小的影响都很小，这是因为他们的复杂度与数据集的大小无关。2.4.2返回路径我们对DR和FDR的返回路径个数进行比较。不同的预算值限制图8表示在Node4000数据集下不同预算值限制的实验结果。查询关键字个数设为3。因为预算值限制的增加允许更多关键字结点的组合所以DR和FDR的返回路径个数均相应的增加。不同的查询关键字个数图9表示查询关键字个数从2到5的情况下返回路径个数的变化。FDR算法在查询关键字个数增加时返回路径个数显著减少。当查询关键字个数太大时，FDR可能不能找到满足条件的路径。

3基于预测的最小时间路径查询问题研究随着经济和技术的飞速发展，越来越多的人们购置私家车作为交通工具。这大大提高了人们出行的自主性和舒适度。同时道路设施也在迅猛发展中，尽可能的保障人们出行的畅通并且为人们出行提供多重选择。但是道路的建设并不能赶上汽车数量的井喷式增加。这带来了城市尤其是大城市的不定时拥堵，进而影响了人们的出行体验。传统的路径查询和车辆导航系统根据静态路网给出从指定起始点到终点的最短路径。然而，在实际生活中，由于拥堵现象在不同地点和不同时间的发生，路网中的最短路径并不是对于用户的最优路径。用户往往需要在指定起点、终点和出发时间后得到一条时间最短的路径，即最小时间路径。目前已有工作基于实时数据进行车辆导航（），然而，根据实时路况进行导航可能会出现出发时设计的是一条畅通的路径，但是当用户到达路径的中点时，从此处到终点的路径发生拥堵。实际交通情况有着复杂性和规律性，如上下班高峰期和雨雪天拥堵频率大大高于其他情况。合理的使用历史数据能够大大提高预测的准确性。制约基于预测的最小时间路径查询的发展的一个重要问题是作为移动应用，需要满足响应时间的要求和运算空间限制。在实际路网环境中，基于庞大的静态路网和繁多的历史数据，传统的改进最短路径的动态路径算法无法处理如此海量的数据，也没办法在可以接受的时间之内给出最小时间路径。最小时间路径的求解方法可以分解为对路段的基于历史数据的短时交通预测和基于路段行驶时间预测的动态路径查询。3.1相关工作3.1.1短时交通预测算法交通预测是指在控制变量决策的时刻t对下一决策时刻t+1甚至t+1之后的若干连续时刻的交通流量做出预测。一般情况下，当时刻t和时刻t+1之间的预测间隔小于15分钟时的交通预测是短时交通预测。实际路网系统是一个复杂的时变混沌系统，其最重要的特征就是时变性和高度的模糊性。时变性是指即刻路况对时间的依赖程度非常高，不同时刻的路况信息差异很大，路况信息的惯性非常小，可能当前时刻路况很好，车辆占有率很低，下一时刻或者几个时刻后的路况会突然变得很差，车辆占有率也突然变高。模糊性是指影响具体路况的因素非常多，各因素对路况好坏的影响程度很难界定。比如天气对路况的影响，定性方面看，雨雪天气等比较差的天气路况通常比较差，晴朗天气等较好的天气路况比较好，然而没有方法可以定量地分析路况比较差时雨雪天气的影响程度，路况比较好时晴朗天气的影响程度。当然，阻碍交通预测的不仅只有是实际路网系统的时变性和模糊性，还有其他方面如人为因素和非人为因素等。人为因素有交通故障、司机驾驶技术、不同性别的司机的突发情况的处理技巧不同等。非人为因素主要是指自然因素，比如天气等一些不可抗因素。这些因素对交通预测带来了困难，尤其是短时交通预测。短时交通不同于较长时期的交通预测，干扰因素对其的影响更大，规律性更加模糊。实际路网系统的时变性和模糊性限制了长期预测的准确性，实际路网系统中长期预测的实用价值不高。与长期交通预测不同，短时交通预测致力于根据当前时刻路况来预测未来15分钟甚至是5分钟的路况，误差率相对于长期预测要低的多，预测的准确性也比较高。根据短时交通预测确定短时路况信息，辅之以路径搜索算法，是实际动态路网系统中查找最小时间路径的标准解决方法。用于进行短时交通预测的方法主要有两类，即参数回归和非参数回归。参数回归的模型在参数成立的前提之下，参数回归的预测精度非常高，对于小样本的预测效果也比较好。然而，参数回归设定回归函数的形式已知，回归模型限制也比较多，比如要求样本数据服从某种数据分布、随机变量与误差之间独立等，而实际数据往往无法严格满足这些要求。另外一种预测方法是非参数回归方法。非参数回归对输入数据没有严格的限定，它依赖于根据历史数据来确定输入和输出之间的关系。非参数回归的回归函数限制比较少，形式自由，对数据的分布没有强制性要求，模型的预测精度也比较高，对非线性、非齐次的预测问题具有很好的效果。新采集到的数据可以方便地添加到历史数据之中，形成非参数预测的新数据源，而不像参数回归那样需要对各种参数进行费时的调整。另外，非参数回归不对数据进行预处理，保持了数据的完整性，相对于参数回归预测更加准确。参数回归主要包括历史平均、时间序列、卡尔曼滤波、小波理论和神经网络等。历史平均包括等权重历史平均算法和加权历史平均算法。等权重历史平均算法通过将历史数据相加并将和除以历史数据的个数计算得到。加权历史平均通过对不同的数据分配不同的权重，将数据乘以权重并求和得到。加权历史平均回归模型受权重分配因素的影响非常大，不同的权重分配得到的回归结果相差很大。然而，没有标准的权重分配算法来保证权重分配的合理性，权重分配必须要通过不断地迭代调整来达到最优。时间序列模型是根据观测得到的时间序列数据（按时间次序观测到的一系列时刻的数据），通过最大似然法等参数估计模型来进行。最著名的时间序列模型是ARMA(AutoRegressionMovingAverage)模型，ARMA模型全称是自回归移动平均模型。当时间序列本身不平稳的时候，ARMA模型无能为力，因此又提出了ARIMA模型，即自回归和移动平均模型。ARIMA模型可以有效应对不平稳的时间序列。卡尔曼滤波（KalmanFiltering）通过系统输入输出观测数据，利用线性系统状态方程对系统状态进行最优估计的算法。因为通过系统观测的数据包括系统中得干扰和噪声，因此最有估计也可以看做是滤波过程。小波理论将系统状态变化视为小得波形的波动，通过分析波形的变动趋势来预测。小波理论认为系统状态的变动具有衰减性和波动性，具有振幅正负相间的震荡形式。神经网络模型的灵感来源于动物特别是大脑的中枢神经系统的工作方式，神经网络模型被用于估计依赖于大量输入的未知近似函数，它可以根据输入的计算值，通过机器学习、模式识别等构建自适应预测系统，以预测之后的趋势。非参数回归主要包括k近邻算法、正交回归、样条光滑等。k近邻算法一种用来进行分类或者回归的非参数方法。无论是分类还是回归，k近邻算法的输入特征空间都k个最近的训练样本，输出则取决于k近邻是用来分类还是用来回归。当k近邻用于分类时，输出是类属。一个对象的最终类属由其邻居投票的多少来决定，最终标记为投票最多的类属。当k为1时，k近邻退化为最近邻，此时其类属为其最近的邻居。当k近邻用于回归时，输出是对象的属性值，其值得大小为k个最近邻居的属性平均值。k近邻算法是最简单的机器学习算法之一，它是一种基于实例的学习方法（延迟学习），该算法的输出只保证局部最优，对全局最优没有任何承诺，它将所有的计算推迟到分类或者回归的最后时刻。k近邻算法作为一种有监督的机器学习算法，并没有明显的训练过程，然而它要求其邻居的类属或者属性值已知。不管是分类k近邻还是回归k近邻，不同邻居的权重往往不同，距离目标对象最近的邻居占有的权重应该较大，距离目标对象较远的邻居占有的权重应该较小，如此才能保证在最终的决策过程中，距离目标对象较近的邻居的贡献较大，距离目标对象较远的邻居的贡献较小。一个常用的分配权重策略是赋予每个邻居的权重为1/d，d为到目标对象的距离。正交回归用于检验两个连续变量即响应变量和预测变量之间的线性关系。不同于简单的线性回归，正交回归中得响应变量和预测变量包含测量误差。而在简单的线性回归中，只有响应变量包含测量误差，预测变量不包含测量误差。样条光滑通过拟合不同的样条曲线来平滑回归方程，比如拟合B曲线来平滑回归方程。k近邻算法思想简单，容易实现，不需要复杂的参数估计，也不需要费时的初期训练。k近邻的耗时计算主要在于求得待分类或者回归的目标的k个最近邻居，然后根据这k个最近邻居来决定目标的分类或者属性值，求k个最近邻居的方法很多，适合的数据结构也很多，比如堆，因此实现k近邻算法也比较简单。k近邻算法适合用于对稀有事件进行分类。当一个时间的发生概率很小时，称该事件为稀有时间。k近邻算法特别适用于对小概率事件进行分类。当除了待分类的目标事件之外其他事件的发生概率分布比较均匀，此时待分类目标的邻居的分布也比较均匀，大部分邻居都使得目标向着一个方向靠拢，不会出现歧义性分类。当对象具有多个类别标签时，k近邻的表现效果要远远好于支持向量机等其他分类算法。k近邻算法在某些情况下是一种非常优雅的无参数分类或者回归算法，然而，另一些情况下有其局限性。k近邻算法最大的一点局限就是当样本非常不平衡时，大样本有很大的概率会支配最终的结果。比如一个类的样本容量非常大，其他类的样本容量相对小，当输入一个新的样本时，新样本的k个最近邻居中大容量样本中得元素占大多数，大容量样本最终支配了分类结果。k近邻算法的另一个局限就是算法的计算量非常大，对于每一个待分类的样本都需要计算该样本到所有样本之间的距离，然后才可以求得该样本的k个最近的邻居，重复进行了很多计算，时间复杂度非常高。3.1.2动态最短路径查询算法根据不同算法依赖的不同前置条件，可以将动态最短路径查询算法分为三大类。第一类是分时段的动态路径查询算法；第二类是小间隔时段动态路径查询算法；第三类是将动态路网建模为时间依赖网络，利用求解单点到单点最短路径的算法如ALT算法来求解。第一类算法考虑车辆的出发时刻，针对车辆不同时刻的不同位置，重新进行路径查询，如此迭代循环动态路径查询的过程，直到到达终点。第一类算法的典型代表是动态分时段改进的Dijkstra算法。第二类算法的基本思想是当时间间隔较小时，动态的路网可以近似地视为静态路网，此时可以利用静态的路径查询算法求解该时段的最短路径。第三类问题国外学者称为TDSPP问题，即Time-dependent

Shortest

Path

Problem。通过将动态路网建模为时间以来的网络，利用成熟的点到点的最短路径算法来求解。动态Dijkstra算法动态路网不同于静态路网，对于不同的时段，每个路段的行驶时间是不同的，动态路网中每个路段的行驶时间对到达该路段入口的时刻依赖非常严重，一个显而易见的实例是早高峰和空闲时段通过同一路段的时间相差颇多，空闲时段只需要十分钟，可能早高峰时通过该路段需要40分钟甚至更多。因此，动态分时段改进的Dijkstra算法不同于静态路段的Dijkstra算法，静态路段的Dijkstra算法假设对于同一路段，所有的时段的行驶时间都相同，因此静态路段的Dijkstra算法不受时段的影响。然而，时段因素对动态分时段的Dijkstra算法有明显的影响，某一路段的行驶时间强烈依赖于到达该路段入口的时间。动态分时段改进的Dijkstra算法通过引入一个依赖时间的函数cost(i,j,t)来加入时段因素的影响，函数cost(i,j,t)表示在时段t通过由i和j组成的路段所耗费的时间。以不同时段的不同路段的行驶时间为基础，改进静态路段的Dijkstra算法即可得到动态分时段改进的Dijkstra算法。动态分时段改进的Dijkstra算法的流程如下图：动态分时段的Dijkstra算法流程图中S表示集合变量，具体指包含最优路径的节点集合；s(v)是表示节点v是否已找到最短路径的布尔标识，s(v)=true表示已经找到了开始节点到节点v的最短路径，s(v)=false表示还没有找到开始节点到节点v的最短路径；dist(v)表示起点到节点v的最优路径所耗费的时间。动态分时段的Dijkstra算法可以根据车辆的路段位置进行不同时段的动态路径查询，最终找出最短路径。然而，由于时段跨度往往比较大，该算法无法应对时间敏感的突发事件，比如天气突变、交通事故等，在这种情况下使用该算法得到的最短路径不是实际情况下的最短路径，因为此时它没有放映突发事件对最终路径的影响，因此该算法在突发事件频发的路段中应用价值有限。小间隔时段动态路径查询算法小间隔时段的路况信息具有连续性，此时可认为某一路段的行驶时间是固定的，因此可以在小间隔时段内调用静态Dijkstra算法来进行路径查询，当下一个时段到来时，该路段的行驶时间发生变化，依据变化之后的数据重新利用静态Dijkstra算法来进行路径查询。小间隔时段动态路径查询算法通常将时段长度设置为5分钟到15分钟之间，此时的时段长度适中，交通信息反馈比较及时，最终得到的规划路径也比较准确。小间隔时段动态路径查询算法有效利用了实时的交通信息，可以有效应对突发天气、交通事故等因素，因此在突发事故比较多的路段实用价值比较高。然而，小间隔时段动态路径查询算法利用实时数据，由于实时数据存在延时、衰减等破坏数据完整新的缺点，小间隔时段动态路径查询算法也存在其局限性。其一为实时采集的数据的延时导致最新的交通信息并没有反映在当前路径查询算法找到的路径中，此时地路径具有时滞性，对于实时性要求比较高的用户来说，具有时滞性的路径的实用价值不大。其二为小间隔时段动态路径查询算法只依赖于当前数据进行路径查询，不考虑未来若干时间段之内的交通信息，容易导致最终规划出得路径偏离最优路径。比如根据当前信息，1小时之后到达的路段的路况良好，然而当车辆在1小时之后行驶至该路段时，可能由于上下班高峰等因素此路段已经非常拥堵，此时规划出得路径不符合用户的预期。其三为在交通比较繁忙的时段，路况信息的波动比较大，每个小时段规划出得路径都不同。用户期望获得是变动较小的最优路径，频繁变动的规划路径可能会给用户带来困扰，最终耗尽他们的耐心。TDSPP问题动态路径查询算法的第三种类型是时间依赖网络中的最短路径问题，该模型最早由Cooke,Halsey在1966年提出。在时间依赖的网络模型中，网络中依赖时间而变化的一些特性是可以预期的。时间依赖网络模型最初被用来解决根据当前路网数据规划的最短路径没有考虑可预期的路况数据变化问题，比如高峰时段等。在时间依赖网络最短路径查询模型中，通过某一路段的时间是从该路段出发的时段的函数，并且所有这些函数都是已知的。时间依赖最短路径查询的具体流程是：在当前时刻，对路网中所有路段进行多步预测，确定之后每个路段的具体行程时间，将路网建模为基于预测行程时间的时间依赖网络。普适的时间依赖最短路径是NP难的，不存在多项式时间复杂度之内的求解算法，因此实际应用中价值有限。然而，通过重新限制其前置条件，可以保证在多项式时间之内求解该问题，而前置条件也符合实际情况。比如通过限制通过顺序将时间依赖网络建模为FIFO网络，即先进先出网络，FIFO符合现实路网的通过顺序。在FIFO网络中，时间依赖最短路径呈现出很多有用的性质，利用这些性质可以设计多项式时间复杂度的求解算法。BrianC.Deany研究了FIFO时间依赖网络的性质并率先提出了多项式时间复杂度的求解算法。将实际路网建模为时间依赖网络，之后进行最短路径查询，这是求解动态路径查询问题的有效方法，也是实际路径导航系统普遍使用的方法。该方法充分整合了第一类动态路径查询算法和第二类动态路径查询算法，有效利用历史数据和实时数据，通过对未来若干时段进行预测，可以应对道路占有率突然升高等突发状况。不同于小间隔时段动态路径查询算法，时间依赖最短路径算法预测得到的未来若干时段的路况信息波动不大，最终规划得到的最短路径也不会频繁变动，不会给用户造成困扰。然而，基于多步预测的时间依赖最短路径算法存在如下局限：其一，也是最重要的一点是当预测的跨度很大时，预测的精度下降很快，依据预测的路况数据规划的最短路径也越偏离实际最短路径；其二为多步预测的最佳预测步长比较模糊，不存在一致的最佳步长，每个实际路网的最佳步长也能都不同，这给选择步长带来了挑战。选择合理的步长，必须通过实际路网中的不断迭代尝试，而大型路网的迭代尝试是非常耗时的。其三是历史数据的选取标准不明确。同当前时刻较近的历史数据对未来时段交通情况的关联性较大，同当前时刻较远的历史数据对未来时段交通情况的关联性较小，考虑所有历史数据涉及的数据量太大，无法在可以接受的时间内规划出合理的路径。考虑最近的历史数据可能会造成最终路径被若干数据支配，影响最终规划路径的准确性。3.1.3其他相关工作3.2算法设计3.2.1基于改进k近邻的短时交通预测算法基于改进k近邻的短时交通预测算法是非参数回归预测算法的一种，通过选择同当前观测的状态向量最相似的k个邻居状态向量来预测未来的路段行驶速度和通过时间。传统的基于k近邻的短时交通预测根据当前的实时速度和历史速度进行比较，从相似度较高的历史数据中的下一时刻的数据预测当前时间下一时刻的交通情况。而我们考虑到在不能获知实时速度而历史数据丰富时的，考虑到交通的规律性，我们从出行时的日期，时刻，星期，天气角度，对任意时刻的交通情况进行预测。算法框架具体而言，基于改进k近邻的短时交通预测算法包含5个组成部分：（1）构建历史数据库。 （2）确定状态向量。 （3）确定预测函数。 （4）从历史数据库搜索当前状态向量的k个最近邻居。（5）根据k个最近邻居，利用预测函数预测行驶速度和通过时间。基于改进k近邻的短时交通预测算法的具体流程如下图： 采用改进k近邻的短时交通预测算法进行交通预测的基础是数据属性丰富且有大量真实有效的历史数据。历史数据应该包含影响交通情况的各个属性如天气、日期、时刻等等的因素从而实时数据可以根据当前的情况找到和历史数据相似度最高的数据。大量真实有效的数据是当前数据在历史数据中有相似项的保证。然而，一方面庞大的历史数据需要合理的设计历史数据库，从而减少数据冗余、提高查询速度。另一方面历史数据中存在着测量误差、记录丢失和干扰数据等等情况，在历史数据库形成前我们需要对原始数据进行数据清洗，降低误差，提高预测准确度。状态向量定义状态向量确定了当前数据特征从而可以在历史数据库找到相似数据。在没有实时交通流速情况下，我们可以根据交通情况的规律性和复杂性，通过对状态向量选择可以将人们主观的结论和历史数据结合起来，对短时交通进行预测。根据[/traffic/]可知，城市交通拥堵问题严重且规律性明显，同时影响不同城市的特征差异很大，如北京的交通受到会议活动影响较大。哈尔滨的城市交通季节特征明显。上海由于气候平稳、无特殊道路交通事件，所以没有和北京哈尔滨相似的特征。但是上海地区晴雨天交通差别明显，高峰时段交通拥堵情况显著，节假日部分交通路段与平时差距较大。在此，我们选择上海作为研究城市，根据上海的交通规律制定相应的状态向量。因此选取日期，时间，星期，天气组成状态向量。即其中，表示路径查询当天的日期。表示历史数据对应的日期。表示当前时间。表示当前的星期，如星期一，星期六。表示路径查询当天的天气，如晴，雨。分别表示历史数据对应的时间、星期和天气。距离度量准则 距离度量准则用来衡量当前采集数据同历史数据库中得数据的匹配程度，通过距离函数来实现。对于给定的域，上的距离函数为映射对于域中的所有，距离函数需要满足如下条件：（1）非负性，即。（2）当且仅当。（3）对称性，即。（4）三角不等式。 常用的距离函数有曼哈顿距离和欧拉距离，这两种距离函数在我们设计的状态向量下不能直接使用。我们使用 预测算法经过上述的近邻匹配机制，假设在历史数据库中找到K个近邻，实际数据和这K个近邻的距离为，这些近邻所对应的时刻的流量为。预测算法包括等权重和带权重的预测算法。其中等权重的预测算法为： 这里并没有考虑当前观测值和历史数据库中不同近邻距离的不同，仅仅将各个近邻对于的流量取简单算数平均作为当前时刻的预测值。带权重的预算算法为：带权重的预测算法认为与当前观测的实时数据距离较小的历史数据库中的数据系列相似度较大，从而在预测算法中，这些距离近的近邻对预测值的权重较大。所以，通过对距离取倒数来确定权值。本文采用带权重的预测算法进行预测。3.2.2基于A*的动态路径查询算法A*算法A*算法是一种在在图中的节点之间寻找最短路径的高效算法。在静态网络中，A*算法的性能很高，如果可以保证启发式估价函数对每个节点的估值不高于其实际值，A*算法确定可以找到一条最短路径。A*算法最早由PeterHart,NilsNilsson和BertramRaphael于1968年提出，最初是作为EdsgerDijkstra于1959年提出的Dijkstra算法的一种推广，通过启发式搜索来提高算法效率。由于A*算法的高效率和精度，A*算法被广泛应用于游戏路径查询中，如在线游戏的BOT移动计算