开放科学（资源服务）标志码（OSID）：
0 概述
随着人们对旅游路线需求的多样化，路径查询不只是常见的最短路径查询，人们通常会综合考虑路径时间开销、路径覆盖的兴趣点等其他因素[1-3]。考虑如下的场景：当用户想要去某些地方旅游时，希望找到一条从指定地点出发，途经满足用户指定的兴趣点，最后到达终点的路径，该路径在满足游客的行程预算（以下称为代价阈值）的前提下，所用时间越短越好。
关键词最优路径查询[3-4]（Keyword-aware Optimal Route query，KOR）是一种在满足关键词全覆盖、路径代价阈值约束下，路径时间开销最小的路径查询类型，常用于旅行规划。KOR求解的途径是路径拓展，现有求解算法本质上都是广度优先搜索——搜索规模随搜索深度指数级增加。缩小搜索规模主要的优化策略有近似支配剪枝[3]、可行解目标值剪枝[3]、关键词顶点拓展[5]、全局优先拓展[3]和最小代价剪枝[6]。这些优化策略在搜索深度浅的情况下是有效的，但是在搜索路径长或搜索深度较深的情况下搜索规模仍然难以控制。因此，避免长路径拓展过程中搜索深度过深是解决这一问题的关键。
受人类在规划长路线时先选取必须要经过的数个重要地点，然后分别针对各段路径进行规划的启发，本文提出一种关键词最优路径查询的分段拓展算法（SE-KOR），SE-KOR根据 < 关键词：顶点 > 的关键词倒排索引表，构建{起点→关键词顶点1→……→关键词顶点n→终点}的关键词顶点路径，将路径分割为以关键词顶点为边界点的多段路径，并分别拓展，降低搜索深度，以避免搜索规模爆炸的问题。最终将各段路径拼接成完整的路径。
1 相关工作
路径拓展算法分为启发式搜索和广度优先搜索。启发式搜索代表算法KDR[7]和Greedy[3]通过得分函数仅对关键词覆盖的顶点拓展，具有较高的执行效率，但返回结果本质上是关键词顶点的最优排序，不是具体路径。广度优先搜索代表算法KSRG[5]仅对关键词顶点拓展，具有较高的执行效率，但返回结果依旧是最优关键词顶点序列，在后续优化中，KSRG[6]利用Skyline路径实现具体路径查询，但预处理工作获取Skyline路径的时空开销巨大；KORL[6]利用树形索引将大图分而治之并在预处理中求取Skyline路径，在拓展阶段需要对压缩图进行复原计算，产生大量中间拓展操作；OSScalling[3]、BucketBound[3]进行邻边拓展，在面临长路径搜索时，易出现搜索规模过大而耗时较长的问题。
在剪枝策略方面，现有策略主要有支配、近似支配、可行解目标值、全局优先拓展、关键词顶点拓展和最小代价剪枝。OSScalling[3]、BucketBound[3]运用支配、可行解目标值和全局优先拓展对中间路径剪枝。KSRG[5]提出关键词顶点拓展，跳过与关键词不相关的节点并利用近似支配剪枝。KORL[8]提出最小代价剪枝，剪去不满足代价阈值的中间路径，但现有剪枝策略不控制路径拓展方向。
除上述KOR算法外，其他关键词的查询也得到广泛研究。基于关键词的最优位置查询[9-11]查找关键词全覆盖下距离各点最近的位置，空间组关键词查询[12-14]检索最接近查询位置且顶点间距离最短的关键词顶点序列。室内关键词感知路径规划[15-16]研究复杂室内场景下的关键词覆盖路径查询问题。多用户空间关键词[17-18]路线查询针对多用户查找关键词全覆盖、代价最小的路径，对多用户场景下的KOR具有启发意义，但以上算法不适用于KOR问题。
为解决路径拓展不具体和长路径搜索耗时长的问题，本文提出关键词最优路径查询的分段拓展算法（SE-KOR），构建关键词顶点路径作为路径边界，将路径划分为多段分别拓展，并且采用局部代价阈值剪枝，保证路径拓展沿关键词顶点路径方向。本文算法的创新点如下：
1）针对广度优先搜索方式遍历顶点、查找兴趣点耗时长的问题，提出一种基于关键词倒排索引表构建关键词顶点路径的方法；以关键词顶点为边界点，把该路径分为多段并分段拓展，降低搜索深度，从而降低搜索规模，缩短执行时间。
2）针对现有剪枝策略不控制路径拓展方向的问题，本文提出局部代价剪枝，控制路径的走向沿着关键词顶点路径的方向拓展，并综合利用近似支配剪枝、可行解目标值剪枝和全局优先拓展，加速拓展过程。
2 KOR及其求解框架
求解KOR是一个NP-hard问题[3]，约束条件分别为关键词全覆盖、满足代价阈值以及目标值最优化。本节给出KOR定义，介绍KOR求解框架。
2.1 符号说明
为方便阅读，首先给出常用符号的说明，如表 1所示。
表 1
(Table 1)
表 1 符号说明表
Table 1 Symbol description table
| 符号 |
描述 |
| $ {w}_{i} $ |
关键词 |
| $ b $ |
代价值 |
| $ o $ |
目标值 |
| $ \widehat{o} $ |
修正目标值 |
| $ e $ |
边$ ({v}_{i}, {v}_{j}) $ |
| $ b({v}_{i}, {v}_{j}) $ |
$ {v}_{i} $到$ {v}_{j} $的代价值 |
| $ o({v}_{i}, {v}_{j}) $ |
$ {v}_{i} $到$ {v}_{j} $的目标值 |
| $ \widehat{o}({v}_{i}, {v}_{j}) $ |
$ {v}_{i} $到$ {v}_{j} $的修正目标值 |
| $ p $ |
路径 |
| $ {L}_{i}^{k} $ |
路径标签 |
| $ {o}_{\mathrm{m}\mathrm{i}\mathrm{n}} $ |
查询图中最小目标值 |
| $ {b}_{\mathrm{m}\mathrm{i}\mathrm{n}} $ |
查询图中最小代价值 |
| $ \tilde{p} $ |
关键词顶点路径 |
| $ {\tilde{p}}_{o} $ |
目标值最小关键词顶点路径 |
| $ {\tilde{p}}_{b} $ |
代价值最小关键词顶点路径 |
|
下载CSV
表 1 符号说明表
Table 1 Symbol description table
|
2.2 问题定义
关键词最优路径查询主要基于路网，路网可以抽象成如图 1所示的查询图。
定义1（查询图）[3] $ G=(V, E) $由顶点集V和边集E构成。任意$ v\in V $表示兴趣点，v的地理位置用经纬度表示，记为$ v.\mathrm{l}\mathrm{o}\mathrm{c} $，v的关键词集合表示为$ v.\varphi =\{v.{w}_{1}, v.{w}_{2}, \cdots \} $。连接邻接点$ {v}_{i} $和$ {v}_{j} $的路径$ ({v}_{i}, {v}_{j}) $称为边，记为e，$ e\in E $。每条边有两个属性：代价值$ b({v}_{i}, {v}_{j}) $和目标值$ o({v}_{i}, {v}_{j}) $。
如图 1所示，通常代价值表示边的长度，用括号外的数值表示；目标值表示经过边所需要的时间，用括号内的数值表示。表 2列出图 1中各顶点对应的关键词集合[5]。
表 2
(Table 2)
表 2 顶点关键词信息
Table 2 Vertex keywords information
| 顶点 |
顶点关键词集合 |
| $ {v}_{1} $ |
$ {w}_{3} $ |
| $ {v}_{2} $ |
$ {w}_{4} $ |
| $ {v}_{3} $ |
$ {w}_{1} $ |
| $ {v}_{4} $ |
$ {w}_{4} $ |
| $ {v}_{5} $ |
$ {w}_{3} $ |
| $ {v}_{6} $ |
$ {w}_{4} $ |
| $ {v}_{7} $ |
$ {w}_{1}, {w}_{3}, {w}_{4} $ |
| $ {v}_{8} $ |
$ {w}_{2} $ |
| $ {v}_{9} $ |
$ {w}_{2} $ |
| $ {v}_{10} $ |
$ {w}_{3} $ |
|
下载CSV
表 2 顶点关键词信息
Table 2 Vertex keywords information
|
定义2（路径） $ p=({v}_{0}, {v}_{1}, \cdots ，{v}_{n}) $表示一条从$ {v}_{0} $出发，经过$ {v}_{1} $，v2，…，$ {v}_{n-1} $，到达$ {v}_{n} $的路径，$ p $覆盖的关键词表示为$ p.\varphi =\underset{v\in p}{\cup }v.\varphi $。
根据定义2，路径$ p $的代价值和目标值分别为：$ b\left(p\right)=\sum\limits_{i=1}^{n}b({v}_{i-1}, {v}_{j}) $，$ o\left(p\right)=\sum\limits_{i=1}^{n}o({v}_{i-1}, {v}_{j}) $。
定义3（KOR） 一个KOR查询$ Q $是一个四元组$ Q=({v}_{s}, {v}_{t}, \varphi , \mathrm{\Delta }) $，$ {v}_{\mathrm{s}} $、$ {v}_{t} $、$ \varphi $和$ \mathrm{\Delta } $分别表示路径起点、终点、覆盖的关键词集合和代价阈值。用$ {p}_{s, t} $表示从$ {v}_{\mathrm{s}} $到$ {v}_{t} $的路径集合，$ {p}_{\mathrm{c}\mathrm{a}\mathrm{n}\mathrm{d}} $表示满足关键词全覆盖和代价阈值的可行路径$ p $的集合，即$ {p}_{\mathrm{c}\mathrm{a}\mathrm{n}\mathrm{d}}=\left\{p\right|p\in {p}_{s, t}\bigcap p.\varphi \supseteq $ $ Q.\varphi \bigcap b\left(p\right)\le {\mathit{\Delta}} \} $，则KOR的最优路径$ {p}_{\mathrm{o}\mathrm{p}\mathrm{t}}=\underset{p\in {p}_{\mathrm{c}\mathrm{a}\mathrm{n}\mathrm{d}}}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}o\left(p\right) $。
2.3 KOR求解框架
现有KOR求解方法的核心是路径拓展，以降低路径拓展代价为目标，组合运用多种剪枝策略，预先计算剪枝时的代价值和目标值。KOR的求解框架如图 2所示，包括预处理和路径拓展两部分。预处理部分预先计算路径拓展过程中用到的路网中任意两个顶点间的最小代价值和最小目标值，避免不同KOR的重复计算；在路网更新时同步更新。路径拓展部分综合运用多种剪枝策略，尽可能地降低拓展代价。剪枝策略分为路径剪枝和可行解剪枝两方面。路径剪枝包括支配剪枝、目标修正的近似支配剪枝、全局优先拓展剪枝等。这些剪枝策略可以单独或组合运用，以低的代价得到可行解集合。然后利用可行解剪枝中的可行解目标值剪枝获取最优解。
KOR的求解过程主要是路径拓展的过程。为方便描述路径拓展过程，下面先给出路径标签和标签操作的定义。
定义4（路径标签） 对任意从$ {v}_{\mathrm{s}} $拓展至$ {v}_{i} $的路径$ p $，在顶点$ {v}_{i} $处构建路径标签$ {L}_{i}^{k}=(\varphi , \widehat{o}, o, b) $，4个参数分别代表路径$ p $覆盖的关键词集合、修正目标值、目标值和代价值。路径标签简称标签。
定义5（标签操作） 由顶点$ {v}_{i} $的标签$ {L}_{i}^{k} $向它的邻接顶点$ {v}_{j} $拓展生成新标签$ {L}_{j}^{l}=(\varphi , \widehat{o}, o, b) $。新标签根据$ {L}_{i}^{k} $的当前顶点$ {v}_{i} $到顶点$ {v}_{j} $的$ o $、$ b $构建，满足以下条件：
1）$ {L}_{j}^{l}.\varphi ={L}_{i}^{k}.\varphi \bigcup {v}_{j}.\varphi $；
2）$ {L}_{j}^{l}.\widehat{o}={L}_{i}^{k}.\widehat{o}+\widehat{o}({v}_{i}, {v}_{j}) $；
3）$ {L}_{j}^{l}.o={L}_{i}^{k}.o+o({v}_{i}, {v}_{j}) $；
4）$ {L}_{j}^{l}.b={L}_{i}^{k}.b+{v}_{j}.b({v}_{i}, {v}_{j}) $。
KOR求解过程如下：
1）从起点开始邻边拓展，对于拓展到新的顶点，记录从起点到该顶点的一个标签，如$ {L}_{i}^{k}=(\varphi , \widehat{o}, o, b) $中包括已经包含的关键词、修正目标值、$ o $、$ b $，并计算该标签的全局优先度，优先度越小，优先级别越高，然后入队。
2）根据全局优先拓展策略，选择优先级最高的路径标签出队，向下一个顶点拓展。
3）根据支配剪枝或者近似支配剪枝策略，判断当前路径是否被支配，若被支配则舍弃，继续下一轮拓展，否则入队。
4）如果当前路径满足关键词全覆盖和代价阈值，若此时可行解集合中为空，当前标签进入可行解集合，否则与现有可行解对比，保留目标值最小的可行解，即可行解目标值剪枝。
5）以此类推，直到优先队列中所有标签为空，返回一个目标值最小的可行解作为最优解。
两个部分相关定义及定理如下：
1）预处理
预处理阶段包括两部分：（1）利用Floyd[19]算法，计算查询图中任意两顶点间的最小代价值$ b({v}_{i}, {v}_{j}) $及最小代价值对应的目标值$ {o}_{\sigma }({v}_{i}, {v}_{j}) $和最小目标值$ o({v}_{i}, {v}_{j}) $及最小目标值对应的代价值$ {b}_{\tau }({v}_{i}, {v}_{j}) $，同时记录$ G=(V, E) $中的最小代价值$ {b}_{\mathrm{m}\mathrm{i}\mathrm{n}} $和最小目标值$ {o}_{\mathrm{m}\mathrm{i}\mathrm{n}} $，并保存在内存中；（2）关键词倒排索引[20]构建，将兴趣点的所有关键词信息$ \{v.{w}_{1}, v.{w}_{2}, \cdots \} $组合成非重合的关键词集合，构建关键词倒排索引表，记录关键词对应的兴趣点，如表 3所示。
表 3
(Table 3)
表 3 关键词倒排索引表
Table 3 Keyword inverted index table
| 关键词 |
包含关键词的顶点集 |
| $ {w}_{1} $ |
$ {v}_{3} , {v}_{7} $ |
| $ {w}_{2} $ |
$ {v}_{8} , {v}_{9} $ |
| $ {w}_{3} $ |
$ {v}_{1} , {v}_{5} , {v}_{7}, {v}_{10} $ |
| $ {w}_{4} $ |
$ {v}_{2}, {v}_{4}, {v}_{6} $ |
|
下载CSV
表 3 关键词倒排索引表
Table 3 Keyword inverted index table
|
2）路径拓展策略
本文算法基于上述算法框架，用到的拓展策略有目标修正的近似支配剪枝和全局优先拓展剪枝。
定义6（目标修正） 给定查询图$ G=(V, E) $和查询$ Q=({v}_{s}, {v}_{t}, \varphi , {\mathit{\Delta}} ) $，已知标签$ {L}_{i}^{k} $，最小代价值$ {b}_{\mathrm{m}\mathrm{i}\mathrm{n}} $，最小目标值$ {o}_{\mathrm{m}\mathrm{i}\mathrm{n}} $，其修正目标值为$ {L}_{i}^{k}.\widehat{o}=\left\lfloor \frac{{L}_{i}^{k}.o}{\theta }\right\rfloor $，$ \theta =\frac{\varepsilon {b}_{\mathrm{m}\mathrm{i}\mathrm{n}}{o}_{\mathrm{m}\mathrm{i}\mathrm{n}}}{{\mathit{\Delta}} } $被称为修正比例，其中$ 0 < \varepsilon < 1 $。
修正目标值用于近似支配剪枝。
定理1 每个顶点最多存储标签的个数为[3]：
|
$ {L}_{\mathrm{m}\mathrm{a}\mathrm{x}}={2}^{k}\left\lfloor \frac{{\mathit{\Delta}} }{{b}_{\mathrm{m}\mathrm{i}\mathrm{n}}}\right\rfloor \left\lfloor \frac{{o}_{\mathrm{m}\mathrm{a}\mathrm{x}}{\mathit{\Delta}} }{\varepsilon {b}_{\mathrm{m}\mathrm{i}\mathrm{n}}{o}_{\mathrm{m}\mathrm{i}\mathrm{n}}}\right\rfloor $
|
其中：$ k=\left|\varphi \right| $为关键词个数。
证明 首先给定k个查询关键词，最多有$ {2}^{k} $个关键词子集。其次给定代价阈值$ {\mathit{\Delta}} $，算法检查一条路经的边数不超过$ \left\lfloor \frac{{\mathit{\Delta}} }{{b}_{\mathrm{m}\mathrm{i}\mathrm{n}}}\right\rfloor $。其中，$ {b}_{\mathrm{m}\mathrm{i}\mathrm{n}} $为查询图$ G $中最短边的代价值。因此，在$ G $中路径的目标值以$ \left\lfloor \frac{{\mathit{\Delta}} }{{b}_{\mathrm{m}\mathrm{i}\mathrm{n}}}\right\rfloor {\widehat{o}}_{\mathrm{m}\mathrm{a}\mathrm{x}}=\left\lfloor \frac{{\mathit{\Delta}} }{{b}_{\mathrm{m}\mathrm{i}\mathrm{n}}}\right\rfloor \left\lfloor \frac{{o}_{\mathrm{m}\mathrm{a}\mathrm{x}}}{\theta }\right\rfloor =\left\lfloor \frac{{\mathit{\Delta}} }{{b}_{\mathrm{m}\mathrm{i}\mathrm{n}}}\right\rfloor \left\lfloor \frac{{o}_{\mathrm{m}\mathrm{a}\mathrm{x}}{\mathit{\Delta}} }{\varepsilon {b}_{\mathrm{m}\mathrm{i}\mathrm{n}}{o}_{\mathrm{m}\mathrm{i}\mathrm{n}}}\right\rfloor $为界。综上，每个顶点最多存储的路径标签为$ {L}_{\mathrm{m}\mathrm{a}\mathrm{x}}={2}^{k}\left\lfloor \frac{{\mathit{\Delta}} }{{b}_{\mathrm{m}\mathrm{i}\mathrm{n}}}\right\rfloor \left\lfloor \frac{{o}_{\mathrm{m}\mathrm{a}\mathrm{x}}{\mathit{\Delta}} }{\varepsilon {b}_{\mathrm{m}\mathrm{i}\mathrm{n}}{o}_{\mathrm{m}\mathrm{i}\mathrm{n}}}\right\rfloor $，其他具有相同目标值的标签都会被近似支配。
定理2 经过目标修正获得的最优解$ {p}_{\mathrm{o}\mathrm{s}} $目标值与实际最优解$ {p}_{\mathrm{o}\mathrm{p}\mathrm{t}} $的目标值有如下关系：$ o\left({p}_{\mathrm{o}\mathrm{s}}\right)\le \frac{1}{1-\varepsilon }\cdot o\left({p}_{\mathrm{o}\mathrm{p}\mathrm{t}}\right) $[3]。
证明 由定义6可知，$ \widehat{o}({v}_{i}, {v}_{j})=\left\lfloor \frac{o({v}_{i}, {v}_{j})}{\theta }\right\rfloor $，$ 0 < \theta < 1 $，以下将$ \widehat{o}({v}_{i}, {v}_{j}) $、$ o({v}_{i}, {v}_{j}) $分别简称为$ \widehat{o} $和$ o $。推导可知，$ o-\theta \le \theta \cdot \widehat{o}\le o $，因此$ o\left({p}_{\mathrm{o}\mathrm{p}\mathrm{t}}\right)=\sum\limits_{e\in {p}_{{\rm{opt}}}}{o}_{e}\ge \sum\limits_{e\in {p}_{\mathrm{o}\mathrm{p}\mathrm{t}}}\theta \cdot {\widehat{o}}_{e} $（$ e $为$ p $中的边），继而：
|
$ \begin{array}{c}o\left({p}_{\mathrm{o}\mathrm{p}\mathrm{t}}\right)\ge \sum\limits_{e\in {p}_{{\rm{opt}}}}\theta \cdot {\widehat{o}}_{e}\ge \sum\limits_{{e}^{{'}}\in {p}_{{}_{{\rm{os}}}}}\theta \cdot {\widehat{o}}_{{e}^{{'}}}\ge \sum\limits_{{e}^{{'}}\in {p}_{{}_{{\rm{os}}}}}({o}_{{e}^{{'}}}-\theta )\ge \\ \sum\limits_{{e}^{{'}}\in {p}_{{}_{{\rm{os}}}}}{o}_{{e}^{{'}}}-\left\lfloor \frac{{\mathit{\Delta}} }{{b}_{\mathrm{m}\mathrm{i}\mathrm{n}}}\right\rfloor \theta \ge \sum\limits_{{e}^{{'}}\in {p}_{{\rm{os}}}}{o}_{{e}^{{'}}}-\varepsilon \cdot {o}_{\mathrm{m}\mathrm{i}\mathrm{n}}\end{array} $
|
因为$ \sum\limits_{{e}^{{'}}\in {p}_{\mathrm{o}\mathrm{s}}}{o}_{{e}^{{'}}}\ge \varepsilon \cdot {o}_{\mathrm{m}\mathrm{i}\mathrm{n}} $，所以$ o\left({p}_{\mathrm{o}\mathrm{p}\mathrm{t}}\right)\ge (1-\varepsilon )\sum\limits_{{e}^{{'}}\in {p}_{{\rm{os}}}}{o}_{{e}^{{'}}}=(1-\varepsilon )o\left({p}_{\mathrm{o}\mathrm{s}}\right) $。
定义7（近似支配） 假设给定一个稍大于1的参数$ \alpha $（如$ \alpha $=1.1），路径$ {p}_{i} $、$ {p}_{j} $的起点和终点相同，若$ {p}_{j}.\varphi \subseteq {p}_{i}.\varphi $且$ b\left({p}_{i}\right)\le b\left({p}_{j}\right)\bigcap \widehat{o}\left({p}_{i}\right)\le \alpha \cdot \widehat{o}\left({p}_{j}\right) $，则路径$ {p}_{j} $被$ {p}_{i} $近似支配，$ {p}_{j} $被剪枝。
定理3 经过近似支配的最优解$ {p}_{\mathrm{d}\mathrm{o}\mathrm{m}} $的目标值与$ {p}_{\mathrm{o}\mathrm{s}} $的目标值有如下关系：$ o\left({p}_{\mathrm{d}\mathrm{o}\mathrm{m}}\right)\le \alpha \cdot o\left({p}_{\mathrm{o}\mathrm{s}}\right) $[6]。
证明 由定义7可知，$ {p}_{j} $被$ {p}_{i} $近似支配时，$ \widehat{o}\left({p}_{j}\right) $被放大$ \alpha $倍，同理对于$ {p}_{\mathrm{d}\mathrm{o}\mathrm{m}} $和$ {p}_{\mathrm{o}\mathrm{s}} $有关系：$ o\left({p}_{\mathrm{d}\mathrm{o}\mathrm{m}}\right)\le \alpha \cdot o\left({p}_{\mathrm{o}\mathrm{s}}\right) $。
定理4 $ {p}_{\mathrm{d}\mathrm{o}\mathrm{m}} $的目标值与$ {p}_{\mathrm{o}\mathrm{p}\mathrm{t}} $的目标值有如下关系：$ o\left({p}_{\mathrm{d}\mathrm{o}\mathrm{m}}\right)\le \frac{\alpha }{1-\varepsilon }\cdot o\left({p}_{\mathrm{o}\mathrm{p}\mathrm{t}}\right) $。
证明 由定理3可知，$ o\left({p}_{\mathrm{d}\mathrm{o}\mathrm{m}}\right)\le \alpha \cdot o\left({p}_{\mathrm{o}\mathrm{s}}\right) $，联立定理2可得$ o\left({p}_{\mathrm{d}\mathrm{o}\mathrm{m}}\right)\le \alpha \cdot o\left({p}_{\mathrm{o}\mathrm{s}}\right)\le \frac{\alpha }{1-\varepsilon }\cdot o\left({p}_{\mathrm{o}\mathrm{p}\mathrm{t}}\right) $。
定义8（全局优先级） 从$ {v}_{s} $到$ {v}_{t} $的最小目标值为$ o({v}_{s}, {v}_{t}) $。设置参量$ \beta $（$ 1 < \beta < 2 $），标签$ {L}_{i}^{k} $的全局优先度表示为$ gp\left({L}_{i}^{k}\right)=\left\lfloor \mathrm{l}\mathrm{o}{\mathrm{g}}_{\beta }\left(\frac{{L}_{i}^{k}.o+o({v}_{i}, {v}_{t})}{o({v}_{s}, {v}_{t})}\right)\right\rfloor $，全局优先度越小，全局优先级越高。
3 SE-KOR算法
SE-KOR的核心思想是构建关键词顶点路径，将路径按照关键词顶点的次序分为多段并分段拓展。因此，本节重点介绍关键词顶点路径的构建和分段拓展的关键技术。
3.1 关键词顶点路径的构建
按照KOR的求解框架，预处理阶段已经计算出查询图中任意两顶点间的$ b({v}_{i}, {v}_{j}) $、$ o({v}_{i}, {v}_{j}) $，保证了任意两顶点之间都是可达的。因此，对于查询$ Q=({v}_{s}, {v}_{t}, \varphi , {\mathit{\Delta}} ) $，在构建关键词顶点路径时，可以隐藏查询图$ G=(V, E) $中没有被$ \varphi $覆盖的顶点，保留起点、终点和$ \varphi $覆盖的顶点，形成查询的关键词顶点查询图$ {G}^{{'}} $。针对$ {G}^{{'}} $进行拓展，获取满足关键词全覆盖和代价阈值的关键词顶点路径。
定义9（关键词顶点） 给定查询$ Q=({v}_{s}, {v}_{t}, \varphi , {\mathit{\Delta}} ) $，若关键词$ {w}_{i}\in {v}_{m}.\varphi $，则称$ {v}_{m} $是包含关键词$ {w}_{i} $的一个顶点，简称关键词顶点。
定义10（关键词顶点路径） 给定$ Q=({v}_{s}, {v}_{t}, \varphi , {\mathit{\Delta}} ) $，$ \varphi =\{{w}_{1}, {w}_{2}, \cdots ，{w}_{n}\} $，从$ {v}_{s} $开始不断检查未覆盖的关键词，并向相应的顶点拓展，获得从$ {v}_{s} $扩展到$ {v}_{t} $的、满足关键词全覆盖和代价阈值的路径，不失一般性，记为$ \tilde{p}=\{{v}_{s}, {v}_{{w}_{1}}, {v}_{{w}_{2}}, \cdots ，{v}_{{w}_{n}}, {v}_{t}\} $，称$ \tilde{p} $为关键词顶点路径。
定理5 给定任意可行路径，都存在一条关键词顶点路径与其一一对应。
证明 可行路径指满足关键词全覆盖、代价阈值的路径，由定义10可知，关键词顶点路径同样满足上述约束条件。
定义11（局部代价阈值） 在构建$ \tilde{p} $过程中，每拓展至一个关键词顶点，记录到达当前节点的代价值，称为局部代价阈值。
$ \tilde{p} $的构建过程如下：
1）针对查询图$ G=(V, E) $和查询$ Q=({v}_{s}, {v}_{t}, \varphi , {\mathit{\Delta}} ) $，隐藏没有被$ \varphi $覆盖的顶点，保留起点、终点和$ \varphi $覆盖的顶点，形成查询的关键词顶点查询图$ {G}^{{'}} $。在实现过程中，可以直接根据关键词倒排索引列表获取关键词顶点，形成查询图$ {G}^{{'}} $。
2）在$ {G}^{{'}} $上利用广度优先搜索，拓展满足关键词全覆盖和代价阈值的路径，记为关键词顶点路径。
3）选取目标值最小的路径记为$ {\tilde{p}}_{o} $，选取代价值最小的路径记为$ {\tilde{p}}_{b} $。
下文用一个实例说明关键词顶点路径的构建过程。在如图 3所示的查询图中，颜色和形状（菱形和三角形）相同的顶点包含相同的关键词，虚线连接的是关键词顶点路径。
在实际构建$ \tilde{p} $时，将图 3中的关键词顶点按照图 4所示的排列组合，通过广度优先搜索对其遍历，最终返回满足关键词全覆盖和代价阈值的$ \tilde{p} $。
按照图 4，以构建$ {\tilde{p}}_{o} $为例，具体拓展过程如下：
1）在$ {v}_{s} $处构建初始标签$ {L}_{s}^{0} $。
2）从起点开始向所有关键词顶点拓展，构建从$ {v}_{s} $到关键词顶点的标签$ {L}_{1}^{1} $、$ {L}_{2}^{1} $、$ {L}_{3}^{1} $、$ {L}_{4}^{1} $，并计算全局优先度后入队。
3）选取全局优先级最高的标签出队，这里假设$ {v}_{1} $顶点处的$ {L}_{1}^{1} $出队，此时$ {L}_{1}^{1} $已经包含关键词$ {w}_{1} $，向$ {L}_{1}^{1} $尚未包含的关键词$ {w}_{2} $覆盖的顶点$ {v}_{3} $、$ {v}_{4} $拓展构建标签$ {L}_{3}^{2} $、$ {L}_{4}^{2} $，并判断新标签是否满足代价阈值和近似支配条件，若满足则入队，否则被删除。
4）继续选取优先级别最高的标签拓展，重复过程3），直至拓展至终点$ {v}_{t} $，选取满足关键词全覆盖、代价阈值和目标值最小的标签记为$ {\tilde{p}}_{o} $。
拓展结果体现在如图 5所示的$ {G}^{{'}} $中，$ {v}_{2} $、$ {v}_{4} $是在构建$ \tilde{p} $时被舍弃的关键词顶点。
在构建$ \tilde{p} $的过程中，返回的目标值最小的$ \tilde{p} $记为$ {\tilde{p}}_{o} $，同时记录$ {\tilde{p}}_{o} $对应的目标值$ {O}_{\mathrm{m}\mathrm{i}\mathrm{n}} $和代价值$ {B}_{\mathrm{m}\mathrm{a}\mathrm{x}} $；返回的代价值最小的$ \tilde{p} $记为$ {\tilde{p}}_{b} $，同时记录$ {B}_{\mathrm{m}\mathrm{i}\mathrm{n}} $和$ {O}_{\mathrm{m}\mathrm{a}\mathrm{x}} $，可得$ \left[{B}_{\mathrm{m}\mathrm{i}\mathrm{n}}, {B}_{\mathrm{m}\mathrm{a}\mathrm{x}}\right] $及$ \left[{O}_{\mathrm{m}\mathrm{i}\mathrm{n}}, {O}_{\mathrm{m}\mathrm{a}\mathrm{x}}\right] $。为保证以$ \tilde{p} $为依据的路径拓展会返回有效路径，以$ {O}_{\mathrm{m}\mathrm{a}\mathrm{x}} $（即$ o\left({\tilde{p}}_{b}\right) $）作为目标值的上界，在最坏情况下返回的路径目标值为$ {O}_{\mathrm{m}\mathrm{a}\mathrm{x}} $，即以$ {\tilde{p}}_{b} $为拓展依据的路径。在拓展阶段，由$ {\tilde{p}}_{o} $和$ {\tilde{p}}_{b} $组成的关键词顶点路径边界共有以下3种情况：
1）$ {\tilde{p}}_{o} $不为空，$ {\tilde{p}}_{b} $不为空，且$ {B}_{\mathrm{m}\mathrm{i}\mathrm{n}}\le {B}_{\mathrm{m}\mathrm{a}\mathrm{x}} $、$ {O}_{\mathrm{m}\mathrm{i}\mathrm{n}}\le {O}_{\mathrm{m}\mathrm{a}\mathrm{x}} $，则在路径分段拓展中，以$ {\tilde{p}}_{o} $为准，并以$ {O}_{\mathrm{m}\mathrm{a}\mathrm{x}} $作为目标值的上界，$ {\tilde{p}}_{o} $中的局部代价阈值约束每段路径拓展。
2）$ {\tilde{p}}_{o} $为空，$ {\tilde{p}}_{b} $不为空，路径分段拓展以$ {\tilde{p}}_{b} $为准。
3）$ {\tilde{p}}_{o} $为空，$ {\tilde{p}}_{b} $为空，说明代价阈值太低，建议提高代价阈值。
由上文可知，在构建$ \tilde{p} $时获取的是目标值最小和代价值最小的2种关键词顶点路径，在实际拓展过程中根据上述3种情况选择具体拓展依据。
3.2 分段拓展和拓展方向的控制
分段拓展补充起点到关键词顶点、关键词顶点之间以及关键词顶点到终点之间的路径，如图 5中$ {v}_{s}\to {v}_{1} $、$ {v}_{1}\to {v}_{3} $、$ {v}_{1}\to {v}_{t} $的路径。
对每一分段采用广度优先搜索，根据局部代价阈值、可行解目标值的约束分别对其进行拓展。在关键词顶点路径的基础上拓展，搜索规模缩减至仅与关键词顶点路径中相关的顶点的局部图，很大程度上降低了路径查询中搜索的规模。
在分段拓展过程中的一个问题是：需要避免分段之间的交叉，即控制拓展方向避免分段之间的交叉。一种解决方案是：利用已经求出的局部代价阈值，进行局部代价阈值剪枝，约束每一段路径的代价值，从而达到控制路径方向，避免分段路径的交叉。
在对每个分段拓展时，将代价阈值约束条件替换为局部代价阈值。如图 6所示，在拓展分段$ {v}_{s}\to {v}_{1} $时，判断从$ {v}_{s} $经过白色顶点到$ {v}_{1} $的上下两条路径$ {p}_{1} $、$ {p}_{2} $的代价值$ b\left({p}_{1}\right) $、$ b\left({p}_{2}\right) $是否小于等于$ {v}_{1} $处的局部代价阈值$ {\tilde{p}}_{o}.b({v}_{s}, {v}_{1}) $，若是则入队，否则被舍弃。如此，路径拓展方向朝向违背$ \tilde{p} $的方向时，会被即时剪枝，避免各分段路径的交叉，控制拓展方向。
3.3 查询近似度分析
现有算法通过邻边拓展求取途径关键词顶点，且满足代价阈值时点与点之间的最短路径，将其划分为子问题可以看作是以关键词顶点为界的每一段路径的拼接。本质上邻边拓展方法是边拓展边判断一个顶点是否为关键词顶点。由定理5可知，任意一条可行路径与一条关键词顶点路径一一对应。而SE-KOR根据关键词倒排索引表直接获取关键词顶点，并依据预处理求取目标值最小关键词顶点路径$ {\tilde{p}}_{o} $以及代价值最小关键词顶点路径$ {\tilde{p}}_{b} $作为路径分段依据，进行分段拓展，大幅减小了搜索规模。因此，SE-KOR算法具有可行性。
在路径拓展过程中，以$ o\left({\tilde{p}}_{b}\right) $即$ {O}_{\mathrm{m}\mathrm{a}\mathrm{x}} $作为路径目标值的上界，以$ o\left({\tilde{p}}_{o}\right) $即$ {O}_{\mathrm{m}\mathrm{i}\mathrm{n}} $作为路径目标值的下界，在最坏情况下，SE-KOR以$ {\tilde{p}}_{b} $为依据将路径划分为多段。并且SE-KOR在对每段路径拓展时，依旧采用修正目标值和近似支配策略对路径进行剪枝，假设最终解为路径$ p $，联立定理2~定理4，结合关键词顶点路径中的目标值可得近似度如下：
|
$ \frac{o\left(p\right)}{o\left({p}_{\mathrm{o}\mathrm{p}\mathrm{t}}\right)}=\frac{o\left({p}_{\mathrm{d}\mathrm{o}\mathrm{m}}\right)}{o\left({p}_{\mathrm{o}\mathrm{s}}\right)}\cdot \frac{o\left({p}_{\mathrm{o}\mathrm{s}}\right)}{o\left({p}_{\mathrm{o}\mathrm{p}\mathrm{t}}\right)}\le \frac{\alpha }{1-\varepsilon }\cdot \frac{{O}_{\mathrm{m}\mathrm{a}\mathrm{x}}}{{O}_{\mathrm{m}\mathrm{i}\mathrm{n}}} $
|
由上式可知，使用SE-KOR算法返回的与最优解误差在最坏情况下不超过$ \frac{\alpha }{1-\varepsilon }\cdot \frac{{O}_{\mathrm{m}\mathrm{a}\mathrm{x}}}{{O}_{\mathrm{m}\mathrm{i}\mathrm{n}}} $，$ \alpha $是一个稍大于1的数值，在可控范围内。
3.4 算法描述
SE-KOR算法由计算关键词顶点路径的$ \mathrm{c}\mathrm{o}\mathrm{m}\mathrm{K}\mathrm{e}\mathrm{y}\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{t}\mathrm{e}\mathrm{x}\mathrm{P}\mathrm{a}\mathrm{t}\mathrm{h}\left(\right) $函数和分段拓展的主程序两部分组成。
根据第3.1节对$ {\tilde{p}}_{o} $和$ {\tilde{p}}_{b} $的分析，选取其中一条路径（$ {\tilde{p}}_{o} $或$ {\tilde{p}}_{b} $）作为拓展路径，以关键词顶点为边界将路径划分为多段进行拓展，并使用$ {\tilde{p}}_{o} $中的局部代价阈值、$ {\tilde{p}}_{b} $中目标值对路径拓展进行约束，最后拼接成完整的从起点到终点满足多约束的路径。
SE-KOR算法主程序如下：
输入 $ Q=({v}_{s}, {v}_{t}, \varphi , {\mathit{\Delta}} ) $
输出 最优路径标签Lopt
1.$ {\tilde{\mathrm{p}}}_{\mathrm{o}}, {\tilde{\mathrm{p}}}_{\mathrm{b}}\leftarrow \mathrm{c}\mathrm{o}\mathrm{m}\mathrm{K}\mathrm{e}\mathrm{y}\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{t}\mathrm{e}\mathrm{x}\mathrm{P}\mathrm{a}\mathrm{t}\mathrm{h}\left(\right) $
2.for each $ \mathrm{p}{\mathrm{v}}_{\mathrm{m}}\in \mathrm{p}{\mathrm{V}}_{\mathrm{t}} $ //$ \mathrm{p}{\mathrm{v}}_{\mathrm{m}} $为每段路径的终点
3. $ {\mathrm{\Delta }}^{\mathrm{{'}}}=\mathrm{b}({\mathrm{v}}_{\mathrm{s}}, \mathrm{p}{\mathrm{v}}_{\mathrm{m}}) $//$ {\tilde{\mathrm{p}}}_{\mathrm{o}} $中的局部代价阈值
4. while $ {\mathrm{Q}}_{\mathrm{u}} $不为空do
5. $ {\mathrm{Q}}_{\mathrm{u}} $中$ {\mathrm{L}}_{\mathrm{i}}^{\mathrm{k}} $出队；// 此处$ {\mathrm{Q}}_{\mathrm{u}} $为优先级队列
6. for each $ {\mathrm{v}}_{\mathrm{j}}\in {\mathrm{V}}_{\mathrm{j}} $ do // $ {\mathrm{V}}_{\mathrm{j}} $为邻接节点集合
7. $ {\mathrm{L}}_{\mathrm{j}}^{\mathrm{l}} $=标签操作$ ({\mathrm{L}}_{\mathrm{i}}^{\mathrm{k}}, {\mathrm{v}}_{\mathrm{j}}) $
8. if $ {\mathrm{L}}_{\mathrm{j}}^{\mathrm{l}}.\mathrm{b}\le {\mathrm{\Delta }}^{\mathrm{{'}}} $ and $ {\mathrm{L}}_{\mathrm{j}}^{\mathrm{l}}.\mathrm{o}+\mathrm{o}({\mathrm{v}}_{\mathrm{j}}, {\mathrm{v}}_{\mathrm{t}})\le \mathrm{U} $且$ {\mathrm{L}}_{\mathrm{j}}^{\mathrm{l}} $未被支配
9. 更新U
10. if $ {\mathrm{v}}_{\mathrm{j}}!=\mathrm{p}{\mathrm{v}}_{\mathrm{m}} $ then $ {\mathrm{Q}}_{\mathrm{u}} $.add（$ {\mathrm{L}}_{\mathrm{j}}^{\mathrm{l}} $）
11. if $ {\mathrm{v}}_{\mathrm{j}}==\mathrm{p}{\mathrm{v}}_{\mathrm{m}} $ and $ {\mathrm{v}}_{\mathrm{j}}!={\mathrm{v}}_{\mathrm{s}} $ then
12. $ \mathrm{t}\mathrm{e}\mathrm{m}\mathrm{p}{\mathrm{L}}_{\mathrm{o}\mathrm{p}\mathrm{t}}={\mathrm{L}}_{\mathrm{j}}^{\mathrm{l}} $并删除队列中标签
13. if $ {\mathrm{v}}_{\mathrm{j}}=={\mathrm{v}}_{\mathrm{t}} $ then $ {\mathrm{L}}_{\mathrm{o}\mathrm{p}\mathrm{t}}={\mathrm{L}}_{\mathrm{j}}^{\mathrm{l}} $
14. $ {\mathrm{Q}}_{\mathrm{u}} $.add（$ \mathrm{t}\mathrm{e}\mathrm{m}\mathrm{p}{\mathrm{L}}_{\mathrm{o}\mathrm{p}\mathrm{t}} $）
15.return $ {\mathrm{L}}_{\mathrm{o}\mathrm{p}\mathrm{t}} $
算法第2行根据第1行获取的$ \tilde{p} $将路径以关键词顶点为边界划分成为多段，每段路径的终点保存在$ p{V}_{t} $中。算法第2行~第14行表示对每段路径的拓展。算法第4行~第13行针对每段路径根据全局优先拓展（第5行）、局部代价阈值（第8行）、可行解目标值剪枝（第8行）和近似支配（第8行）剪枝策略进行拓展，每拓展至某段路径的终点，则进入下一段路径的拓展，直至获得完整路径。
计算$ {\tilde{p}}_{o} $和$ {\tilde{p}}_{b} $的函数如下：
函数 $ \mathrm{c}\mathrm{o}\mathrm{m}\mathrm{K}\mathrm{e}\mathrm{y}\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{t}\mathrm{e}\mathrm{x}\mathrm{P}\mathrm{a}\mathrm{t}\mathrm{h}\left(\right) $
输入 $ Q=({v}_{s}, {v}_{t}, \varphi , {\mathit{\Delta}} ) $
输出 最优关键词顶点路径$ {\tilde{p}}_{o} $和$ {\tilde{p}}_{b} $
1.while $ {\mathrm{Q}}_{\mathrm{u}} $不为空do //此处$ {\mathrm{Q}}_{\mathrm{u}} $为优先级队列
2. $ {\mathrm{Q}}_{\mathrm{u}} $中优先级别最高的标签$ {\mathrm{L}}_{\mathrm{i}}^{\mathrm{k}} $出队；
3. for each $ {\mathrm{w}}_{\mathrm{i}}\in {\rm{ \mathsf{ φ} }}^{\mathrm{{'}}} $do //$ {\rm{ \mathsf{ φ} }}^{{'}} $代表尚未被覆盖的关键词集合
4. for each $ {\mathrm{v}}_{\mathrm{j}}\in {\mathrm{V}}_{\mathrm{t}\mathrm{i}} $do //遍历关键词覆盖的顶点
5. $ {\mathrm{L}}_{\mathrm{j}}^{\mathrm{l}} $=标签操作$ ({\mathrm{L}}_{\mathrm{i}}^{\mathrm{k}}, {\mathrm{v}}_{\mathrm{j}}) $，记录$ {\mathrm{L}}_{\mathrm{j}}^{\mathrm{l}}.\mathrm{b} $, $ {\mathrm{O}}_{\mathrm{m}\mathrm{i}\mathrm{n}} $, $ {\mathrm{B}}_{\mathrm{m}\mathrm{a}\mathrm{x}} $
6. if $ {\mathrm{O}}_{\mathrm{m}\mathrm{i}\mathrm{n}} < \mathrm{U} $ and $ {\mathrm{B}}_{\mathrm{m}\mathrm{a}\mathrm{x}}\le \mathrm{\Delta } $ and $ {\mathrm{L}}_{\mathrm{j}}^{\mathrm{l}} $未被支配then
7. $ {\mathrm{Q}}_{\mathrm{u}} $.add（$ {\mathrm{L}}_{\mathrm{j}}^{\mathrm{l}} $）
8. if $ {\mathrm{L}}_{\mathrm{j}}^{\mathrm{l}}.{\rm{ \mathsf{ φ} }}\bigcap \mathrm{Q}.{\rm{ \mathsf{ φ} }}==\mathrm{Q}.{\rm{ \mathsf{ φ} }} $then
9. $ \mathrm{U}={\mathrm{O}}_{\mathrm{m}\mathrm{i}\mathrm{n}} $，$ {\tilde{\mathrm{p}}}_{\mathrm{o}} $=标签操作$ ({\mathrm{L}}_{\mathrm{i}}^{\mathrm{k}}, {\mathrm{v}}_{\mathrm{t}}) $
10.while $ {\mathrm{Q}}_{\mathrm{u}} $不为空do //此处$ {\mathrm{Q}}_{\mathrm{u}} $为优先级队列
11. $ {\mathrm{Q}}_{\mathrm{u}} $中优先级别最高的标签$ {\mathrm{L}}_{\mathrm{i}}^{\mathrm{k}} $出队；
12. for each $ {\mathrm{w}}_{\mathrm{i}}\in {\rm{ \mathsf{ φ} }}^{\mathrm{{'}}} $do //遍历尚未覆盖的关键词
13. for each $ {\mathrm{v}}_{\mathrm{j}}\in {\mathrm{V}}_{\mathrm{t}\mathrm{i}} $do
14. $ {\mathrm{L}}_{\mathrm{j}}^{\mathrm{l}} $=标签操作$ ({\mathrm{L}}_{\mathrm{i}}^{\mathrm{k}}, {\mathrm{v}}_{\mathrm{j}}) $，保存$ {\mathrm{L}}_{\mathrm{j}}^{\mathrm{l}}.\mathrm{b} $, $ {\mathrm{O}}_{\mathrm{m}\mathrm{i}\mathrm{n}} $, $ {\mathrm{B}}_{\mathrm{m}\mathrm{a}\mathrm{x}} $
15. if $ {\mathrm{B}}_{\mathrm{m}\mathrm{i}\mathrm{n}} < \mathrm{B} $and $ {\mathrm{B}}_{\mathrm{m}\mathrm{a}\mathrm{x}}\le \mathrm{\Delta } $ and $ {\mathrm{L}}_{\mathrm{j}}^{\mathrm{l}} $未被支配then
16. $ {\mathrm{Q}}_{\mathrm{u}} $.add（$ {\mathrm{L}}_{\mathrm{j}}^{\mathrm{l}} $）
17. if $ {\mathrm{L}}_{\mathrm{j}}^{\mathrm{l}}.{\rm{ \mathsf{ φ} }}\bigcap \mathrm{Q}.{\rm{ \mathsf{ φ} }}==\mathrm{Q}.{\rm{ \mathsf{ φ} }} $then
18. $ \mathrm{B}={\mathrm{B}}_{\mathrm{m}\mathrm{i}\mathrm{n}} $，$ {\tilde{p}}_{b} $=标签操作$ ({\mathrm{L}}_{\mathrm{i}}^{\mathrm{k}}, {\mathrm{v}}_{\mathrm{t}}) $
19.return $ {\tilde{\mathrm{p}}}_{\mathrm{o}}, {\tilde{\mathrm{p}}}_{\mathrm{b}} $
第1行~第9行表示$ {\tilde{p}}_{o} $的拓展过程，第10~第18行表示$ {\tilde{p}}_{b} $的拓展过程。采用广度优先搜索的方式在每轮拓展时，选取优先级别最高的标签出队，仅对关键词顶点拓展（第3、4行），在每个关键词顶点上构建路径标签（第5行）。并判断该标签是否满足代价阈值约束以及是否被支配，若满足条件，则记录到达此顶点代价值作为局部代价阈值，并入队（第5行~第7行）。以此类推，直至实现关键词全覆盖，选取目标值最小路径作为$ {\tilde{p}}_{o} $（第8、9行）。$ {\tilde{p}}_{b} $的拓展过程和$ {\tilde{p}}_{o} $的拓展过程类似，在此不再赘述。
运行示例：给出$ Q=\{{v}_{1}, {v}_{10}, < {w}_{1}, {w}_{2} > , 11\} $，以图 1、表 2为例，修正参数$ \varepsilon =0.5 $，修正相当于将$ o $放大22倍，近似支配参数$ \alpha =1.1 $，全局优先度参数$ \beta =1.1 $。
算法SE-KOR执行说明：由$ \mathrm{c}\mathrm{o}\mathrm{m}\mathrm{K}\mathrm{e}\mathrm{y}\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{d} $ $ \mathrm{V}\mathrm{e}\mathrm{r}\mathrm{t}\mathrm{e}\mathrm{x}\mathrm{P}\mathrm{a}\mathrm{t}\mathrm{h}\left(\right) $可知，$ {\tilde{p}}_{o} $不为空，$ {B}_{\mathrm{m}\mathrm{a}\mathrm{x}} $=11，U=$ {O}_{\mathrm{m}\mathrm{a}\mathrm{x}} $=10。获取$ {\tilde{p}}_{o} $中路径节点$ p{V}_{t}=\{{v}_{1}, {v}_{3}, {v}_{8}, {v}_{10}\} $，路径被分为s=3段。在$ {v}_{1} $处构建$ {L}_{s}^{0}=\{\mathrm{\varnothing }, 0, 0, 0\} $，$ {v}_{1}\to {v}_{3} $的终点为$ {v}_{3} $，由图 1可知，在$ {v}_{3} $处构建标签$ {L}_{3}^{1}=\{ < {w}_{1} > , \mathrm{110, 5}, 1\} $。$ {v}_{3} $到$ {v}_{8} $有两条路径，即$ {L}_{8}^{1}=\{ < {w}_{1}, {w}_{2} > , \mathrm{154, 7}, 6\} $，$ {L}_{8}^{1}=\{ < {w}_{1}, {w}_{2} > , \mathrm{154, 7}, 13\} $。可知$ {L}_{8}^{2}.b $=13，$ {\tilde{p}}_{o}.b({v}_{1}, {v}_{8}) $=6，由于$ {v}_{3}\to {v}_{8} $路径受到局部代价阈值约束（13 > 6），$ {L}_{8}^{1} $入队。$ {v}_{8} $的邻接点有$ {v}_{7} $和$ {v}_{10} $，构建标签$ {L}_{10}^{1}=\{ < {w}_{1}, $ $ {w}_{2} > , \mathrm{220, 11, 10}\} $和标签$ {L}_{7}^{1}= < {w}_{1}, {w}_{2} > , \mathrm{176, 8}, 9\} $。由于队列中还有$ {L}_{7}^{1} $，遍历并未结束。$ {L}_{7}^{1} $出队，$ {L}_{10}^{2}=\{ < {w}_{1}, $ $ {w}_{2} > , \mathrm{220, 10, 11}\} $，可知$ {L}_{10}^{2} $支配$ {L}_{10}^{1} $，最优路径标签为$ {L}_{10}^{2} $，最优路径为$ {v}_{1}\to {v}_{3}\to {v}_{7}\to {v}_{8}\to {v}_{10} $。
$ \mathrm{c}\mathrm{o}\mathrm{m}\mathrm{K}\mathrm{e}\mathrm{y}\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{t}\mathrm{e}\mathrm{x}\mathrm{P}\mathrm{a}\mathrm{t}\mathrm{h}\left(\right) $执行说明：通过关键词倒排索引表获取$ {w}_{1} $、$ {w}_{2} $对应的顶点$ {v}_{3} $、$ {v}_{7} $、$ {v}_{8} $、$ {v}_{9} $，沿目标值最小的方向拓展，有$ {L}_{3}^{1}=\{ < {w}_{1} > , \mathrm{110, 5}, 1\} $，$ {L}_{7}^{1}=\{ < {w}_{1} > , \mathrm{132, 6}, 10\} $，$ {L}_{8}^{1}=\{ < {w}_{2} > , \mathrm{154, 7}, 6\} $，以及$ {L}_{9}^{1}=\{ < {w}_{2} > , \mathrm{176, 8}, 13\} $。标签$ {L}_{3}^{1} $、$ {L}_{8}^{1} $满足代价阈值约束且不被支配，被加入队列继续拓展。由全局优先度计算公式$ gp\left({L}_{i}^{k}\right)=\left\lfloor \mathrm{l}\mathrm{o}{\mathrm{g}}_{\beta }\left(\frac{{L}_{i}^{k}.o+o({v}_{i}, {v}_{t})}{o({v}_{s}, {v}_{t})}\right)\right\rfloor $，可得$ gp\left({L}_{3}^{1}\right)=0 $，$ gp\left({L}_{8}^{1}\right)=2 $，则出队顺序为$ {L}_{3}^{1} $、$ {L}_{8}^{1} $。第二轮迭代：$ {L}_{3}^{1} $出队，向顶点$ {v}_{8} $、$ {v}_{9} $拓展，可得$ {L}_{8}^{2}=\{ < {w}_{1}, {w}_{2} > , $ $ \mathrm{154, 7}, 6\} $、$ {L}_{9}^{1}=\{ < {w}_{1}, {w}_{2} > , \mathrm{176, 8}, 13\} $。$ {L}_{8}^{2} $已经实现关键词全覆盖，向终点拓展生成标签$ {L}_{10}^{1}=\{ < {w}_{1}, {w}_{2} > , $ $ \mathrm{220, 10, 11}\} $。第三轮迭代：$ {L}_{8}^{1} $出队，向$ {v}_{3} $、$ {v}_{7} $拓展，同理$ {L}_{10}^{2}=\{ < {w}_{1}, {w}_{2} > , \mathrm{220, 10, 11}\} $，$ {L}_{10}^{2}.o={L}_{10}^{1}.o $，因此选$ {L}_{10}^{1} $为目标值最小路径。
下面分析算法的时间和空间复杂度：
1）时间复杂度
关键词顶点总数$ {V}_{\varphi }=\sum\limits_{{w}_{i}}\left|{V}_{{w}_{i}}\right| < k{V}_{\mathrm{m}\mathrm{a}\mathrm{x}} $（$ k $为关键词个数，$ {V}_{\mathrm{m}\mathrm{a}\mathrm{x}} $为关键词顶点最大个数）。由定理1可知，每个顶点标签最多为$ {L}_{\mathrm{m}\mathrm{a}\mathrm{x}}={2}^{k}\left\lfloor \frac{{\mathit{\Delta}} }{{b}_{\mathrm{m}\mathrm{i}\mathrm{n}}}\right\rfloor \left\lfloor \frac{{o}_{\mathrm{m}\mathrm{a}\mathrm{x}}{\mathit{\Delta}} }{\varepsilon {b}_{\mathrm{m}\mathrm{i}\mathrm{n}}{o}_{\mathrm{m}\mathrm{i}\mathrm{n}}}\right\rfloor $。当构建$ \tilde{p} $时，在最坏情况下，总循环次数为$ k{V}_{\mathrm{m}\mathrm{a}\mathrm{x}}{L}_{\mathrm{m}\mathrm{a}\mathrm{x}} $，复杂度为$ O({k}^{2}{V}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{2}{L}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{2}+{k}^{2}{V}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{2}{L}_{\mathrm{m}\mathrm{a}\mathrm{x}}\mathrm{l}\mathrm{g}{L}_{\mathrm{m}\mathrm{a}\mathrm{x}}) $。在一次循环中，最多产生$ k{V}_{\mathrm{m}\mathrm{a}\mathrm{x}} $个标签，判断每个标签是否满足支配要求并剪枝的复杂度为$ O\left({L}_{\mathrm{m}\mathrm{a}\mathrm{x}}\right) $，每产生一个有效标签被加入队列的复杂度为$ O\left(\mathrm{l}\mathrm{g}{L}_{\mathrm{m}\mathrm{a}\mathrm{x}}\right) $。则一次循环，复杂度为$ O\left(k{V}_{\mathrm{m}\mathrm{a}\mathrm{x}}\right(\mathrm{l}\mathrm{g}{L}_{\mathrm{m}\mathrm{a}\mathrm{x}}\left)\right) $。因此，在构建$ \tilde{p} $时，复杂度为$ O({k}^{2}{V}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{2}{L}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{2}+{k}^{2}{V}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{2}{L}_{\mathrm{m}\mathrm{a}\mathrm{x}}\mathrm{l}\mathrm{g}{L}_{\mathrm{m}\mathrm{a}\mathrm{x}}) $。
在分段拓展中，路径被划分为$ s+1 $（$ s+1\ge 1 $）段，假设有n（$ n\le \left|V\right| $）个顶点被拓展，当路径被划分为$ s+1 $段时，每段路径平均遍历$ \frac{n}{s+1} $个顶点，产生$ \frac{n}{s+1}{L}_{\mathrm{m}\mathrm{a}\mathrm{x}} $个标签。针对每段路径，算法复杂度为$ O\left(\frac{n}{s+1}{L}_{\mathrm{m}\mathrm{a}\mathrm{x}}({L}_{\mathrm{m}\mathrm{a}\mathrm{x}}+\mathrm{l}\mathrm{g}{L}_{\mathrm{m}\mathrm{a}\mathrm{x}})\right) $，则拓展$ s+1 $段路径，算法时间复杂度为$ O(n{L}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{2}+n{L}_{\mathrm{m}\mathrm{a}\mathrm{x}}\mathrm{l}\mathrm{g}{L}_{\mathrm{m}\mathrm{a}\mathrm{x}}) $。
综上，$ O\left(\right({k}^{2}{V}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{2}+n){L}_{\mathrm{m}\mathrm{a}\mathrm{x}}\mathrm{l}\mathrm{g}{L}_{\mathrm{m}\mathrm{a}\mathrm{x}}+({k}^{2}{V}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{2}+n\left){L}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{2}\right) $为总的时间复杂度。在实际查询中，关键词个数往往较少，且$ {V}_{\mathrm{m}\mathrm{a}\mathrm{x}} $和n远小于$ \left|V\right| $，因此该算法具有较高的执行效率。
2）空间复杂度
在构建$ \tilde{p} $过程中，最坏的情况下需要对关键词覆盖的每个顶点进行遍历，即需要对$ k{V}_{\mathrm{m}\mathrm{a}\mathrm{x}} $个关键词覆盖的顶点拓展，加上起点、终点则有$ k{V}_{\mathrm{m}\mathrm{a}\mathrm{x}}+2 $被拓展顶点。又因为每个顶点存储的标签上界为$ {L}_{\mathrm{m}\mathrm{a}\mathrm{x}} $，队列最多存储$ (k{V}_{\mathrm{m}\mathrm{a}\mathrm{x}}+2){L}_{\mathrm{m}\mathrm{a}\mathrm{x}} $路径标签，所以空间复杂度为$ O\left(\right(k{V}_{\mathrm{m}\mathrm{a}\mathrm{x}}+2\left){L}_{\mathrm{m}\mathrm{a}\mathrm{x}}\right) $。
在分段拓展过程中，将路径划分为$ s+1 $（$ s+1\ge 1 $）段路径。假设整条路径需要遍历n（$ n\le \left|V\right| $）个节点，当路径被划分为$ s+1 $段时，则每段路径平均遍历$ \frac{n}{s+1} $个节点，因此每个顶点标签个数的上界为$ {2}^{\frac{n}{s+1}}\cdot {L}_{\mathrm{m}\mathrm{a}\mathrm{x}} $，则$ s+1 $段路径共需维护$ (s+1){2}^{\frac{n}{s+1}}\cdot {L}_{\mathrm{m}\mathrm{a}\mathrm{x}} $个标签，空间复杂度为$ O\left(\right(s+1){2}^{\frac{n}{s+1}}\cdot {L}_{\mathrm{m}\mathrm{a}\mathrm{x}}) $。
4 实验结果与分析
上文已经给出SE-KOR的实现过程和算法步骤，本节通过实验验证SE-KOR在执行时间上的优越性，并对执行时间与近似度进行分析。
4.1 实验设定
实验设计如下：
1）实验环境与数据集
实验环境：win10，运行在Intel® CoreTM i7-8550U处理器和16 GB内存上。算法使用Java在IntelliJ IDEA上实现。数据从公开的路网数据集中下载，并随机生成关键词信息。数据集信息如表 4所示。
表 4
(Table 4)
表 4 不同规模数据查询
Table 4 Data query of different scales
| 查询图 |
顶点数 |
边数 |
顶点平均关键词数 |
| $ {G}_{1} $ |
1 869 |
4 790 |
6.63 |
| $ {G}_{2} $ |
3 066 |
6 764 |
6.15 |
| $ {G}_{3} $ |
4 261 |
10 452 |
6.33 |
| $ {G}_{4} $ |
8 261 |
20 452 |
4.68 |
|
下载CSV
表 4 不同规模数据查询
Table 4 Data query of different scales
|
2）实验设计
由于KORL的预处理阶段与SE-KOR的预处理有所不同，且面向大规模数据集，Greedy、KSRG没有实现具体路径的查找，因此仅与OSScalling、BucketBound算法对比。针对关键词个数、代价阈值、查询图规模等查询因素，设置实验1~实验3，取平均查询时间和平均近似度为评价标准。
实验1 关键词个数不同时算法的执行时间
控制数据集和代价阈值不变，改变关键词个数。查询图为$ {G}_{3} $，代价阈值为40 km，关键词个数为2、4、6、8，分别对3个算法进行测试，随机提交5个查询，取平均执行时间和平均近似度。
实验2 代价阈值不同时算法执行时间
控制数据集和关键词个数不变，改变代价阈值。查询图为$ {G}_{3} $，关键词个数是4，代价阈值为45 km、55 km、65 km、75 km、85 km，分别对3个算法进行测试，随机提交5个查询，取平均执行时间和平均近似度。
实验3 查询图规模不同时算法的执行时间
控制关键词个数和代价阈值不变，改变查询图规模。代价阈值为55 km，关键词个数为6，分别对3个算法进行测试，随机提交5个查询，取平均执行时间和平均近似度。
4.2 实验结果
本节分别给出3个查询因素下SE-KOR的执行时间和近似度的实验结果，并加以分析。
4.2.1 不同查询因素下算法的执行时间
不同查询因素下算法的执行时间主要有以下3种：
1）不同关键词个数下算法的执行时间实验1结果如图 7所示，随着关键词个数的增长，SE-KOR的执行时间明显短于对比算法，当关键词个数为2时，SE-KOR执行时间至少缩短8.0%。OSScalling是邻边拓展，当关键词个数增加时，搜索规模也随之增加。虽然BucketBound将优先级队列划分为多个bucket，但邻边拓展的本质没变。而SE-KOR将路径划分为多段，有效降低搜索规模，缩短了执行时间。
2）不同代价阈值下算法的执行时间
实验2结果如图 8所示，当代价阈值增大时，查询时间呈先增长后稳定的趋势，且SE-KOR的执行时间较BucketBound至少缩短61.0%。针对另外两种算法，当代价阈值持续增加时，最优解不会发生变化，查询时间由高趋于稳定。而SE-KOR的查询时间与构建关键词顶点路径有关，因此查询时间的峰值点与另外两种算法有所不同，但走向基本一致。
3）不同查询图规模下算法的执行时间
实验3结果如图 9所示，随着查询图规模的增大，SE-KOR的查询时间较另外两种算法缓慢增长，且SE-KOR执行时间至少缩短57.7%。随着查询图规模不断增大，另外两种算法因大量中间拓展操作，造成搜索规模越来越大。而SE-KOR将路径划分为多段拓展，能有效避免拓展过程中产生的大量拓展操作，从而显著缩短执行时间。
4.2.2 不同查询因素下的近似度分析
不同查询因素下的近似度分析主要有以下2种：
1）不同关键词个数下的近似度分析
实验1的近似度曲线如图 10所示，在不同关键词个数下，SE-KOR的近似度与另外两种算法相差无几，甚至会出现优于BucketBound的情况。而OSScalling、BucketBound求的近似解在实际最优解处波动。
2）不同代价阈值下的近似度分析
实验2的近似度曲线如图 11所示，在不同代价阈值的约束下，SE-KOR的近似度趋于稳定，而另外两种算法的近似度有所浮动。这是因为代价阈值越大，前期构建路径边界时越容易找到目标值最小关键词顶点路径。而另外两种算法依旧是逐步筛选中间路径，直到找到近似最优解，因此会有波动。
5 结束语
针对现有KOR算法在搜索长路径时执行时间较长的问题，提出SE-KOR算法将路径划分为多段并分别拓展。SE-KOR算法根据关键词倒排索引列表对关键词顶点拓展，获得目标值最小关键词顶点路径$ {\tilde{p}}_{o} $以及代价值最小关键词顶点路径$ {\tilde{p}}_{b} $，以此为依据，将路径以关键词顶点为边界节点，把路径划分为多个分段。在分段拓展中采用局部代价阈值以及综合运用近似支配、可行解目标值剪枝、全局优先拓展等剪枝策略加速拓展。实验结果表明，SE-KOR算法能够显著缩短执行时间，且不损失精度。下一步将对现有单源[21-23和全源[24-26]最短路径进行研究，提出合适拓展策略降低各个分段路径的关联度，并行拓展每个分段路径，最终将各分段路径拼接，形成完整的路径。
2022, Vol. 48
