近些年来，基于位置的服务成为研究的热点，越来越多的人需要这一服务帮助自己规划行程.当一个人到达一个陌生的城市，可能会遇到这样的问题：从宾馆出发，在乘火车离开之前，怎样规划一条人气分数最高的旅游路线，享受在这个城市中余下的6 h呢？在这一需求中，已知用户的当前位置(宾馆)和目标位置(火车站)，以及旅游时间(6 h)，这是一个基于时间约束的人气分数最优路径搜索问题，这一问题的求解是NP难问题^[1].

上述问题主要面临两方面的挑战：一是如何获得景点的人气分数.目前已经有很多研究工作^{[2, 3, 4, 5, 6]}根据用户的历史轨迹通过一定的规则统计景点的人气分数.二是如何按照约束条件规划路线上的景点.文献[1, 4, 6, 7, 8, 9]中采用不同的方法解决带约束的最优路径搜索问题，其中与本文研究的问题最相关的是文献[1, 4, 9].

文献[4]的目标是根据用户所在的城市、用户的喜好和用户的限定时间，为用户推荐整个城市中满足要求的旅游路线.文中利用动态规划算法(DPA)搜索最优路线，实验表明在景点个数不超过60时，算法有效性很高.

文献[9]提出了一种基于数据挖掘的精确算法(TripMine算法)，寻找从源点出发，最终回到源点并且景点人气分数之和最高的旅游路线.文中假设任意两点都有直达路径，也就是在一个完全图中按照排列组合的思想挖掘最优路线.实验表明在景点的个数不超过100时，算法的有效性高于文献[4]中的算法.TripMine算法与DPA算法面临着同样的问题，就是扩展性不好，当景点个数超过100时，两个算法都不能有效地挖掘出满足要求的路线.

文献[1]中，对于已知用户当前位置、目标位置和旅游时间的情况，假设景点的人气分数与景点的游玩时间成正比，提出了一种性能优于文献[4, 9]中算法的精确最优路径搜索算法和启发式最优路径搜索算法.但是事实上，景点的人气分数与景点的游玩时间往往是不成比例的.

本文为了解决景点的人气分数与游玩时间不成比例情况下的基于时间约束的人气最优路径搜索问题，提出了一种近似算法PSScaling，使用了一个修整参数δ，将景点的人气分数调整为一个整数，在原地图的基础上，生成一个缩放后的地图G_s，在G_s中，每一个节点对应一个标签列表，维护从源点出发的所有可用的子路径信息.整个解决方案的主要思想是从源点出发，扩展当前最优的子路径，并生成对应的标签，直到在目标节点生成所有的候选标签，最后将目标节点候选标签中最优的标签对应的子路径返回给用户.

本文用图G(见图 1)表示道路交通图.图中的点表示地图中用户的兴趣点，边表示两点间的路径.为了便于说明，本文主要研究有向图中基于时间约束的人气最优路径搜索问题，本文的方法也可以直接扩展到无向图中.

图1(Figure 1)

图1 图G Fig. 1 G map

图G(V,E)由节点集合V和边集E构成，其中每一个节点v∈V表示图上的一个点，每一条边e∈E表示两个邻接点之间的路径，从v_i到v_j的边表示为(v_i,v_j).一条路径P=<v₀,v₁,…,v_n>，表示按照顺序从点v₀沿着相关联的边到达点v_n的所有点的序列集合.

定义1    目标分数 (objective score) 和代价分数 (cost score). 已知图G(V,E)，其中每一个节点v∈V，每一条边e∈E，每个节点上的标签(w_o;w_c)表示节点v的目标分数和代价分数，每条边上的标签表示边的代价分数，记为w(e).节点上和边上的代价分数可以代表景点的游玩时间或者花费的金钱，节点上的目标分数可以代表景点的人气值等.

已知一条路径P=<v₀,v₁,…,v_n>，路径P上的点的集合为V_P，如果v_i∈V_P，则这条路径的目标分数表示为路径P上被访问的点的目标分数之和，如式(1)所示：

路径P的代价分数表示为路径P上边的代价分数之和加上路径P上被访问的点的代价分数之和，如式(2)所示:

问题描述. 已知源点v_s，终点v_d，代价限制C，搜索一条最优路径P，使得这条最优路径满足下面两个条件：

1) arg max OS(P) ;

2) C(P)≤C .

在已有的解决方法^{[3, 7, 8, 9]}中，最优路线的搜索规则是路径中包含的点都访问,而在本文的需求中，如图 1所示,如果查询q=(v₁,v₅,10)，也就是从v₁到v₅搜索满足10 h的人气最优路线.如果从v₁到达v₅经过的点全都访问，没有满足约束条件的最优路线；如果对于每一条路径上包含的节点，当时间不足以访问全部时，通过评估路径上节点的权重,有选择地挑选，在上述例子中最终会找到一条经过点v₁,v₈,v₇,v₄,v₅的最优路径P，因为代价的限制，路径中的点v₇来不及访问，最终可得：OS(P)=8，C(P)=10.

在一条路径P中，当点v_i被访问时，本文将其表示为v_i，没有被访问时，表示为v_i.上述例子中的最优路径P可以表示为P=<v₁,v₈,v₇,v₄,v₅>，这就表示从v₁到v₅，访问了v₁,v₈,v₄和v₅，经过v₇但是没有访问.

基于时间约束的人气最优路径搜索问题是NP难问题^[1]，为了解决这一问题，本文提出了一种近似的最优路径搜索算法PSScaling，借鉴了文献[10]中的一个完全多项式时间近似模式的基本思想.本文首先定义一个修整参数δ=εw_cminw_omin/C，w_cmin和w_omin分别表示图G中节点上最小的代价分数和最小的目标分数，而ε表示一个(0,1)范围的参数.对于每一个节点，本文缩放节点的目标分数w_o为_o，_o=w_o/δ，节点缩放的图称为缩放图，表示为G_s.在缩放图G_s中，已知一条路径P=<v₀,v₁,…,v_n>，则这条路径缩放后的目标分数之和为(P)=∑_i=1ⁿ_o(v_i).

近似算法PSScaling的基本思想，就是从缩放图G_s的源点v_s出发，基于宽度优先策略向终点v_d进行路径扩展.在路径的搜索过程中，如果扩展到当前节点v_i的子路径P_i的目标分数小于从源点到该节点的其他子路径的目标分数，而代价分数大于其他子路径的代价分数，那么算法忽略这条子路径P_i.

定义2    节点标签. 对于图中的每一个节点v_i，需要为其维护一个标签列表，标签列表维护着从源点v_s到节点v_i的所有子路径的状态信息，每一个标签对应着源点v_s到点v_i的一条子路径状态，记为L_i^k，其数据格式表示为(),和L_i^k.C分别表示L_i^k对应的子路径缩放后的目标分数之和、原目标分数之和以及代价分数之和.

已知节点v_i上的一个标签L_i^k，对于节点v_i的每一个邻接点v_j，可以扩展生成一个新的标签L_i^k.如果扩展的节点v_j是要访问的节点，则生成节点v_j的标签.如果节点v_j是经过的节点，那么生成标签.

定义3    标签的支配关系.L_i^k和L_i^m是从源点v_s到点v_i的两条子路径的标签，如果L_i^k.≥L_i^m.，并且L_i^k.C≤L_i^m.C，那么称标签L_i^k支配标签L_i^m，记为L_i^kL_i^m.

在算法PSScaling中，用节点标签缩放后的目标分数代替原目标分数去判断一个节点的标签是否支配另外的节点标签.也就是说被支配标签原来的目标分数比较低，在路径搜索的过程中可能被丢失，这就是算法PSScaling是近似算法的原因.

通过计算，可以限定一个节点上的标签的最多个数，如定理1所示：

定理1    每个节点上最多维护个标签.其中ε,C,w_cmin,w_omax,w_omin分别表示缩放的参数、指定的代价、节点的最小代价、节点的最大目标分数和节点的最小目标分数.

证明    根据本文算法可以计算出在指定的代价C内能访问的节点数目不超过，因此，在G_s中满足要求路线的最高目标分数不超过

因为同一节点上标签之间的支配关系，所以每个节点中存储的标签数目不超过.实际上，每个节点要维护的标签数目一定小于上面的公式得到的值，因为在上式中没有考虑节点间边上的代价.

定义4    标签的顺序. L_i^k和L_i^m分别表示从源点出发到达节点v_i和v_j的两条子路径(v_i和v_j也可以是相同的两点)，如果L_i^k.≥L_j^m.，而L_i^k.C≤L_j^m.C，本文称L_i^k的顺序比L_i^m靠前.

定理2    一条路径上，经过而没有访问的节点如果不在它的前驱节点和后继节点之间的最短路径上，那么这条子路径的标签是被支配的标签.

证明    已知路径P=m,(v_i),v_j>，表示从节点v_m到节点v_j之间的一条子路径，它对应的标签为：L_j^m=((L_j^m.)=_o(v_m)+_o(v_j),L_j^m.OS=w_o(v_m)+w_o(v_j),L_j^m.C=w(v_m,v_i)+w(v_i,v_j)+w_c(v_m)+w_c(v_j)).并且w(v_m,v_i)+w(v_i,v_j)>c_m,j；假设存在另外一条从节点v_m到节点v_j的子路径P′=m,(v_n),v_j>，并且w(v_m,v_n)+w(v_n,v_j)=c_m,j,P′对应的标签为L_jⁿ=(L_jⁿ.=_o(v_m)+_o(v_j),L_jⁿ.OS=w_o(v_m)+w_o(v_j),L_jⁿ.C=w(v_m,v_n)+w(v_n,v_j)+w_c(v_m)+w_c(v_j)),所以L_j^m.=L_jⁿ.,L_j^m.C>L_jⁿ.C，根据定义3可知，L_jⁿ≥L_j^m.在本文中，一条路径中当前节点v_i的前驱节点记为pre(v_i).路径P=m,(v_i),v_j>中，节点v_i的前驱节点就是v_m，即pre(v_i)=v_m.

本文提出的算法PSScaling的详细流程如下.

1) 首先初始化最优队列Q，设置最优路线P=Ф，以及当前获得的路线的最高目标分数OS_max=0.

2) 接受一个查询q=(v_s,v_d,C).

3) 比较源点到终点的最小代价c_s,d和指定代价C，如果c_s,d<C，从源点v_s出发，生成访问源点的子路径标签L_s⁰和不访问原点节点的子路径标签L_s¹，分别将其入队；然后按照标签的顺序将标签L_i^k出队，如果是终点并且L_i^k.OS>OS_max，那么将L_i^k.OS赋值给OS_max,L_i^k赋值给最优路径P.如果v_i不是终点，向当前节点v_i的邻接点v_j扩展.

4) 在路径的扩展过程中，如果当前节点v_i是被访问的节点或者节点v_i的前一个节点v_pre(i)到达当前节点的代价与当前节点v_i到达其邻接点v_j的代价和等于pre(v_i)到达v_j的最小代价，则生成路过节点v_j的标签L_j^l，如果没有其他标签支配L_j^l，当前标签L_j^l的代价与节点v_j到达终点的代价之和小于指定代价，将标签L_j^l入队，然后比较标签L_j^l与节点v_j的每一个标签L，如果标签L被标签L_j^l支配，那么删除标签L.接着生成访问节点v_j的标签L_j^k，如果没有其他标签支配L_j^k，并且当前标签L_j^k的代价与节点v_j到达终点的代价之和小于指定代价C，将标签L_j^l入队，然后比较标签L_j^k与节点v_j的每一个标签L，如果标签L被标签L_j^k支配，那么删除标签L.

5) 直到队列为空，搜索过程结束，最后返回最优路径P.

本文在算法的实现过程中，为了提高路径搜索的效率，将任意两点之间的路径的时间代价c_i,j进行预处理保存起来.

最优路径表示为P_opt，基于缩放图G_s中计算的近似最优路径表示为P_opt^S，则有：

定理3    .

证明    因为，

所以 .

因为 ，

所以

因为，

所以.

从运行时间和目标函数值的相关度两个方面对本文提出的近似算法PSScaling与文献[6]提出的启发式算法HeuriSearch进行实验比较与分析.

实验的数据集是在网上下载的北京的真实地图数据的基础上，按照本文需要的数据特点在图数据的点上加了人气和游玩时间两个权重属性，最终获得节点个数分别为1 000，2 000，3 000，4 000，5 000的5个数据规模不同的数据集，边的代价分数用路程时间表示，点的代价分数是在0~5的范围内随机设置的整数，人气分数是(0,1)之间随机设置的.

本文算法都是使用VC++实现，运行在以下配置的计算机上：Intel (R) Core(TM)2 CPU E7300@2.93 GHz，8.0 GB RAM.

1) 节点个数变化对运行时间和相关度的影响,见图 2.ε=0.5，限制时间为8 h的情况下，算法PSScaling和启发式算法HeuriSearch的运行时间相差不多，算法PSScaling的运行时间略优于算法HeuriSearch.主要是因为算法HeuriSearch沿着源点与终点的最短路径扩展搜索，所以当限定的时间为8 h，算法的运行时间受节点数目影响不是很大.

图2(Figure 2)

图2 节点数目改变的运行时间 Fig. 2 Running time with the number of nodes varing

利用文献[6]提出的精确算法计算人气最优路径，但是这一算法的运行效率很低，尤其是节点数据超过500时，很多查询算法1天都运算不出结果，所以本文的实验选择了获得运行结果的数据进行比较.本实验中随着节点数目的增加，两种算法的相关度(见图 2)略微下降，但是变化幅度不大，因为算法PSScaling的相关度与参数ε的设置有关，当ε固定时，相关度基本在很小的范围内波动，而算法HeuriSearch的相关度不稳定，但是当限定的时间为8 h时，相关度也相对较高.

2) 限定时间变化对运行时间和相关度的影响,见图 3(ε=0.5，节点数据为5 000).因为算法HeuriSearch是沿着源点与终点的最短路径搜索最优路径，所以当限定的时间比较大时，路径搜索的效率明显变低.

图3(Figure 3)

图3 限定时间变化的运行时间情况 Fig. 3 Running time with the time limit varing

因为算法PSScaling的相关度与参数ε的设置有关，当ε固定的时候，相关度基本在很小的范围内波动，而算法HeuriSearch的相关度不稳定，在限定代价超过12 h的时候，相关度明显变低，此时算法PSScaling的相关度明显优于算法HeuriSearch.

3) 参数ε变化对运行时间和相关度的影响,见图 4(节点个数为5 000，并且限定时间为8 h).算法的运行时间随着参数ε的增加而减小.算法的运行时间受参数ε的影响，当ε增加的情况下，算法的相关度相应变低，算法的运行时间会略微下降.

图4(Figure 4)

图4 ε变化的运行时间 Fig. 4 Running time with ε varing

参数ε变化会影响算法的相关度，当ε增加的情况下，算法的相关度会略微变低，但是本实验中始终保持在0.95左右.

为了解决基于时间约束的人气最优路径搜索问题，本文提出了一种近似算法PSScaling：使用修整参数δ，将景点的人气分数调整为一个整数，然后利用路径标签上缩放后的景点的人气分数和子路径的时间代价选择最优的子路径向终点扩展.最后，通过实验分析得出，本文提出的算法能够在很高的执行效率下找到近似的最优路线.