1.一种基于近似算法的最短路径查询方法,其特征在于,包括以下步骤:(1)以固定的时间间隔接收来自多个用户的多个路径查询请求,每个路径查询请求包括其对应路径的起始点、目标点、起始点与目标点之间的欧几里得距离;
(2)根据所有路径查询请求对应路径的收益确定代表路径,将该代表路径作为当前代表路径存储在服务器的缓存(Cache)中,从所有路径查询请求中选择与代表路径夹角为30°的所有路径,并将所有路径中目标点位于当前代表路径上的路径返回给客户端;
(3)针对步骤(2)中每一条其对应路径没有被返回给客户端的路径查询请求而言,在服务器的缓存中对该路径查询请求进行查询处理,以得到该路径查询请求对应的最短路径,并将该最短路径返回到客户端。
(4)针对步骤(2)和(3)处理完毕后,步骤(1)得到的所有路径查询请求中所有其对应路径还没有被返回给客户端的每条路径查询请求而言,利用双向A*算法对该路径查询请求对应路径的起始点到目标点进行处理,以得到该路径查询请求对应的路径,并将该路径返回给客户端。
2.根据权利要求1所述的最短路径查询方法,其特征在于,
在服务器的缓存中,采用路径信息索引的方式存储每条代表路径,并存储代表路径的起始点、目标点、到达时间和收益;
在服务器的缓存中是以位图索引的方式存储代表路径上的所有节点,若某个节点v的值为0,则表示缓存中的代表路径不包含此节点v,若节点v的值为1,则表示缓存中的代表路径包含此节点v。
在服务器的缓存中采用节点邻接索引(Node Neighbor Index)的方式存储代表路径上节点间的邻接关系,记录缓存的位图中要存储的代表路径上节点之间的邻接关系。
3.根据权利要求1所述的最短路径查询方法,其特征在于,步骤(2)包括以下子步骤:(2-1)设置计数器i=1;
(2-2)判断i是否大于等于服务器的缓存所能存储的最大路径查询请求数,如果是则进入步骤(3),否则转入步骤(2-3);
(2-3)设置计数器j=1;
(2-4)判断j是否大于等于路径查询请求的总数,如果是则过程结束,否则转入步骤(2-
5);
(2-5)从除了第j条路径查询请求以外的所有路径查询请求中,获取与第j条路径查询请求对应的路径具有相同起始点的所有路径对应的M条路径查询请求,计算第j条路径查询请求和M条路径查询请求各自对应路径的收益,并将最大收益对应的路径作为代表路径;
(2-6)从第j条路径查询请求和M条路径查询请求对应的路径中选择与代表路径夹角为
30°的所有路径;
(2-7)将步骤(2-6)选择的所有路径中目标点位于当前代表路径上的路径返回给客户端;
(2-8)判断服务器的缓存中存储的代表路径的总数是否大于1,如果是则进入步骤(2-
9),否则进入步骤(2-14);
(2-9)设置计数器k=1;
(2-10)判断k是否大于等于缓存中在当前代表路径之前存储的代表路径总数,如果是则进入步骤(2-15),否则进入步骤(2-11);
(2-11)判断步骤(2-6)存储在缓存中当前代表路径和该当前代表路径之前存储的第k条代表路径之间的相似度是否大于已预设阈值,如果是则进入步骤(2-12),否则进入步骤(2-15);
(2-12)判断存储在服务器的缓存中的当前代表路径的收益是否大于缓存中先前存储的第k条代表路径的收益,如果是则进入步骤(2-13),否则进入步骤(2-14);
(2-13)把缓存中先前存储的第k条代表路径替换为步骤(2-6)存储在缓存中的当前代表路径,并转入步骤(2-14);
(2-14)设置k=k+1,并进入步骤(2-10);
(2-15)设置j=j+1,并返回步骤(2-4);
(2-16)设置i=i+1,并返回步骤(2-2)。
4.根据权利要求3所述的最短路径查询方法,其特征在于,步骤(2-5)中,计算路径的收益的计算公式是:其中,Rvo表示路径的起始点,Rvd表示路径的目标点,|RvoRvd|表示路径的起点和目标点之间的欧几里得距离,∑Rvo表示路径上起始点的邻接节点的总数,∑Rvd表示路径上目标点的邻接节点的总数,k表示路径上节点的总数, 表示步骤(1)得到的所有路径查询请求中,以路径的起始点Rvo为起始点、Rvd为目标点、并与路径夹角为30°的所有路径对应路径查询请求的总数。μ1、μ2、μ3、μ4分别为以上4个参数的影响因子,其取值分别为μ1=
0.2,μ2=0.1,μ3=0.5,μ4=0.2。
5.根据权利要求3所述的最短路径查询方法,其特征在于,步骤(2-11)中计算代表路径之间相似度的计算公式是:其中P为缓存中已有的代表路径,P1为当前代表路径。L(SP∩SP1)为路径P与路径P1共同的节点数量,L(P)表示代表路径P上的节点数,L(P1)表示代表路径P1上的节点数,min{L(P),L(P1)}表示路径P上的节点数与路径P1上的节点数二者之间的最小值。
6.根据权利要求1所述的最短路径查询方法,其特征在于,步骤(3)包括以下子步骤:(3-1)设置计数器a=1;
(3-2)判断a是否大于等于所有其对应路径没有被返回给客户端的路径查询请求的总数,若是则过程结束,否则进入步骤(3-3);
(3-3)设置计数器b=1;
(3-4)判断b是否等于缓存中的最大存储路径数量,若是则进入步骤(3-8),否则进入步骤(3-5);
(3-5)在服务器的缓存中,判断缓存中的第b条代表路径上的节点是否包含所有其对应路径没有被返回给客户端的路径查询请求中的第a条路径查询请求对应的路径的起始点和目标点,如果是则进入步骤(3-6),否则进入步骤(3-7);
(3-6)将缓存中第b条代表路径,作为所有其对应路径没有被返回给客户端的路径查询请求中的第a条路径查询请求的路径查询结果,并将该路径查询结果返回到客户端,然后转入步骤(3-29)。
(3-7)设置b=b+1,并返回步骤(3-4);
(3-8)针对所有其对应路径没有被返回给客户端的路径查询请求中的第a条路径查询请求而言,将其对应路径的长度设置为无穷大;
(3-9)设置计数器c=1,d=1,e=1,并初始化数组SO、SD为空;
(3-10)判断c是否大于等于服务器的缓存所能存储的最大路径查询请求数,若是则进入步骤(3-18),否则进入步骤(3-11);
(3-11)判断服务器的缓存中存储的第c条代表路径上是否包含所有其对应路径没有被返回给客户端的路径查询请求中第a条路径查询请求对应路径的起始点,如果是则进入步骤(3-12),否则进入步骤(3-14);
(3-12)将服务器的缓存中存储的第c条代表路径存储到数组SO;
(3-13)设置d=d+1,并进入步骤(3-17);
(3-14)判断缓存中存储的第c条代表路径上是否包含所有其对应路径没有被返回给客户端的路径查询请求中第a条路径查询请求对应路径的目标点,如果是则进入步骤(3-15),否则进入步骤(3-17);
(3-15)将第c条代表路径存储到数组SD;
(3-16)设置e=e+1,并进入步骤(3-17);
(3-17)设置c=c+1,并返回步骤(3-10);
(3-18)设置计数器f=1,g=1;
(3-19)判断f是否大于等于数组SO中存储的代表路径的数量d,如果是则进入步骤(3-
27),否则进入步骤(3-20);
(3-20)判断g是否大于等于数组SD中存储的代表路径的数量e,如果是则进入步骤(3-
26),否则进入步骤(3-21);
(3-21)判断数组SO中存储的第f条代表路径和数组SD中存储的第g条代表路径是否有公共节点vm,若是进入步骤(3-22),否则进入步骤(3-25);
(3-22)对于所有其对应路径没有被返回给客户端的路径查询请求中第a条路径查询请求对应的每一条路径而言,判断是否有等式 成立,若是则进入步骤(3-23),否则进入步骤(3-25),其中ρ表示约束阈值,dis(vovm)表示从起始点vo到公共节点vm的路径的长度,dis(vmvd)表示从公共节点vm到目标点vd的路径的长度,ρ为给定的约束阈值,|vovd|表示从起始点vo到目标点vd的欧几里得距离。
(3-23)针对所有其对应路径没有被返回给客户端的路径查询请求中的第a条路径查询请求而言,判断其对应路径中从起始点vo到公共节点vm再到目标点vd的路径的长度dis(vovmvd)是否大于等于路径的长度dis(vovd),如果是则进入步骤(3-25),否则进入步骤(3-
24),且有dis(vovmvd)=dis(vovm)+dis(vmvd)。
(3-24)对于所有其对应路径没有被返回给客户端的路径查询请求中的第a条路径查询请求而言,将其对应路径的长度设置为dis(vovm)=dis(vovmvd),并将从起始点vo到目标点vd的路径设置为从起始点vo到公共节点vm再到目标点vd的路径;
(3-25)设置g=g+1,并返回步骤(3-20);
(3-26)设置f=f+1,并返回步骤(3-19);
(3-27)判断所有其对应路径没有被返回给客户端的路径查询请求中第a条路径查询请求q=(vo,vd)对应路径的长度dis(vovm)是否是无穷大,如果是则进入步骤(3-29),否则进入步骤(3-28);
(3-28)向客户端返回所有其对应路径没有被返回给客户端的路径查询请求中第a条路径查询请求对应的路径vo→vm→vd,以及路径的长度dis(vovmvd)。
(3-29)设置a=a+1,并返回步骤(3-2)。
7.一种基于近似算法的最短路径查询系统,其特征在于,包括:
第一模块,用于以固定的时间间隔接收来自多个用户的多个路径查询请求,每个路径查询请求包括其对应路径的起始点、目标点、起始点与目标点之间的欧几里得距离;
第二模块,用于根据所有路径查询请求对应路径的收益确定代表路径,将该代表路径作为当前代表路径存储在服务器的缓存(Cache)中,从所有路径查询请求中选择与代表路径夹角为30°的所有路径,并将所有路径中目标点位于当前代表路径上的路径返回给客户端;
第三模块,用于针对第二模块中每一条其对应路径没有被返回给客户端的路径查询请求而言,在服务器的缓存中对该路径查询请求进行查询处理,以得到该路径查询请求对应的最短路径,并将该最短路径返回到客户端;
第四模块,用于针对第二模块和第三模块处理完毕后,步骤(1)得到的所有路径查询请求中所有其对应路径还没有被返回给客户端的每条路径查询请求而言,利用双向A*算法对该路径查询请求对应路径的起始点到目标点进行处理,以得到该路径查询请求对应的路径,并将该路径返回给客户端。