近年来, 随着信息技术和互联网的飞速发展, 图数据作为一种重要的数据模型变得愈加重要.在很多领域, 图数据刻画了不同实体之间的相互关系, 例如社交网络^{[1, 2]}、道路交通网^[3]、生物信息网^[4]、计算机网络^[5]和Web网络^[6]等.

其中, 最短路径查询是图数据管理中的一类非常重要的研究问题.在社交网络中, 每个人都构成了图中的一个顶点, 人与人之间的联系则形成了边.社交网络中的最短路径是网络顶点影响力评判的重要因素, 小世界网络中, 直径的计算一般也是通过计算最长最短路径得到的^[7]; 在Web网络中, 数据转发时每个路由器使用路由协议和链路状态信息来识别从自己到其他路由器的最短路径, 网络拓扑通常随时间而变化, 因此, 一个高效的最短路径算法在路由计算中显得尤为重要^[8]; 在道路交通网中, 经常需要计算两个地点之间的最短路径, 有时因为一些特殊的需求还要计算最小的前k条最短路径^[9-11].

在实际应用中, 用户往往需要查询带有约束条件的最短路径.例如, 某游客去一座城市旅行, 他计划首先前往某餐馆就餐, 然后分别参观景点A~景点C, 最后返回酒店.特别地, 该游客计划在参观景点B之前先参观景点A.因此, 如何设计一条满足用户约束且代价最小的观光路径成为一个重要的问题.在该例中, 道路交通网被建模为一张图G(V, E), 则上述问题可形式化描述为:给定起点v_s和终点v_e, 寻找一条从v_s到v_e的最短路径, 使得此路径经过用户指定点集V_s⊆V中的所有点, 且某些点的访问要满足一定的先后顺序.在本文中, 该问题被称为基于规则的最短路径查询问题.

目前, 存在少量工作研究了最优路径查询问题optimal route queries(ORQ).ORQ将图G中全部顶点划分为多个不同的类别, 用户查询时, 给出起点v_s和一个访问顺序图G_Q.这里, G_Q是一个有向无环图, G_Q中的每个点都对应于G中的一个类别信息, G_Q中每条有向边(c, c')表示G中类别c优先于类别c'访问.查询结果是一条以v_s为起点且满足G_Q的最优路径.例如, 某游客计划去餐馆、酒吧和电影院, 每个类别都有多个具体的地点可供选择, 而且游客希望在去酒吧之前要先去餐馆吃饭, 因此, 他需要制定一条路线使得在满足约束条件的前提下路线的总距离最短.目前, 解决ORQ问题的精确算法的基本思想是:首先计算G_Q中所有类别的全排列(每个类别在排列中的顺序代表此类的访问顺序), 并删除访问顺序不满足约束条件的排列; 然后对于每一个排列, 依次从排列的每个类中选择一个点构成一条路径; 最终枚举出满足约束条件的所有路径, 并返回具有最短距离的路径.然而这些方法在面对基于规则的最短路径问题时, 主要存在以下两个缺点:(1)针对基于规则的路径查询问题, 对图G进行划分所得的每个类仅包含一个顶点, 即任意两点对应的类都不相同, 已有的算法求解此类问题相当于枚举出所有满足约束条件的排列, 然而大部分排列对于求解最短路径来说是冗余的; (2)目前已有的解决ORQ问题的算法面向的是空间数据库, 这些算法均通过计算两点之间的欧氏距离加速查询, 然而本文所解决的问题是基于普通的图模型, 两点间的最短距离即为最短路径的长度, 而存储全部顶点对之间的最短距离空间开销过高.因此, 本文设计了一种前向扩展算法来快速求解基于规则的最短路径问题, 其主要思想是, 尽可能早地过滤掉不能构成最短路径的子路径.真实数据集上的实验结果证明了本文提出的算法的效率远远优于传统ORQ算法.

本文的主要贡献如下:

(1) 提出了广义规则树的概念, 设计了生成广义规则树的算法, 并利用广义规则树来判断算法是否找到一条基于规则的最短路径;

(2) 设计了基于最优子路径的前向扩展算法, 该算法可以快速求解基于规则的最短路径问题, 并设计了前向扩展算法的改进算法——基于最短优先策略的前向扩展算法;

(3) 在真实的数据集上设计了大量的实验, 并与已有的性能最好的算法比较, 实验结果验证了本文算法的有效性.

本文第1节给出基于规则的最短路径查询问题的形式化定义, 并证明此类问题是NP-hard问题.第2节介绍广义规则树的概念, 并设计生成广义规则树的算法.第3节介绍一种图数据的预处理技术, 可以用来快速求解两点之间的最短路径.第4节和第5节分别介绍前向扩展算法以及基于最短优先策略的前向扩展算法, 并分别对它们的算法复杂度进行分析.第6节在真实的数据集上验证本文算法的高效性.第7节介绍相关工作.最后一节对全文进行总结.

1 问题定义

有向加权图可以表示为G(V, E, w)(简称G), V表示图G中全部顶点的集合, E表示全部边的集合.任意一条有向边e∈E可以表示为e=(v_i, v_j), 其中, v_i, v_j∈V, e称为v_i的出边或者v_j的入边, v_j(v_i)被称为v_i(v_j)的出边(入边)邻居.w是一个权重函数, 并且对图G中的每条边都赋予一个非负的权重, 本文使用w_{i, j}来表示有向边(v_i, v_j)∈E的权重, 即w_{i, j}=w(v_i, v_j).图G中的路径p是一个顶点序列, 即p=(v₁, v₂, …v_k), 其中, (v_i, v_i+1)(1≤i≤k-1)是图G中的一条有向边, 路径p的权重用w(p)表示, 表示p中全部有向边的权重之和, 即$w(p)=\sum\limits_{1\le i\le k-1}{{{w}_{i, i+1}}}$.路径p是一条简单路径当且仅当p中没有重复的顶点.对于无向图, 一条无向边(v_i, v_j)等价于两条有向边(v_i, v_j)和(v_j, v_i), 因此, 本文提出的方法也可应用到无向图上的同类问题.

本文主要研究基于规则的最短路径查询问题, 首先介绍什么是路径查询规则, 然后给出基于规则的路径定义.本文中, 路径规则用$${\mathfrak{R}}$表示, 被定义为二元组${\mathfrak{R}} $=(I, R), 包含两个元素.

(ⅰ) I是V的一个顶点子集, 即I⊆V;

(ⅱ) R是一组偏序关系〈v_i, v_j〉的集合, 其中, v_i, v_j∈I.〈v_i, v_j〉表示v_i$\prec $v_j.

需要注意的是:偏序关系集R中不存在环, 即R中不存在一个偏序关系子集{〈v₁, v₂〉, …, 〈v_k-1, v_k〉, 〈v_k, v₁〉}, 其中, 顶点v₁, v₂, …, v_k∈I.下面给出基于规则的路径定义.

定义1.1(基于规则的路径).给定图G(V, E, w), 起点为v_s, 终点为v_e, 规则$\mathfrak{R}$=(I, R), 如果路径p满足以下两个条件, 则被称为由v_s到v_e的基于规则$\mathfrak{R}$的路径.

(1) 对每一个顶点v_i∈I, 都有v_i∈p;

(2) 对每一个偏序关系〈v_i, v_j〉∈R(或者v_i$\prec $v_j), 路径p中都存在一个从v_i到v_j的子路径v_i$\rightsquigarrow$v_j.

在定义1.1中, 条件(1)是指:若路径p基于规则$\mathfrak{R}$=(I, R), 则p需要包含I中的所有点; 条件(2)是指:对R中的任意偏序关系v_i$\prec $v_j, 在路径p中都存在一条从顶点v_i到顶点v_j的子路径.

给定图G中的两个顶点v_s, v_e以及规则${\mathfrak{R}}$, 从v_s到v_e的基于规则$\mathfrak{R}$的最短路径表示为$p_{s, e, {\mathfrak{R}}}^{*}$, 是指从v_s到v_e的基于规则${\mathfrak{R}}$的所有路径中权重w(p)最小的路径.表 1列出了本文常用的符号.

例1.1:给定有向图G(V, E, w), 如图 1(a)所示, 已知规则$\mathfrak{R}$=(I, R), I={v₂, v₄, v₅, v₆}, R={v₂$\prec $v₄, v₂$\prec $v₅}, 其中, 起点为v₁, 终点为v₃, 可得此图基于规则$\mathfrak{R}$的最短路径为$p_{s, e, {\mathfrak{R}}}^{*}=({{v}_{1}}, {{v}_{3}}, {{v}_{2}}, {{v}_{4}}, {{v}_{6}}, {{v}_{5}}, {{v}_{3}})$, 如图 1(b)中的虚线箭头所示.

定理1.1. 基于规则的最短路径查询问题是一个NP-hard问题.

证明:本文通过将其归约到哈密尔顿路问题(NPC问题)证明.给定一个有向图G, 令v_s和v_e分别表示起点和终点.G中每条边的权重都设为1, 规则$\mathfrak{R}$=(I, R)被设置为I=V-{v_s, v_e}, R=Ø.显然, 图G中存在一条从v_s到v_e的哈密尔顿路当且仅当从v_s到v_e的基于规则${\mathfrak{R}}$的最短路径的长度为|V|-1(|V|表示V中顶点的个数), 而且对于一条给定的路径, 不能在多项式时间验证它是否是基于规则的最短路径, 因此, 基于规则的最短路径问题是一个NP-hard问题.证毕.

2 广义规则树

若p为一条基于规则$\mathfrak{R}$的路径, 由第1节可知:在规则$\mathfrak{R}$中, 偏序关系集R中的偏序关系v_i$\prec $v_j(v_i, v_j∈I)表示在路径p中存在一条从v_i到v_j的子路径.显然, 对I中的任意一点v_i, p中存在一条从起点v_s到v_i的子路径, 也存在一条v_i到终点v_e子路径.由于v_s和v_e分别为p的起点和终点, 因此集合I_R=I∪{v_s, v_e}中的任意点都在基于规则${\mathfrak{R}}$的路径p中, 称集合I_R为规则点集, I_R中的点称为规则点.本节提出了广义规则树的概念, 广义规则树并非真正的树, 其将规则点集I_R中的全部顶点组织成类似树的结构, 并通过树中的祖先后代关系来表示两个规则点之间的偏序关系, 即:若v_i$\prec $v_j, 则在广义规则树中, 结点v_i是结点v_j的祖先结点.与普通树区别在于, 广义规则树中的结点可能具有多个父亲结点.利用广义规则树, 本文提出的算法可以高效判断搜索到的路径p是否是一条满足规则的路径.下面首先给出广义规则树的定义, 然后给出广义规则树的生成算法.

定义2.1(广义规则树). 满足规则$\mathfrak{R}$的广义规则树是一棵由规则点集I_R中全部顶点构成的广义树, 记为${{T}_{\mathfrak{R}}}$, 其满足以下两个条件.

(1) 起点v_s为根结点、终点v_e为唯一叶结点;

(2) 对${{T}_{\mathfrak{R}}}$中除根结点和叶结点外的任意两个结点v_i, v_j, 若v_i是v_j的一个父亲结点, 当且仅当v_i$\prec $v_j; 且不存在另外一个顶点v_k∈I, 使得v_i$\prec $v_k和v_k$\prec $v_j同时成立.

广义规则树满足以下两个性质.

性质2.1. 给定起点v_s、终点v_e和规则$\mathfrak{R}$, 广义规则树${{T}_{\mathfrak{R}}}$存在且唯一.

证明:当给定起点v_s和终点v_e, ${{T}_{\mathfrak{R}}}$的根和唯一叶结点即已确定.给定规则$\mathfrak{R}$, ${{T}_{\mathfrak{R}}}$中结点的父亲-孩子关系也已确定, 故${{T}_{\mathfrak{R}}}$存在且唯一.证毕.

性质2.2. R中蕴含的任意一个偏序关系都对应广义规则树中的一对祖先后代结点.

证明:若R中蕴含v_i$\prec $v_j, 由广义规则树定义中的条件(2)可知:在${{T}_{\mathfrak{R}}}$中, v_i是v_j的祖先结点.证毕.

显然, 在广义规则树中, 起点是所有其他点的祖先结点, 终点是所有其他点的后代结点.规则点v_i∈I_R的全部父结点集合表示为$S_{i}^{p}$, 子结点集合表示为$S_{i}^{c}$, 祖先结点集合表示为$S_{i}^{a}$, 后代结点集合表示为$S_{i}^{d}$.例2.1给出了广义规则树的示例.

例2.1:给定有向图G, 如图 1(a)所示, 其中, 起点为v₁, 终点为v₃, 规则$\mathfrak{R}$=(I, R), I={v₂, v₄, v₅, v₆}, 若R=Ø, 则基于规则$\mathfrak{R}$的广义规则树如图 2(a)所示; 若R={v₂$\prec $v₄, v₂$\prec $v₅}, 此基于规则$\mathfrak{R}$的广义规则树如图 2(b)所示.

下文中, 规则点v_i∈I_R的父结点、子结点、祖先结点和后代结点均指广义规则树中对应树结点v_i的父结点、子结点、祖先结点和后代结点.例如在图 2(b)中, 规则点v₂的父结点集合$S_{2}^{p}=\{{{v}_{1}}\}$、子结点集合$S_{2}^{c}=\{{{v}_{4}}, {{v}_{5}}\}$、祖先结点集合$S_{2}^{a}=\{{{v}_{1}}\}$、后代结点集合$S_{2}^{d}=\{{{v}_{3}}, {{v}_{4}}, {{v}_{5}}\}$.

算法1展示了构造广义规则树的伪代码.初始阶段, 算法将所有的规则点初始化一棵广义树(第1行), 广义树的根设为起点v_s, 唯一叶结点设为终点v_e, I中的所有顶点都互为兄弟结点, 且它们的父结点和祖先结点都设为v_s, 子结点和后代结点都设为v_e, 因此, v_s的子结点集合和v_e的父结点集合均为I.算法1的主要思想是:依次处理R中的每一对偏序关系, 并逐步构造广义规则树.在每次迭代中, 对每个〈v_i, v_j〉∈R, 算法判断在${{T}_{\mathfrak{R}}}$中v_i是否是v_j的祖先:若是, 则忽略〈v_i, v_j〉并跳出本轮迭代(第3行~第3行); 否则, 根据〈v_i, v_j〉更新广义规则树${{T}_{\mathfrak{R}}}$.更新过程如下.

●首先, 对${{T}_{\mathfrak{R}}}$中v_i的每个子结点${{v}_{k}}\in S_{i}^{c}$, 若v_k是v_j的后代结点, 则将v_k从$S_{i}^{c}$中删除(第6行~第10行); 对${{T}_{\mathfrak{R}}}$中v_j的每个父结点${{v}_{k}}\in S_{j}^{p}$, 若v_k是v_i的祖先结点, 则将v_k从$S_{j}^{p}$中删除(第11行~第15行);

●然后, 将v_i加入v_j的父结点集合, 将v_j加入v_i的子结点集合(第16行);

●最后, 对v_j的每个祖先结点v_k, 将v_k的后代结点集合更新为$S_{k}^{a}\cup S_{i}^{a}$(第17行~第19行); 对v_i的每个祖先结点v_k, 将v_k的祖先结点集合更新为$S_{k}^{a}\cup S_{i}^{a}$(第20行~第22行).当R中的全部偏序关系处理完毕, 算法结束并返回${{T}_{\mathfrak{R}}}$.

算法1. GeneralizedRuleTree(G, v_s, v_e, $\mathfrak{R}$).

输入:图G, 起点v_s, 终点v_e, 规则$\mathfrak{R}$=(I, R);

输出:广义规则树${{T}_{\mathfrak{R}}}$.

1.用所有的规则点初始化广义树, 即:广义树的根结点为v_s, 叶结点为v_e, I中的所有顶点都互为兄弟结点, 并且它们的父结点和祖先结点都设为v_s, 子结点和后代结点都设为v_e;

2. for each 〈v_i, v_j〉∈R do

3.   if ${{v}_{i}}\in S_{j}^{a}$ then

4.      continue;

5.   end if

6.   for each ${{v}_{k}}\in S_{i}^{c}$ do

7.        if ${{v}_{k}}\in S_{j}^{d}$ then

8.           $S_{i}^{c}\leftarrow S_{i}^{c}-\{{{v}_{k}}\}, S_{k}^{p}\leftarrow S_{k}^{p}-\{{{v}_{i}}\}$;

9.       end if

10.    end for

11.    for each ${{v}_{k}}\in S_{j}^{p}$ do

12.        if ${{v}_{k}}\in S_{i}^{a}$ then

13.          $S_{j}^{p}\leftarrow S_{j}^{p}-\{{{v}_{k}}\}, S_{k}^{c}\leftarrow S_{k}^{c}-\{{{v}_{j}}\}$;

14.        end if

15.     end for

16.    $S_{j}^{p}\leftarrow S_{j}^{p}\cup \{{{v}_{i}}\}, S_{i}^{c}\leftarrow S_{i}^{c}\cup \{{{v}_{j}}\}$;

17.     for each ${{v}_{k}}\in S_{j}^{a}$ do

18.        $S_{k}^{d}\leftarrow S_{k}^{d}\cup S_{j}^{d}$

19.     end for

20.     for each ${{v}_{k}}\in S_{i}^{d}$ do

21.        $S_{k}^{a}\leftarrow S_{k}^{a}\cup S_{i}^{a}$

22.     end

23. end for

24. return ${{T}_{\mathfrak{R}}}$

例2.2:接例1.1, 利用算法1构造其对应的广义规则树.首先, 初始化广义规则树, 结果如图 3(a)所示; 当偏序关系v₂$\prec $v₄插入到广义树中后, 结点v₂的子结点集合修改为{v₄}, 结点v₄的父结点集合修改为{v₂}, 结点v₁的子结点集合修改为{v₂, v₅, v₆}, 结点v₃的父结点集合修改为{v₄, v₅, v₆}, 结果如图 3(b)所示; 当偏序关系v₂$\prec $v₅插入到广义树中后, 结点v₂的子结点集合修改为{v₄, v₅}, 结点v₅的父结点集合修改为{v₂}, 结点v₁的子结点集合修改为{v₂, v₆}, 结果如图 3(c)所示.

广义规则树${{T}_{\mathfrak{R}}}$中, 结点v_i被某路径p合法访问是指:若v_i为根结点, 则p包含v_i; 否则, p包含v_i且v_i在${{T}_{\mathfrak{R}}}$中的所有父结点都已被p中从起点v_s到v_i的子路径合法访问.定理2.1给出了路径p是否满足规则$\mathfrak{R}$的判断条件.

定理2.1.路径p为一条从起点v_s到终点v_e的路径, 若终点v_e被路径p合法访问, 则路径p为一条基于规则$\mathfrak{R}$的路径.

证明:由规则点被路径合法访问的定义可知, 集合I中的点都在路径p中.下面证明偏序关系集R中的所有偏序关系均已满足.假设存在一个偏序关系〈v_i, v_j〉∈R, 使得p不满足此偏序关系, 即p中不存在一条从v_i到v_j的子路径, 因此, 规则点v_j没有被合法访问且v_j的所有子结点也没有被合法访问.由于终点v_e是所有规则点的后代结点, 可得终点v_e没有被路径p合法访问.这与已知条件矛盾.因此, 所有的偏序关系均已满足.综上可得, 路径p为一条基于规则$\mathfrak{R}$的路径.证毕.

由定理2.1可知:可以依据一个查询的终点是否被一条路径合法访问, 来判断此路径是否为基于规则的路径.在下文介绍的前向扩展算法中, 本文依据定理2.1来判断是否已找到一条基于规则的路径.

3 分层收缩技术

分层收缩(contraction hierarchies, 简称CH)^[12]是一种简单有效的图数据预处理技术, 它可以提高最短路径的查询效率.CH本质上是预先存储一些最短路径信息, 从而实现加速最短路径查找的目的.本文采用CH技术进行预处理, 以使算法能更高效地计算两点之间的最短路径.给定图G(V, E, w), CH首先给V中所有顶点分配一个序号, 任意两个顶点的序号都不相同; 然后依据序号的大小, 按照从小到大的顺序对点进行收缩.顶点v_i被收缩是指:把v_i以及与v_i相连的边从G中删除, 并且添加一些新的边到G中.具体地, 对每一对v_i的入边(v_j, v_i)和出边(v_i, v_k), 如果路径(v_j, v_i, v_k)是连接v_j和v_k的唯一的最短路径, 则往G中添加边(v_j, v_k), 并且将边(v_j, v_k)的权重设为(v_j, v_i)和(v_i, v_k)的权重之和.所有顶点收缩完成之后, CH将原图G分为两个新图, 分别为前向图G_u和后向图G_d; 然后, CH利用G_u和G_d计算最短路径.CH技术的具体细节见文献[12].

4 FE算法

本节提出前向扩展算法(forward expanding, 简称FE)来求解基于规则${\mathfrak{R}}$的最短路径.接下来, 首先介绍最优子排列, 然后详细介绍FE算法, 最后分析了算法的时间和空间复杂度.

4.1 最优子排列

给定有向图G(V, E, w)、规则$\mathfrak{R}$=(I, R)以及起点v_s和终点v_e, 可得规则点集I_R, 令r表示I_R中点的个数, 即r=|I_R|.I_R的一个排列π是一个点序列v₁v₂…v_r, 对任意点v_i(1≤i≤r)都有v_i∈I_R, 且排列π中不包含重复的点.显然, 一个规则点集I_R总共有r!个排列.对于一个排列p, 本文用规则点在π中的次序来表示此规则点在路径p中的合法访问顺序, 即:若v_i∈I_R在π中处于第i个位置, 则在p中, v_i是第i个被合法访问的.给定排列π=v₁v₂…v_r, 如果路径p满足下面3个条件, 称p为一条对应于p的路径, 记为p|_π.

(1) 对π中任意点v_i, p中都包含点v_i;

(2) 若π中点v_i的位置在v_j之前, 则p中包含一条从v_i到v_j的子路径;

(3) 路径p的起点和终点分别为v₁和v_r.

给定路径p|_π, 它可以被π中的所有点划分为r-1条子路径v₁$\rightsquigarrow $v₂, v₂$\rightsquigarrow$v₃, …, v_r-1$\rightsquigarrow$v_r.每条子路径v_i$\rightsquigarrow$v_i+1(1≤ i≤r-1)都被称为p|_π的一个路径片段.本文使用S_p|π来表示p|_π的所有路径片段.

在例1.1中, 路径$p_{s, e, {\mathfrak{R}}}^{*}=({{v}_{1}}, {{v}_{3}}, {{v}_{2}}, {{v}_{4}}, {{v}_{6}}, {{v}_{5}}, {{v}_{3}})$是一个对应于排列π=v₁v₂v₄v₆v₅v₃的路径, 此时, S_p|π={(v₁, v₃, v₂), (v₂, v₄), (v₄, v₆), (v₆, v₅), (v₅, v₃)}.下面给出基于规则的排列定义.

定义4.1(基于规则的排列).给定图G(V, E, w), 起点为v_s, 终点为v_e, 规则${\mathfrak{R}}$=(I, R), π是规则点集I_R的一个排列.已知条件:(1) π起始位置和末尾位置的顶点分别为v_s和v_e; (2)对每一个偏序关系〈v_i, v_j〉∈R(或者v_i$\prec $v_j), π中v_i的位置都在v_j之前.若排列π满足上述两个条件, 则称π为从v_s到v_e的基于规则${\mathfrak{R}}$的排列.所有基于规则${\mathfrak{R}}$的排列构成的集合记为${{\Pi }_{{{v}_{s}}, {{v}_{e}}, {\mathfrak{R}}}}$, 即, ${{\Pi }_{{{v}_{s}}, {{v}_{e}}, {\mathfrak{R}}}}$, 中所有排列都以v_s为起始位置顶点、v_e为末尾位置顶点且满足规则${\mathfrak{R}}$.

由定义4.1可知:若π为一个基于规则${\mathfrak{R}}$的排列, 则p|_π为一个基于规则${\mathfrak{R}}$的路径.如果路径p是对应于排列π的路径, 且p中的所有路径片段均为最短路径, 本文称p为对应于排列p的最短路径, 记为p^*|_π.由此可以得到下面的定理:

定理4.1.给定图G(V, E, w), 起点为v_s, 终点为v_e, 规则${\mathfrak{R}}$=(I, R), 若p^*是I_R的所有基于规则的排列所对应的p^*|_π中权重最小的一条路径, 则p^*即为基于规则${\mathfrak{R}}$的最短路径.

证明:给定I_R的一个基于规则${\mathfrak{R}}$的排列π, 因为p^*|_π中的所有路径片段都是最短路径, 因此p^*|_π的权重不大于π所对应的每一条路径p|_π的权重; 又因为p^*是所有基于规则的排列所对应的p^*|_π中权重最小的一条路径, 而且所有的p^*|_π都是基于规则${\mathfrak{R}}$的路径, 因此, p^*为基于规则${\mathfrak{R}}$的最短路径.证毕.

由定理4.1可知:对于一个基于规则的排列p, 只有当π所对应的路径p|_π中的所有路径片段都为最短路径时, 即p|_π为p^*|_π, 此路径才有可能成为基于规则的最短路径.因此, 本文后续部分所提到的任意排列π所对应的路径都特指p^*|_π, 即所有的路径片段都为最短路径.

对于点集V_s⊆V, 可以逐步扩展点序列的长度来得到V_s的排列, 其中, 点序列中的每个点都属于V_s, 且点序列中不包含重复的顶点.如果点序列中包含l个顶点, 本文称此点序列为V_s的l-子排列(特别地, 本文规定:规则点集I_R的所有子排列均以起点v_s作为起始位置的顶点), 记为π_l, 其中, 1≤l≤r(r=|V_s|).包含π_l中l个顶点的点集合称为子排列π_l对应的点集, 记为${{V}_{{{\pi }_{l}}}}$.给定一个排列π, π⊕v表示π扩展一个顶点后形成的新排列, 这称为排列的扩展操作, 其中, ⊕是一个连接符, 即, 把点v添加到π的末尾.若${{\pi }_{{{l}_{1}}}}$和${{\pi }_{{{l}_{2}}}}$分别为V_s的l₁-子排列和l₂-子排列, 已知条件: (1) l₁≤l₂; (2) ${{\pi }_{{{l}_{2}}}}$经由${{\pi }_{{{l}_{1}}}}$扩展0个或多个顶点得到.如果${{\pi }_{{{l}_{1}}}}$和${{\pi }_{{{l}_{2}}}}$满足条件(1)和条件(2), 则称${{\pi }_{{{l}_{1}}}}$为${{\pi }_{{{l}_{2}}}}$的前缀.例如, v₁v₂是v₁v₂v₃v₄的前缀.下面本文给出子排列满足的规则的定义.

定义4.2(子排列满足的规则${\mathfrak{R}}$'=(I', R')).给定图G(V, E, w), 起点为v_s, 终点为v_e, 规则${\mathfrak{R}}$=(I, R), π_l为I_R的l-子排列(1≤l≤|I_R|)且π_l起始位置的顶点为v_s.${\mathfrak{R}}$'=(I', R'), 其中, I'⊆I, R'⊆R, 已知条件:(1) π_l是I'的一个排列; (2)对任意偏序关系〈v_i, v_j〉∈R', 都有v_i, v_j∈I'且π_l中v_i的位置在v_j之前; (3)不存在偏序关系〈v_i, v_j〉∈R-R', 使得v_i, v_j∈I'.若规则${\mathfrak{R}}$'满足上述3个条件, 则称${\mathfrak{R}}$'为子排列π_l满足的规则.

利用定义4.2, 可以很容易地给出最优子排列定理.

定理4.2. 给定图G(V, E, w), 起点为v_s, 终点为v_e, 规则${\mathfrak{R}}$=(I, R), 若I_R的排列π对应的路径p|_π为基于规则${\mathfrak{R}}$的最短路径, π_l为π的包含l(1≤l≤|I_R|)个顶点的前缀, π_l满足的规则为${\mathfrak{R}}$'=(I', R'), v^*是π_l末尾位置的顶点, 对任意排列${{{\pi }'}_{l}}\in {{\Pi }_{{{v}_{s}}, {{v}^{*}}, {\mathfrak{R}}'}}$, 都有$w(p{{|}_{{{{{\pi }'}}_{l}}}})\ge w(p{{|}_{{{\pi }_{l}}}})$, 本文称π_l为I_R的一个最优子排列.

证明:假设存在一个${{{\pi }'}_{l}}\in {{\Pi }_{{{v}_{s}}, {{v}^{*}}, {\mathfrak{R}}'}}$且${{{\pi }'}_{l}}$不等于π_l, 使得$w(p{{|}_{{{{{\pi }'}}_{l}}}}) < w(p{{|}_{{{\pi }_{l}}}})$, 将π的前缀π_l替换为${{{\pi }'}_{l}}$得到I_R的一个新的排列p', 显然, π'同样为基于规则${\mathfrak{R}}$的排列且w(p|_π') < w(p|_π).这与p|_π为基于规则${\mathfrak{R}}$的最短路径矛盾, 假设不成立.因此, 对任意的排列${{{\pi }'}_{l}}\in {{\Pi }_{{{v}_{s}}, {{v}^{*}}, {\mathfrak{R}}'}}$, 都有$w(p{{|}_{{{{{\pi }'}}_{l}}}})\ge w(p{{|}_{{{\pi }_{l}}}})$.证毕.

给定有向图G(V, E, w)如图 1(a)所示, 已知规则${\mathfrak{R}}$=(I, R), I={v₂, v₄, v₅, v₆}, R=Ø, 起点为v₁, 终点为v₃, 可得排列π=v₁v₂v₄v₆v₅v₃对应的路径p|_π=(v₁, v₃, v₂, v₄, v₆, v₅, v₃)为基于规则${\mathfrak{R}}$的最短路径, π₄=v₁v₂v₄v₆为π的包含4个顶点的前缀, v₆是π₄末尾位置的顶点, π₄满足的规则为${\mathfrak{R}}$'=(I', R'), 其中, I'={v₁, v₂, v₄, v₆}, R'=Ø, ${{\Pi }_{{{v}_{1}}, {{v}_{4}}, {\mathfrak{R}}'}}=\{{{\pi }_{4}}={{v}_{1}}{{v}_{2}}{{v}_{4}}{{v}_{6}}, {{{\pi }'}_{4}}=$ v₁v₄v₂v₆}, π₄和${{{\pi }'}_{4}}$分别对应的路径为$p{{|}_{{{\pi }_{4}}}}=({{v}_{1}}, {{v}_{3}}, {{v}_{2}}, {{v}_{4}}, {{v}_{6}})$和$p{{|}_{{{{{\pi }'}}_{4}}}}=({{v}_{1}}, {{v}_{3}}, {{v}_{2}}, {{v}_{4}}, {{v}_{5}}, {{v}_{3}}, {{v}_{2}}, {{v}_{4}}, {{v}_{6}})$.显然,

$ w(p{{|}_{{{\pi }_{4}}}}) <w(p{{|}_{{{{{\pi }'}}_{4}}}}). $

推论4.1. 给定图G(V, E, w), 起点为v_s, 终点为v_e, 规则${\mathfrak{R}}$=(I, R), 已知I_R的长度为l(1≤l≤|I_R|)的一个子排列p_l, π_l起始位置的顶点为v_s、末尾位置的顶点为v^*, π_l满足的规则为${\mathfrak{R}}$'=(I', R'), 则扩展操作得到的子排列集合${{\Pi }_{{{v}_{s}}, {{v}^{*}}, {\mathfrak{R}}'}}$中, 存在一个子排列${{{\pi }'}_{l}}$, 使得对任意的${{{\pi }''}_{l}}\in {{\Pi }_{{{v}_{s}}, {{v}^{*}}, {\mathfrak{R}}'}}$, 都有$w(p{{|}_{{{{{\pi }'}}_{l}}}})\le w(p{{|}_{{{{{\pi }''}}_{l}}}})$, I_R的排列π对应的路径p|_π为基于规则${\mathfrak{R}}$的最短路径, 若π的长度为l的前缀属于${{\Pi }_{{{v}_{s}}, {{v}^{*}}, {\mathfrak{R}}'}}$, 将π的长度为l的前缀替换为${{{\pi }'}_{l}}$得到新的排列p', 则w(p|_π')= w(p|_π), 本文称${{{\pi }'}_{l}}$为I_R的一个最优子排列.

推论4.1的结论是显然的.因此, 对于${{\Pi }_{{{v}_{s}}, {{v}^{*}}, {\mathfrak{R}}'}}$中的排列, 只需保留对应路径具有最小权重的任意一个排列, 即只需保留最优子排列.基于推论4.1, 可以设计一个前向扩展算法来求解基于规则${\mathfrak{R}}$的最短路径, 在第4.2节, 本文将详细介绍此算法.

4.2 前向扩展算法

本节提出求解基于规则${\mathfrak{R}}$的最短路径的前向扩展算法, 算法的主要思想是:从规则点集I_R的1-子排列逐步进行扩展操作直至I_R的r-子排列(r=|I_R|), 并利用最优子排列对生成的子排列进行过滤, 最终返回I_R的r-子排列对应的路径中权重最小的那条路径.

前向扩展算法的伪代码见算法2.

算法2. FE(G, v_s, v_e, ${\mathfrak{R}}$).

输入:图G, 起点v_s, 终点v_e, 规则${\mathfrak{R}}$=(I, R);

输出:$p_{s, e, {\mathfrak{R}}}^{*}$.

1. ${{T}_{\mathfrak{R}}}$←GeneralizedRuleTree(G, v_s, v_e, ${\mathfrak{R}}$);

2.利用NN算法得到路径p_g;

3. θ←w(p_g);

4. π₁←v_s;

5. ${{R}_{1}}\leftarrow \{p{{|}_{{{\pi }_{1}}}}\}$;

6. for l=2 to r=|I_R| do

7.    R_l←Ø;

8.   依据点集${{V}_{{{\pi }_{l-1}}}}$将R_l-1划分为不同的集合;

9.    for each v∈I_R-{v_s} do

10.      for each划分R_l-1得到的集合${{{R}'}_{l-1}}$ do

11.        R'←Ø;

12.        for each $p{{|}_{{{\pi }_{l-1}}}}\in {{{R}'}_{l-1}}$ do

13.          if π_l-1不包含v且v的所有父结点均已被$p{{|}_{{{\pi }_{l-1}}}}$合法访问then

14.              π_l←π_l-1⊕v;

15.             ${R}'\leftarrow {R}'\cup \{p{{|}_{{{\pi }_{l}}}}\}$;

16.        end if

17.     end for

18.     查找R'中具有最小权重的路径, 记为${{p}^{*}}{{|}_{{{\pi }_{l}}}}$;

19.      if $w({{p}^{*}}{{|}_{{{\pi }_{l}}}})\le \theta $ then

20.          ${{R}_{l}}\leftarrow {{R}_{l}}\cup \{{{p}^{*}}{{|}_{{{\pi }_{l}}}}\}$;

21.      end if

22.     end for

23.    end for

24. end for

25.查找R_r中具有最小权重的路径, 记为$p_{s, e, {\mathfrak{R}}}^{*}$;

26. return $p_{s, e, {\mathfrak{R}}}^{*}$;

给定图G(V, E, w), 起点为v_s, 终点为v_e, 规则${\mathfrak{R}}$=(I, R), FE首先调用算法1得到广义规则树${{T}_{\mathfrak{R}}}$(第1行); 然后, 利用下文相关工作部分介绍的启发式算法NN求解得到基于规则${\mathfrak{R}}$的路径p_g, 令θ等于p_g的权重(第2行、第2行); 第4行~第24行, FE逐步扩展规则点集I_R的1-子排列直至I_R的r-子排列(r=|I_R|).在构建I_R的1-子排列时, 因为只有π₁=v_s这一个1子排列满足规则, 因此, FE将R₁初始化为{v_s}(第4行、第5行); 第6行~第24行, FE循环得到I_R的2-子排列至r-子排列.下面将详细介绍FE求解I_R的l-子排列的过程, 其中, 2≤l≤r.

FE用R_l来存储I_R的l子排列所对应的路径:首先, 将R_l初始化为空集(第7行); 然后, FE对长度为l-1的子排列进行扩展操作, 并利用最优子排列理论过滤不可能成为基于规则的最短路径所对应排列的前缀.依据子排列π_l-1对应的点集${{V}_{{{\pi }_{l-1}}}}$, FE将R_l-1划分为不同的集合, 即属于同一集合里的路径拥有相同的点集${{V}_{{{\pi }_{l-1}}}}$, 属于不同集合的路径拥有不同的点集${{V}_{{{\pi }_{l-1}}}}$(第8行).接下来, FE依次遍历规则点集I_R中除v_s之外的其他所有点(第9行), 并对每一个v∈I_R-{v_s}做如下操作:遍历划分R_l-1得到的每一个集合${{{R}'}_{l-1}}, {{{R}'}_{l-1}}$中的每一条路径都与一个长度为l-1的子排列所对应, 对于${{{R}'}_{l-1}}$中的每一条路径$p{{|}_{{{\pi }_{l-1}}}}$及相应的π_l-1, 如果π_l-1中不包含点v且v的所有父结点均已被$p{{|}_{{{\pi }_{l-1}}}}$合法访问, 那么将v添加到π_l-1的末尾构成长度为l的子排列π_l并且生成相应的路径$p{{|}_{{{\pi }_{l}}}}$, 若${{{R}'}_{l-1}}$中的每一条路径均已完成上述操作, 则从新生成的路径中选择一条权重最小的路径, 记为${{p}^{*}}{{|}_{{{\pi }_{l}}}}, {{p}^{*}}{{|}_{{{\pi }_{l}}}}$即为一个最优子排列, 如果${{p}^{*}}{{|}_{{{\pi }_{l}}}}$的权重不大于θ, 则将${{p}^{*}}{{|}_{{{\pi }_{l}}}}$添加到R_l中(第10行~第22行).

FE求得I_R的r-子排列所对应的路径之后, 由于I_R的r子排列所对应的路径的最后一个顶点为终点v_e, 由定理2.1可知, I_R的r子排列所对应的路径都为基于规则${\mathfrak{R}}$的路径, 显然, 基于规则${\mathfrak{R}}$的最短路径即为I_R的r子排列所对应的路径中权重最小的一条.第25行、第26行, FE首先遍历R_r得到具有最小权重的路径, 然后返回此路径作为基于规则${\mathfrak{R}}$的最短路径.

例4.1:接例1.1, 利用FE算法求解基于规则${\mathfrak{R}}$的最短路径的过程见表 2, 其中, π_l表示一个子排列, |π_l|表示子排列中包含顶点的个数, ${{V}_{{{\pi }_{l}}}}$表示π_l对应的点集, v^*表示π_l的最后一个顶点, $p{{|}_{{{\pi }_{l}}}}$表示π_l所对应的路径.用贪心算法求解得到基于规则${\mathfrak{R}}$的路径p_g=(v₁, v₃, v₂, v₄, v₅, v₃, v₂, v₄, v₆, v₅, v₃), θ=w(p_g)=12.加删除线的子排列表示被最优子排列过滤掉的子排列, 从表 2的结果可得, 最优子排列可以减少算法在求解过程中生成的子排列个数, 从而降低算法的求解时间.FE算法最终得到的排列为p=v₁v₂v₄v₆v₅v₃, 所对应的路径为p|_π=(v₁, v₃, v₂, v₄, v₆, v₅, v₃), w(p|_π)=8, 因此, p|_π即为基于规则${\mathfrak{R}}$的最短路径.

4.3 复杂度分析 4.3.1 时间复杂度.

FE的时间复杂度主要集中在计算I_R的长度为1至r(r=|I_R|)的子排列上, 对于长度为l(1≤l≤r)的子排列, 由最优子排列可知, FE至多生成$rC_{r}^{l}$个, 其中, $C_{r}^{l}$表示I_R中顶点的组合数.因此, FE至多生成$\sum\nolimits_{l=1}^{r}{rC_{r}^{l}}$个子排列.本文采用CH技术求解两点之间的最短路径, 它的时间复杂度为O(nlogn+m)(n=|V|, m=|E|), 因此, FE的时间复杂度为O((nlogn+m)·(r·2^r)).

4.3.2 空间复杂度.

FE需要利用长度为l-1的子排列来求解长度为l的子排列, 因为FE至多生成$rC_{r}^{l}$个长度为l(2≤l≤r)的子排列, 因此在求解长度为l的子排列时, 内存的总消耗为$O(n\cdot rC_{r}^{l-1}+n\cdot rC_{r}^{l})$; 一旦求得长度为l的子排列之后, 即可将存储长度为l-1的子排列的内存释放.因此, FE所消耗的内存最大为$O\left( {\mathop {\max }\limits_{l = 2}^r (n \cdot rC_r^{l - 1} + n \cdot rC_r^l)} \right) = O(n \cdot r \cdot {2^r}),$即, FE的空间复杂度为O(n·r·2^r).

5 FEBF算法

本节提出FE算法的改进算法——基于最短优先策略的前向扩展算法(forward expanding based on best-first searching, 简称FEBF).接下来, 本文首先分析如何对FE算法进行改进; 然后给出基于最短优先策略的前向扩展算法, 并对算法做出详细的介绍; 接着, 对FEBF算法提出了几个优化技术; 最后, 分析了FEBF算法的时间和空间复杂度.

5.1 基于最短优先策略的前向扩展算法

从第4.2节可知, FE算法依次扩展规则点集I_R的长度为1至长度为r(r=|I_R|)的子排列, 最后从长度为r的子排列对应的路径中选择权重最小的路径作为问题的解.在求解长度为l的子排列时, FE必须先求得长度为l-1的所有子排列.事实上, 某些长度为l-1的子排列所对应路径的权重已大于基于规则${\mathfrak{R}}$的最短路径的权重, 因此没有必要对这部分子排列进行扩展操作.在例4.1中长度为3的子排列v₁v₆v₂对应路径为(v₁, v₃, v₂, v₄, v₆, v₅, v₃, v₂), 其权重为9, 而基于规则${\mathfrak{R}}$的最短路径权重为8, 因此, 没有必要再对子排列v₁v₆v₂进行扩展操作.基于此, 本文提出基于最短优先策略来逐步扩展路径的算法, 算法的主要思想是:在对子排列进行扩展操作时, FEBF首先从已有的子排列中选择一个对应路径的权重最小的一个子排列, 然后对它进行扩展操作, 并得到对应的路径, 所有规则点扩展结束之后, FEBF删除这个子排列, 然后重复上述操作, 直至找到一个基于规则${\mathfrak{R}}$的排列, 它所对应的路径即为基于规则${\mathfrak{R}}$的最短路径.

FEBF算法本质上也是逐步扩展I_R的长度为1的子排列到长度为r的子排列, 它采用最短优先的策略尽可能少地计算I_R的子排列, 从而可以尽快找到问题的解.FEBF算法的伪代码见算法3.

算法3. FEBF(G, v_s, v_e, ${\mathfrak{R}}$).

输入:图G, 起点v_s, 终点v_e, 规则${\mathfrak{R}}$=(I, R);

输出:$p_{s, e, {\mathfrak{R}}}^{*}$.

1.定义一个优先级队列Q, Q中的元素为元组〈π, w(p|_π)〉且以w(p|_π)的大小进行从小到大排序;

2. ${{T}_{\mathfrak{R}}}$←GeneralizedRuleTree(G, v_s, v_e, ${\mathfrak{R}}$);

3.利用NN算法得到路径p_g;

4. θ←w(p_g);

5.将Ω中的每一个元素的值初始化为∞;

6. π₁←v_s;

7.将$\langle {{\pi }_{1}}, w(p{{|}_{{{\pi }_{1}}}})\rangle $插入到Q中;

8.弹出Q的队首元素〈π', w(p|_π')〉, 令v^*为π'末尾位置的点;

9. while v^*≠v_e do

10.    for each v∈I_R-{v_s} do

11.      if π'不包含v且v的所有父结点均已被p|_π'合法访问then

12.       π←π'⊕v;

13.        if ${{\mathit{\Omega} }_{v, {{V}_{\pi }}}}>w(p{{|}_{\pi }})$ then

14.          ${{\mathit{\Omega} }_{v, {{V}_{\pi }}}}\leftarrow w(p{{|}_{\pi }})$;

15.         将〈π, w(p|_π)〉插入到Q中;

16.        end if

17.      end if

18.    end for

19.   弹出Q的队首元素〈π', w(p|_π')〉, 令v^*为π'末尾位置的点;

20. end while

21. $p_{s, e, {\mathfrak{R}}}^{*}\leftarrow p{{|}_{{{\pi }'}}}$;

22. return $p_{s, e, {\mathfrak{R}}}^{*}$;

给定图G(V, E, w), 起点为v_s, 终点为v_e, 规则${\mathfrak{R}}$=(I, R), FEBF利用优先级队列实现从已有子排列中选出具有最小权值的路径及其相应的子排列.算法首先定义优先级队列Q, Q中存储的元素为二元组, 记为〈π, w(p|_π)〉, 其中, π为I_R的子排列, 并用w(p|_π)的值进行优先级比较, 以实现对Q中的元素从小到大进行排序(第1行).接下来调用算法1得到广义规则树${{T}_{\mathfrak{R}}}$(第2行), 然后用NN算法求解得到基于规则${\mathfrak{R}}$的路径p_g, 令θ等于p_g的权重(第3行、第4行).为了利用最优子排列过滤子排列, FEBF逐步构建最优子排列表(记为Ω)来存储已得到的最优子排列.当扩展得到子排列π_l时, FEBF首先查找最优子排列表中对应位置的元素(记为${{\mathit{\Omega} }_{{{v}^{*}}, {{V}_{{{\pi }_{l}}}}}}$, 其中, v^*为π_l末尾位置的顶点, ${{V}_{{{\pi }_{l}}}}$为子排列π_l对应的点集), 然后对${{\mathit{\Omega} }_{{{v}^{*}}, {{V}_{{{\pi }_{l}}}}}}$和$w(p{{|}_{{{\pi }_{l}}}})$进行比较:若${{\mathit{\Omega} }_{{{v}^{*}}, {{V}_{{{\pi }_{l}}}}}}>$ $w(p{{|}_{{{\pi }_{l}}}})$, 则将${{\mathit{\Omega} }_{{{v}^{*}}, {{V}_{{{\pi }_{l}}}}}}$的值设为$w(p{{|}_{{{\pi }_{l}}}})$且保留子排列π_l并对其进行后续操作; 否则, 删除子排列π_l.FEBF将最优子排列表中每一个元素的值都初始化为∞(第5行).接下来, FEBF将逐步扩展子排列直至找到基于规则${\mathfrak{R}}$的排列(第6行~第20行).

在构建I_R的1-子排列时, 因为只有π₁=v_s这一个1子排列满足规则, 因此, FEBF将$\langle {{\pi }_{1}}, w(p{{|}_{{{\pi }_{1}}}})\rangle $插入到优先级队列Q中(第6行、第7行), 然后弹出Q的队首元素〈π', w(p|_π')〉, 令v^*为π'末尾位置的点(第8行).如果v^*=v_e(第9行), 则表示π'是一个基于规则${\mathfrak{R}}$的排列(由定理2.1可得), 又因为Q每次弹出的位于队首的元素都具有最小的路径权重, 因此, p|_π'即为基于规则${\mathfrak{R}}$的最短路径, FEBF返回此路径作为问题的解(第21行、第22行); 否则(v^*≠v_e), 执行以下循环操作(第10行~第19行).首先, FEBF依次遍历规则点集I_R中除v_s之外的其他所有点(第10行), 然后对每一个v∈I_R-{v_s}做如下操作:如果π'中不包含点v且v的所有父结点均已被p|_π'合法访问, 那么将v添加到π'的末尾构成新的子排列π, 若${{\mathit{\Omega} }_{v, {{V}_{\pi }}}}>w(p{{|}_{\pi }})$, 则将${{\mathit{\Omega} }_{v, {{V}_{\pi }}}}$的值设为w(p|_π), 并将〈π, w(p|_π)〉插入到Q中(第11行~第17行).若I_R-{v_s}中的每个点均已完成上述操作, 则FEBF弹出Q的队首元素〈π', w(p|_π')〉, 令v^*为π'末尾位置的点(第19行), 然后开始下一轮循环.

例5.1:接例1.1, 利用FEBF算法求解基于规则${\mathfrak{R}}$的最短路径.

FEBF首先生成〈v₁, 0〉并把它插入到优先级队列Q中, 接下来的操作是:

从Q中弹出〈v₁, 0〉, 利用它扩展得到〈v₁v₂, 2〉, 〈v₁v₆, 5〉并分别插入到Q中;

从Q中弹出〈v₁v₂, 2〉, 利用它扩展得到〈v₁v₂v₄, 3〉, 〈v₁v₂v₅, 4〉, 〈v₁v₂v₆, 5〉并分别插入到Q中;

从Q中弹出〈v₁v₂v₄, 3〉, 利用它扩展得到〈v₁v₂v₄v₅, 4〉, 〈v₁v₂v₄v₆, 5〉并分别插入到Q中;

从Q中弹出〈v₁v₂v₅, 4〉, 利用它扩展得到〈v₁v₂v₅v₄, 7〉, 〈v₁v₂v₅v₆, 9〉并分别插入到Q中;

从Q中弹出〈v₁v₂v₄v₅, 4〉, 利用它扩展得到〈v₁v₂v₄v₅v₆, 9〉并插入到Q中;

从Q中弹出〈v₁v₆, 5〉, 利用它扩展得到〈v₁v₆v₂, 9〉并插入到Q中;

从Q中弹出〈v₁v₂v₆, 5〉, 利用它扩展得到〈v₁v₂v₆v₄, 10〉, 〈v₁v₂v₆v₅, 7〉并分别插入到Q中;

从Q中弹出〈v₁v₂v₄v₆, 5〉, 利用它扩展得到〈v₁v₂v₄v₆v₅, 7〉并插入到Q中;

从Q中弹出〈v₁v₂v₅v₄, 7〉, 利用它扩展得到〈v₁v₂v₅v₄v₆, 9〉并插入到Q中;

从Q中弹出〈v₁v₂v₆v₅, 7〉, 利用它扩展得到〈v₁v₂v₆v₅v₄, 10〉并插入到Q中;

从Q中弹出〈v₁v₂v₄v₆v₅, 7〉, 利用它扩展得到〈v₁v₂v₄v₆v₅v₃, 8〉并插入到Q中;

从Q中弹出〈v₁v₂v₄v₆v₅v₃, 8〉且满足路径搜索终止条件, 此时算法终止, FEBF返回(v₁, v₃, v₂, v₄, v₆, v₅, v₃)作为问题的解.

在例4.1中, FE算法总共生成24个子排列; 而在例5.1中, FEBF总共生成18个子排列.显然, FEBF能有效减少算法生成的子排列个数.

5.2 优化技术

本节提出3个优化技术来提高FEBF算法的效率.

●缓存机制

给定I_R的基于规则${\mathfrak{R}}$的两个不同排列p和π', 这两个排列对应的路径p^*|_π'和p|_π'可能包含一些相同的路径片段, 因此这些相同的路径片段本质上只需要计算一次.本文可以采用缓存机制, 将计算过的路径片段存储在内存中, 这样就可以避免大量重复的计算, 从而提高算法的效率.比如在例4.1中, 长度为6的排列v₁v₂v₄v₆v₅v₃和v₁v₂v₄v₆v₅v₃所对应的路径包含相同的路径片段v₁$\rightsquigarrow$v₂和v₂$\rightsquigarrow$v₄, 因此当采用缓存机制后, 这两个路径片段仅仅只需要计算一次, 当再次需要计算这两个路径片段时, 可以直接从缓存中读取出来.实验结果验证了缓存机制可以有效避免大量的冗余计算.

●排列过滤

当FE对长度为l-1的子排列π_l-1进行扩展操作时, 它首先判断规则点v∈I_R是否已在π_l-1中, 然后再判断v的所有父结点是否已被路径$p{{|}_{{{\pi }_{l-1}}}}$合法访问, 若上述两个条件都满足, 则将v添加到π_l-1的末尾构成长度为l的子排列π_l.上述两个条件本质上是从规则点v是否应该被合法访问这个角度判断v是否应该添加到π_l-1的末尾, 本文也可以从路径权重的角度来进一步过滤生成的排列, 即:已知v_i, v_j∈I_R且v_j已被添加到π_l-1的末尾构成π_l-1⊕v_j, v^*是π_l-1末尾位置的顶点, 如果v^*到v_j的最短路径是v^*到v_i最短路径的子路径, 则v_i不应被添加到p_l-1的末尾构成π_l-1⊕v_i.下面的定理保证了排列过滤的正确性.

定理5.1. 给定长度为l-1的子排列π_l-1, v^*是π_l-1末尾位置的顶点, 已知v_i, v_j$\rightsquigarrow$I_R, π_l-1⊕v_j和π_l-1⊕v_i分别为FE用v_j和v_i对π_l-1进行扩展操作得到的长度为l的子排列, 如果v^*到v_j的最短路径是v^*到v_i最短路径的子路径, 则I_R的所有基于规则${\mathfrak{R}}$且以π_l-1⊕v_i为前缀的排列π都对应一个I_R基于规则${\mathfrak{R}}$且以π_l-1⊕v_j为前缀的排列π', 且w(p|_π')≤w(p|_π).

证明:不失一般性, 设π_l-1=v₁v₂…v^*是I_R的长度为l-1的子排列, π_l-1⊕v_j和π_l-1⊕v_i分别为FE用v_j和v_i对π_l-1进行扩展操作得到的长度为l的子排列, 已知v^*到v_j的最短路径是v^*到v_i最短路径的子路径.

设π=v₁v₂…v^*v_i…v_kv_jv_x…v_r为I_R的基于规则${\mathfrak{R}}$的一个排列, 显然, π'=v₁v₂…v^*v_jv_i…v_kv_x…v_r也为I_R的基于规则${\mathfrak{R}}$的一个排列, π_l-1⊕v_i和π_l-1⊕v_j分别为π和π'的前缀, 因为任意排列对应的路径包含的所有路径片段均为最短路径, 因此p|_π中的路径片段v^*$\rightsquigarrow$v_i可以分解为p|_π'中的两个路径片段v^*$\rightsquigarrow$v_j和v_j$\rightsquigarrow$v_i, 而且分解前后路径的权重不变.此外, p|_π中的路径片段v_k$\rightsquigarrow$v_j和v_j$\rightsquigarrow$v_x的权重之和大于等于p|_π'中的路径片段v_k$\rightsquigarrow$v_x的权重.

综上可得w(p|_π')≤w(p|_π).证毕.

在例4.1中, 对于长度为2的子排列v₁v₂, 可以分别用点v₄, v₅, v₆对v₁v₂进行扩展操作, 从而得到v₁v₂v₄, v₁v₂v₅, v₁v₂v₆.因为从v₂到v₄的最短路径(v₂, v₄)是从v₂到v₅最短路径(v₂, v₄, v₅)的子路径, 也是从v₂到v₆最短路径(v₂, v₄, v₆)的子路径, 因此可以过滤掉子排列v₁v₂v₅和v₁v₂v₆.

●权重预估

当FE扩展长度为l-1的子排列得到长度为l的子排列π_l时, v^*是π_l末尾位置的顶点.对于I_R的所有基于规则${\mathfrak{R}}$且以π_l为前缀的排列p, 可以估计w(p|_π)的下限, 从而使得FE可以尽量早的过滤掉一些排列, 提高算法的效率.具体的做法是:当得到π_l后, 首先计算$w(p{{|}_{{{\pi }_{l}}}})$, 然后计算从v^*到终点v_e的最短路径的权重, 然后得到这两个路径的权重之和w^*, 若w^* > θ, 则舍弃子排列p_l; 否则保留π_l.

5.3 复杂度分析

本文首先分析FEBF的时间复杂度, 对于长度为l(1≤l≤|I_R|)的子排列, FEBF至多生成$rC_{r}^{l}$个, 因为本文采用CH技术求解两点之间的最短路径, 因此, FEBF的时间复杂度为O((nlogn+m)·(r·2^r))(n=|V|, m=|E|); 接下来分析算法的空间复杂度, FEBF的优先级队列Q中至多存储O(r·2^r)个元素, 每个元组至多消耗的内存为O(n), 除此之外, 最优子排列表W消耗的内存至多为O(r·2^r), 因此, FEBF的空间复杂度为O(n·r·2^r+r·2^r)=O(n·r·2^r).

6 实验分析

本节使用不同规模的真实数据集来验证算法的有效性, 并与解决同类问题中已有的最好算法作对比.第6.1节介绍了实验的基本设置, 第6.2节对实验的结果进行分析.

6.1 实验设置

本文的所有算法都使用C++语言实现, 并在Linux操作系统环境下进行测试, 硬件的信息为:Intel(R) Core(TM) i7-4770K, 32GB RAM.本文对每组实验重复100次, 并把平均值作为此组实验的结果.如果一个算法在某个数据集上的运行时间超过24h或者超过32GB RAM, 则忽略此算法在这个数据集上的运行结果.

●数据集

本文使用8个真实数据集来验证本文提出的算法, 其中4个为道路交通网数据集(http://www.dis.uniroma1.it/challenge9/index.shtml ), 另外4个为非道路交通网数据集(http://snap.stanford.edu/data/), 数据集的详细信息见表 3, d表示顶点的平均度的大小.对于道路交通网数据集, 本文将两点之间的距离作为边的权重; 对于非道路交通网数据集, 本文给每一条边随机生成一个1~100之间的值作为此边的权重值.

●查询集

对于每个数据集, 本文生成25个查询集Q1~Q25, 它们分别对应不同规模的规则${\mathfrak{R}}$.在现实生活中, I的规模一般不超过10, 本文从实际应用的角度设计了以下的查询集.对于Q1~Q5, |R|=5, I中顶点的个数依次为6~10;对于Q6~Q10, |I|=8, R中偏序关系个数依次为4, 6, 8, 10, 12;对于Q11~Q15, R=Ø, I中顶点的个数依次为6~10;对于Q16~Q20, I中顶点的个数依次为6~10, 对应的R中偏序关系个数依次为15, 21, 28, 36, 45;对于Q21~Q25, |R|=10, I中顶点的个数依次为16~20.注意到:查询集Q11~Q15中偏序集个数为0, 此问题退化为广义旅行商问题; Q16~ Q20中的偏序集可以构成一个全序集, 即I中顶点的合法访问顺序已确定, 此问题退化为最优序列路径查询问题.Q21~Q25中规则${\mathfrak{R}}$的规模较大, 是用来验证算法能否应用于输入规模较大的情形.对于上述所有的查询集, I中所有的顶点以及起点v_s和终点v_e都是采用随机数的方式随机生成, R中偏序关系也是随机从对应的I中选择两个点构成且保证R中不存在两个相同的偏序关系.

●对比算法

对每一组实验, 本文将算法FE、FEBF与算法SBS和SFS作对比, SBS^[13]和SFS^[13]是同类问题的已有算法中性能最好的精确算法.本文不与其他的算法对比的原因是:(1) BBS^[13]和BFS^[13]分别为SBS和SFS的优化算法, 主要是解决当I中包含的不是点而是类别信息时, 随着每个类中包含顶点的个数增多, 导致搜索空间增大的问题, 当每个类中只包含一个顶点时, 优化前后的算法性能相同; (2) NN^[14]是一个启发式算法, 它最终返回的路径是一条接近最优的路径, 而本文的算法返回的是一条最优的路径.

●其他

由于SBS和SFS都为应用于空间数据集上的算法, 在空间数据集上可以直接利用经纬度坐标求得两点之间的欧氏距离, 而本文所设计的算法均应用于普通的图数据, 即, 由点和边构成的数据, 考虑到对比的公平性, 本文对所有的算法均利用CH技术来求解两点之间的最短距离.

6.2 结果分析

●查询效率

在查询集Q1~Q5上算法的运行结果如图 4所示.可以看出:对于每一个数据集, SFS的查询时间都大于其他算法的查询时间, FE算法的查询时间明显小于SBS和SFS的查询时间, FEBF算法的查询时间小于其他所有算法, 即使在具有百万个顶点的数据集(FLA)上, FEBF也能在1s左右得到查询的结果.因为查询集Q1~ Q5具有相同个数的偏序关系, 随着规则点集的规模逐渐增大, 规则点集的基于规则${\mathfrak{R}}$的排列也逐渐增多, 因此算法的查询时间也逐渐增多, 图中的结果验证了这一点, 即:从Q1~Q5, 所有算法的查询时间都逐渐增多.显然, 改进后的FEBF算法比原始的FE算法性能有较大的提高.

图 5展示了算法在查询集Q6~Q10上的查询结果.对于所有的数据集, SFS具有最大的查询时间, FEBF算法的查询时间小于其他所有算法.因为查询集Q6~Q10具有相同个数的规则点, 随着R中偏序关系的逐渐增多, 规则点集的基于规则${\mathfrak{R}}$的排列将逐渐减少.可以看出对于所有算法, Q6~Q10的查询时间都逐渐减小.

查询集Q11~Q15中包含的偏序关系个数为0, 此问题退化为广义旅行商问题, 算法的查询结果如图 6所示.因为Q11~Q15的偏序关系个数为0, 则规则点集的任意排列都为基于规则${\mathfrak{R}}$的排列, 算法的查询时间显然大于在Q1~Q5上的查询时间.对于每一个数据集, FEBF的查询时间都小于其他算法的查询时间.

查询集Q16~Q20的偏序集可以构成一个全序集, 即I中顶点的合法访问顺序已确定, 此问题退化为最优序列路径查询问题, 算法的查询结果如图 7所示.由于每个类中仅包含一个顶点, 因此, Q16~Q20本质上为计算|I|+1个最短路径.从图中可知:对于每一个数据集, SBS算法的查询时间都是最短的.这是因为SBS没有利用其他的优化策略来过滤子排列, 而对于Q16~Q20来说, 基于规则${\mathfrak{R}}$的子排列只有一个, 因此, SBS可以快速地求解得到问题的解.FE和FEBF算法由于利用了一些过滤子排列的优化技术(Q16~Q20并不需要对子排列进行过滤), 从而增加了算法的运行时间.然而在现实生活中, 这种查询几乎不存在(退化为普通的最短路径问题).

查询集Q21~Q25对应的规则${\mathfrak{R}}$规模较大, 因此算法的运行时间较长.在此, 本文仅给出算法FEBF的查询时间.从图 8的结果来看:即使在规则${\mathfrak{R}}$的规模较大时, 本文的FEBF算法也可以在一定时间内给出问题的解.

●改进后的算法有效性

FEBF算法是FE算法的改进算法, 图 9展示了FE和FEBF算法在查询集Q11~Q15上的加速比(加速比是指FE算法的查询时间与FEBF算法的查询时间的比值), 结果表明:在每个数据集上, 随着规则点个数的增多, 加速比越来越大.显然, 改进后的FEBF算法的运行效率极大地优于FE算法的运行效率.

FE和FEBF算法的查询时间主要与生成的子排列个数有关:生成的子排列越多, 查询时间则越长; 反之, 查询时间则越短.因此, 本文用子排列的减少比$\frac{{{N}_{FE}}-{{N}_{FEBF}}}{{{N}_{FE}}}$(N_FE表示FE算法生成的子排列个数, N_FEBF表示FEBF算法生成的子排列个数)来反映FE和FEBF算法的性能优劣, 结果如图 10所示.对于道路交通网数据集, FEBF算法生成的子排列个数比FE算法生成的子排列个数降低了至少20%;对于非道路交通网数据集, FEBF算法生成的子排列个数相比于FE算法生成的子排列个数也有所降低.

●优化技术的有效性

对于FEBF算法, 本文提出了3个优化技术.图 11展示了在查询集Q11~Q15上, FEBF算法在未使用优化技术与使用优化技术两种情况下的加速比(即未使用优化技术的FEBF算法的查询时间与使用优化技术的FEBF算法的查询时间的比值), 结果表明:在每个数据集上, 相对于未使用优化技术的FEBF算法, 使用优化技术的FEBF算法能够有效降低算法的查询时间.

7 相关工作

本节介绍相关的工作, 并把最短路径问题分为传统的最短路径问题和ORQ问题.ORQ问题又细分为如下几类:已指定必须经过类别的访问顺序、未指定必须经过类别的访问顺序、部分指定必须经过类别的访问顺序.下面分类依次介绍相关的工作.

●传统的最短路径问题

传统的最短路径问题具有不同的应用场景.稠密距离图(dense distance graph, 简称DDG)是平面图的分解图, 即:将一个平面图分解为几个区域, 每个区域所包含的顶点个数最多为r, 其中, r < n, n为平面图中包含的顶点个数.Shay等人^[15]提出了一种求解稠密距离图上的最短路径的算法, 并从理论上证明了所提的算法优于已有的最优算法.对于一个有向加权图, 如果它的权重存在负值, 称此图为实有向加权图, Fahim等人^[16]提出了一种实有向加权图上的单源最短路径算法, 此算法可以快速检测路径中是否包含权值为负的环路, 且性能优于已有的算法.对于规模较大的加权图, Qiu等人^[17]提出了一种并行最短路径距离查询框架——ParaPLL, ParaPLL能够快速给出大规模加权图上的最短路径的距离, ParaPLL通过使用共享内存和消息传递来实现最短路径距离的并行计算.给定起点v_s和终点v_e, 重路由序列是一系列从v_s到v_e的最短路径序列, 使得在序列中相邻的两个最短路径只有一个顶点不相同.Paul^[18]研究了最短路径重路由问题(即:给定图G中从v_s到v_e的两条最短路径P和Q, 是否存在从P到Q的重路由序列), 并给出了求解最短路径重路由问题的动态规划方法.进化图序列是指一系列静态图序列, 它本质上是随时间变化的时序图, 在每一时刻的图快照都对应于进化图序列中的一张静态图.Ren等人^[19]研究了进化图序列上的最短路径查询问题, 并提出了解决方案框架——FVF.Jihye等人^[20]提出了基于磁盘的大规模动态图上的最短路径查询算法, 此算法可以有效求解边的插入或删除以及边权重的增加或减少情况下的最短路径查询问题.Hasan^[21]提出了针对稀疏图的top-k最短路径查询算法, 该算法较已有的top-k最短路径算法有明显的性能提升.对于有向无环图, Matus等人^[22]提出了计算两点之间的近似最短路径算法, 即:给定起点v_s和终点v_e以及权重阈值L, 该算法返回一条从v_s到v_e权重不超过L的路径.

●已指定必须经过类别的访问顺序

已知必须经过的类别集合, 若已规定所有类别的访问顺序, 则ORQ问题称为类别全序的最优路径查询问题.R-LORD^[23]是一个精确算法, 用来求解空间数据集上类别全序的最优路径查询问题, 假设p^*=(v_s, v₁, v₂, …, v_r, v_e)是上述问题的一个最优路径, 则p^*的任意一个后缀p在p中都是最短的, P是满足下面两个条件的路径集合: (1)以p的起点作为起点; (2)与p相同的顺序访问p中的所有类.基于此, R-LORD采用动态规划的方式逐步构建最优后缀表.在构建最优后缀表之前, R-LORD利用贪心算法得到一条满足类别访问顺序的路径, 并用此路径的权重作为阈值来过滤不可能成为最优路径的后缀.在构建最优后缀表时, R-LORD利用椭圆剪枝技术来排除无法构成最优路径的子路径.Michael等人提出了基于动态规划的算法求解类别全序的最优路径查询问题^[24], 此算法主要是逐步构建一个实值矩阵X, X是一个r行g列的矩阵, 其中, r表示必须经过的类别个数, g表示规模最大的类中包含的顶点个数.矩阵的每个元素X[i, j]是一个最优子路径的长度, 此路径表示从起点到访问顺序为i的类别中的第j个顶点的最优子路径.此外, Michael还设计了两个优化技术, 分别为图结构优化和问题结构优化, 并通过剪枝策略来解决由于类别规模过大导致算法运行时间过长的问题.由于本文所研究的问题对类别的访问顺序只做了部分的限制, 即, 并未完全指定每个类别的访问顺序, 因此, 上述两个算法都无法用来求解本文所研究的问题.

●未指定必须经过类别的访问顺序

已知必须经过的类别集合, 若没有规定任何类别的访问顺序, 则ORQ问题称为类别无序的最优路径查询问题.对于空间数据集, Li等人提出了几个近似算法来求解类别无序的最优路径查询问题^[25].A_NN^[25]是一个近似算法, 其主要思想是:从单个起点构成的路径p'开始, 反复地从G中选择一个离p'末尾顶点最近的点(记为v^c), 且v^c对应的类别c尚未被p'访问, 然后将v^c添加到p'的末尾构成新的p'.重复上述操作, 直至所有的类别都已被p'访问, 最后将终点添加到p'的末尾, 从而构成一条包含指定所有类别的路径.A_MD^[25]也是一个近似算法, 它的主要思想是:对于每一个必须访问的类c, 从类c中选择一个顶点v^c, 使得v^c离起点和终点的距离之和小于其他任意点离起点和终点的距离之和, 从每个类中选择得到的点构成集合V_C, 然后调用A_NN算法(此处在调用A_NN算法时, 将G中的点替换为V_C中的点), 从而得到一条包含指定所有类别的路径.LESS^[26]是一个求解此类问题的精确算法, 它的本质是将指定的所有类别进行全排列, 每个类别在排列中的位置表示此类别在路径中被访问时所处的位置.对于每一个排列, 按顺序依次从排列的类别中选择一个顶点, 最终构成一条包含指定所有类别的路径. LESS枚举出所有排列对应的所有路径, 然后选择一条长度最小的路径作为问题的最优解.由于本文所研究的问题对类别的访问顺序做了部分的限制, 而上述算法只能解决访问顺序没有限制的情况, 因此, 上述两个算法都无法用来求解本文所研究的问题.

●部分指定必须经过类别的访问顺序

已知必须经过的类别集合, 若已规定部分类别的访问顺序, 则ORQ问题称为类别偏序的最优路径查询问题.NN^[14]是求解类别偏序的最优路径查询问题的启发式算法, 它最终返回一条接近最优的路线, 算法的具体流程为:从单个起点构成的路径p'开始, 反复地从G中选择一个离p'末尾顶点最近的点(记为v^c), 且v^c对应的类别c在图G_Q(G_Q是查询图且是一个有向无环图, G_Q中的每个点都对应于G中的一个类别信息, G_Q中每条有向边(c, c')表示G中类别c的点先于类别c'的点访问)中且入度为0, 然后, 从G_Q中删除类别c以及与它相连的边, 接着将v^c添加到p'的末尾构成新的p'.重复上述操作, 直至G_Q中不包含任何点, 最终找到一条满足约束条件的路线.Li等人提出了4个精确算法来求解在空间数据集上的此类问题^[13], 它们分别为SBS, BBS, SFS和BFS. SBS利用R-LORD^[23]中提出的后缀最优定理, 逐步求解1后缀到r后缀(r为必须经过的类别的个数), 然后, 从r后缀中选择一个路径长度最小的路径作为此问题的最优解.BBS是SBS的优化算法, 对于每一个必须经过的类别, BBS首先将具有相同类别的点进行聚类, 即, 把彼此距离较近的一些点归为同一组, 然后, BBS以每一个组的点为单位, 执行与SBS相同的操作, 当每个类中包含的点的个数较多时, BBS可以很大程度地提高算法的运行效率.SFS本质上是采用分层回溯的方式求解问题的解, 算法运行时所处的层数表示此时已得到的子路径所包含的类别个数.SFS采用NN^[14]添加顶点的方式, 每次选择离当前路径末尾顶点最近的一个点, 每往路径中添加一个新的顶点, 则意味着SFS进入到当前层的下一层, 然后再执行相同的添加顶点的操作.当算法到达第r层后, 则表明此算法已找到一条满足约束的路径, 然后算法回溯到r-1层, 将离当前路径末尾顶点次近的点添加到路径的末尾.重复上述回溯操作, 直至得到所有满足约束的路径, 最后返回一条最优的路径.BFS是SFS的优化算法, 与BBS类似, BFS首先将具有相同类别的点进行聚类, 即, 把彼此距离较近的一些点归为同一组, 然后, BFS以每一个组的点为单位, 执行与SFS相同的操作, 最终得到问题的最优解.由于本文所研究的问题是基于普通的图数据而非空间数据, 因此上述4个算法无法直接应用于本文所研究的问题, 而且这些算法较少过滤掉不可能成为最优路径的子路径, 使得算法的运行时间较长.

广义旅行商问题是传统旅行商问题的变种, 带优先级约束的旅行商问题属于广义旅行商问题的一种, 它可以描述为:已知n个城市之间的相互距离, 现有一旅行商计划全部访问这n个城市, 并且每个城市只能访问一次, 在访问这些城市时必须满足一定的约束条件(例如, 必须先访问城市1和城市2, 然后才能访问城市3), 最后, 旅行商返回到出发的城市, 目的是寻找一条旅行商行走的路线, 使得此路线满足上述约束条件且具有最小的距离. Ascheuer等人^[27]提出了基于分支切割的算法来解决不对称的有约束条件的旅行商问题.Moon等人^[28]和Wang等人^[29]分别采用遗传算法和整数规划的方式解决带有约束条件的旅行商问题; 有优先约束的哈密顿路径问题(Hamiltonian path problems with precedence constraints)又称为顺序排序问题(sequential ordering problem), 可描述为寻找由指定的起点前往指定的终点的最短路径查询问题, 途中经过其他所有顶点有且只有一次, 而且顶点之间存在先后顺序约束, Karan等人^[30]提出了一个基于分支界限法的算法来解决顺序排序问题.已有的解决广义旅行商问题的精确算法本质上为枚举出每一种可能的路径, 因此这些算法不适用于大规模图上问题的求解, 而本文所提的算法可以很好地应用于大规模图上的查询.

8 总结

本文设计了一个基于最优子路径的前向扩展算法, 该算法可以快速求解基于规则的最短路径查询问题, 并设计了前向扩展算法的改进算法——基于最短优先策略的前向扩展算法.从实验的结果来看, 基于最短优先策略的前向扩展算法对原始算法的查询效率有很大程度的提高.本文在真实的数据集上设计了大量的实验, 并与已有的性能最好的算法作比较, 实验结果表明, 本文的算法大幅度优于已有的算法.