动态有向超图中限制不交B-路算法设计

doi:10.12677/AAM.2022.114203

期刊菜单

动态有向超图中限制不交B-路算法设计
Design of Restricted Disjoint B-Path Algorithm in Dynamic Directed Hypergraph

DOI: 10.12677/AAM.2022.114203, PDF, HTML, XML, 科研立项经费支持
作者: 米文燕, 张淑蓉：太原理工大学，数学学院，山西太原
关键词: 有向超图；容错性；动态网络；B-路；不交路径；Directed Hypergraph； Fault Tolerance； Dynamic Network； B-Path； Disjoint Path

摘要: 超图在现实生活中有很重要的应用价值，比如信息传递、货物运输、商品配送等问题都可以归约到超图中建立数学模型并设计优化算法。而网络环境是会随时间发生连续动态变化的，故本文主要研究动态超图中的连通性问题。同时，由于大规模网络中故障的发生是不可避免的，而且是极具破坏性的，所以，提高网络的生存性能，保证网络的容错性有很重要的研究价值。设计不交超路径是提高网络容错性的主要解决方案。由于超路中B-路有很好的结构性质和广泛的应用背景，因此，本文在时变超图网络中考虑满足时间限制的不交B-路构建问题。目前由于动态网络研究的复杂性，连续时间动态网络背景的处理方法大多是采用时间离散化转换为静态网络去求近似解，本文考虑当给定起始时刻时，在时间范围[0,Τ]内每条超弧的延迟函数为连续时间动态函数的情况下，针对不交B-路问题给出最优解的求解算法，并证明算法的正确性及运算复杂度。

Abstract: Hypergraph has very important application value in real life, for example, information transmission, goods transportation, commodity distribution and other problems can be reduced to hypergraph to establish mathematical model and design optimization algorithm. The network environment will change continuously and dynamically with time, so this paper mainly studies the connectivity problem in dynamic hypergraph. At the same time, the occurrence of faults in large-scale networks is inevitable and extremely destructive. Therefore, it has important research value to improve the survival performance of networks and ensure the fault tolerance of networks. Designing disjoint hyperpath is the main solution to improve network fault tolerance. Because the B-path in hyperpath has good structural properties and wide application background, we consider the construction of disjoint B-paths satisfying time constraints in time-varying hypergraph networks in this paper. At present, due to the complexity of dynamic network research, most of the processing methods of continuous time dynamic network background adopt time discretization to static network to obtain approximate solutions. However, in this paper, when the starting time is given, the delay function of each super-arc within the time range [0,Τ] is continuous time dynamic function, the algorithm for solving the optimal solution of the disjoint B-path problem is given. Finally, the correctness and computational complexity of the algorithm are proved.

文章引用：米文燕, 张淑蓉. 动态有向超图中限制不交B-路算法设计[J]. 应用数学进展, 2022, 11(4): 1857-1869. https://doi.org/10.12677/AAM.2022.114203

1. 引言

超图作为一般图的推广，将点集合视为超边的结构特点使其在网络中的应用可以有效反应多层次的节点关系并得到广泛研究 [1] [2] [3]。特别是有向超图涉及多个学科领域，如人工智能 [4] [5]、数据库 [6]、运筹学 [7] [8] 等。同时，在许多现实问题中，不同时刻下的运输成本或运输量、信息的传输过程，都会有所不同，会随时间发生连续变化，因此，研究动态超图中的路由设计是亟待解决的问题之一。在动态网络中，通信网络节点或链路在信息传输时因受到干扰或攻击发生故障，会对网络功能产生影响，为了提高网络容错性，在主功能路径的基础上设计备份路径来传输信息是有效的解决方案。因此，在动态超网络背景下设计动态不交路是重要的研究课题。

超图中B-路具有很好的结构性质和应用背景。早在1989年，学者Italiano和Nanni [9] 证明了在超图中的最短B-路问题是NP-难问题。到1993年，Gallo等学者 [10] 提出在有向超图中，当网络中的超弧满足权值函数递增且不存在负圈时最短B-路问题是可以多项式时间内解决的，并给出最短B-树算法。但现实网络中往往会存在故障风险，为保证服务连续性，最常见的解决方案是设计备份路径，保证网络的容错性。

为了提高网络的容错性能，已经有不少学者研究了一般图中静态不交路的问题。早在1974年，Suurballe [11] 利用最短路径的标记方法给出了在静态网络中查找k条min-sum内部节点不相交路由算法。在1984年，Suurballe等人 [12] 又提出在静态网络中查找两条min-sum边不相交路由算法。之后很多研究者先后研究了不交路minsum-minmin [13] [14]、minsum-minmax [15] 等优化问题。虽然关于静态网络中不交路问题的研究已经很成熟，但动态超网络中的相关研究还很少。

目前，由于动态网络结构的复杂性，大量文献的研究成果都采用了时间离散化的方法，将时变赋权函数(延迟，容量，能耗等)的时间范围进行离散化，把时变网络上的动态问题简化为静态问题。由此对问题进行简化并得到近似解 [16] [17]，但近似度的提高需要以时间细化程度为代价，增加了运算时间的复杂性。因此为了设计有效算法并获得最优解，一些学者对连续时间动态网络问题进行了研究。比如，在解决与时间相关的最短路径(TDSP)问题上，Ding [18] 等人在先进先出(FIFO)连续时变网络中寻找TDSP问题的最优解，并提出时间复杂度为 $O ((n \log n + m) α (T))$ 的有效算法，在给定时间区间 $[0, T]$ 内 $α (T)$ 个子时间段中均得到了最优路径。Wang等人 [19] 采用了一种层次图划分的方法解决TDSP问题，并给出时间复杂度为 $O (\log_{2}^{2} \cdot k_{f} \cdot n \cdot \log_{2}^{2} α (T))$ 的算法，其中 $k_{f}$ 是图划分得到的最小子图的个数。由于超图结构关系较复杂，在超图背景下与动态路径设计的相关文献还很缺乏。本文在一般超图 $V_{Π} = \cup_{e_{i} \in E_{Π}} e_{i}$ ， $V_{Π} \subseteq V$ 相关工作的基础上研究动态超图中的限制不交B-路问题，即在动态网络中，当时间范围是 $[0, T]$ 且在某一固定时刻出发时从源点到汇点的两条内部不交B-路。本文主要在于保证网络中两条路径的节点和超弧均是动态不交的，并且均在 $[0, T]$ 内可以到达目标节点。

本文结构如下：第二节阐述了超图和动态超图中的基本概念；第三节分为两部分，第一部分提出在连续时间动态超网络中找一条 $[0, T]$ 时间范围内的限制动态B-路算法，第二部分研究动态超图网络中的限制不交B-路并给出有效算法，同时在本节中对算法进行实例说明，证明了算法的正确性并计算了时间复杂度，之后，将动态不交B-路算法推广到动态不交F-路算法；第四部分总结全文。

2. 模型建立

2.1. 超图

定义1 (超图 [10] ) 一个超图 $H = (V, E)$ 是一个有序对，其中 $V = {v_{1}, v_{2}, \dots, v_{n - 1}, v_{n}}$ 表示节点集， $E = {e_{1}, e_{2}, \dots, e_{m}}$ 表示超弧集，并且对于 $\forall i = 1, 2, \dots, m$ ，有 $e_{i} \subseteq V$ 。特别的，当 $| e_{i} | = 2$ 时，超图就是一般图。超图 $H$ 的大小定义为超弧基数的和：

$s i z e (H) = \sum_{e_{i} \in E} | e_{i} |$

一个有向的超弧e是一个有序对， $e = (T (e), H (e))$ ， $T (e)$ 和 $H (e)$ 分别为弧e的尾节点和头节点集合， $T (e) \cap H (e) = ϕ$ 。当 $| H (e) | = 1$ 时，超弧e被称为B-弧。设 $F S (v)$ 为尾节点包含节点v的超弧， $F S (v) = {e \in E : v \in T (e)}$ ， $B S (v)$ 为头节点包含节点v的超弧， $B S (v) = {e \in E : v \in H (e)}$ 。由有向超弧组成的超图称为有向超图。下文中，为简便，将有向超图简写为超图。

定义2 (简单路P [10] ) 给定超图 $H (V, E)$ ，其中 $V = {v_{1}, v_{2}, \dots, v_{n - 1}, v_{n}}$ ， $E = {e_{1}, e_{2}, \dots, e_{m}}$ 。一条简单路P是指一个有限非空序列 $P = {v_{1} = v_{s}, e_{i_{1}}, v_{2}, e_{i_{2}}, v_{3}, \dots, e_{i_{k - 1}}, v_{k} = v_{d}}$ ，它的项交替的为节点和超弧，并且节点和超弧都互不相同。其中源点 $v_{s} \in T (e_{i_{1}})$ ，目标节点 $v_{d} \in H (e_{i_{k - 1}})$ ，且 $v_{j} \in H (e_{i_{j - 1}}) \cap T (e_{i_{j}})$ ， $j = 2, \dots, k - 1$ 。

接下来，给出B-路的定义。

定义3 (B-路 [10] ) 给定超图 $H (V, E)$ ，源点和目标节点分别为 $v_{s}$ 和 $v_{d}$ 。B-路 $Π_{v_{s} v_{d}}$ 是一个极小的超图 $H_{Π_{v_{s} v_{d}}} = (V_{Π}, E_{Π})$ 且满足以下条件：

1) $E_{Π} \subseteq E$ ；

2) $v_{s}, v_{d} \in V_{Π}$ ，其中 $V_{Π} = \cup_{e_{i} \in E_{Π}} e_{i}, V_{Π} \in V$ ；

3) 对任一点 $v_{x} \in V_{Π}$ ， $v_{x}$ 与源点 $v_{s}$ 是连通的，也就是说，可以找到从 $v_{s}$ 出发到达 $v_{x}$ 有一条有向无环路。

在有了B-路的定义后，实现了在复杂的超图网络中找一条路。接下来，我们考虑动态超图网络。

2.2. 动态超图网络

定义4 (连续时间动态超图网络) 一个连续时间动态超图网络是一个有向超图 $H = (V (H), E (H), W, T, v_{s}, v_{d})$ ，定义如下：

1) $V (H)$ 为图 $H$ 的节点集， $| V (H) | = n$ 。

2) $E (H)$ 为图 $H$ 的超弧集，对任一条有向超弧 $e = (T (e), H (e))$ ， $T (e)$ 和 $H (e)$ 分别为弧e的尾节点和头节点集合， $T (e) \cap H (e) = ϕ$ 。并且超弧 $e \subseteq V$ ， $| E (H) | = m$ 。

3) T是本文考虑时间范围的上界。

4) $W = {w_{e} (t), e \in E (H)}$ ，其 $w_{e} (t) : [0, T] \mapsto R^{+}$ 表示超弧e的连续延迟函数，t为超弧e的出发时间。对所有的 $t > T$ ， $w_{e} (t) = \infty$ 。

5) $v_{s}, v_{d}$ 分别是源节点和目标节点。另外 $v_{s} (v_{d})$ 不是任意一条超弧的头节点(尾节点)。

假设网络的拓扑结构和弧上的权值函数已确定。设 $F S (v)$ 为尾节点集中包含节点v的超弧， $F S (v) = {e \in E (H) : v \in T (e)}$ ， $B S (v)$ 为头节点集中包含节点v的超弧， $B S (v) = {e \in E (H) : v \in H (e)}$ 。本文中，每一个节点 $v_{i}$ 的到达时间用 $f (i)$ 表示。特别的，由于每条超弧e的尾节点数 $| T (e) | \geq 1$ ，所以规定超弧e的出发时间t等于超弧尾节点 $T (e)$ 的最晚到达时间，故设每条超弧的出发时间t满足 $t = max {f (x) | v_{x} \in T (e)}$ ， $f (x)$ 为节点 $v_{x}$ 的到达时间。

在实际超图网络中，每条超弧 $e \in E (H)$ 对应的延迟函数 $w_{e} (t)$ 是非负递增函数 [10]。对于任意两个节点 $u \in T (e)$ ， $v \in H (e)$ ，从节点u到v存在一条有向超弧e当且仅当 $E (H)$ 中有元素 $e = (T (e), H (e))$ 。

定义5 (节点时间对) 节点时间对 $(v_{x}, f (x))$ 指的是在路径P上，到达节点 $v_{x}$ 的时刻为 $f (x)$ ，其中 $v_{x} \in V (H)$ 。

定义6 (动态B-路) 给定一个连续时间动态超图网络 $H = (V (H), E (H), W, T)$ ，源节点为 $v_{s}$ ，目标节点为 $v_{d}$ 。设 $V_{Π} (t)$ 是动态B-路的节点集， $E_{Π} (t)$ 是动态B-路的有向超弧集，动态B-路是一个极小的动态超图 $H_{Π} (t) = (V_{Π} (t), E_{Π} (t))$ 。一条动态B-路 $H_{Π} (t)$ 指的是当出发时间为t时，从源点 $v_{s}$ 到目标节点 $v_{d}$ 的一条超路，满足：

1) $E_{Π} (t) \subseteq E (H)$ 。

2) ${(v_{s}, t), (v_{d}, f (d))} \in V_{Π} (t)$ ，其中 $V_{Π} (t) = \cup_{e_{i} \in E_{Π} (t)} e_{i}$ ， $V_{Π} (t) \subseteq V (H)$ 。

3) 对 $\forall v_{x} \in V_{Π} (t)$ ，可以找到从源点 $v_{s}$ 到 $v_{x}$ 的一条有向无环路。

4) 经过每条超弧e的出发时间 $t^{'}$ 等于尾节点 $T (e)$ 的最大到达时间， $t^{'} = \max {f (x) | v_{x} \in T (e)}$ ，即经过一条超弧的必要条件是在该超弧所有尾节点都到达的情况下才能出发。

在给出以上定义后，现在我们定义当出发时间为t时，在动态B-路 $H_{Π_{e_{1} e_{m}}} (t)$ 上从节点 $v_{s} \in T (e_{1})$ 到达节点 $v_{d} \in H (e_{m})$ 的旅行时间函数 $w_{Π_{e_{1} e_{m}}} (t)$ ：

$w_{Π_{e_{1} e_{m}}} (t) = w_{Π_{e_{1} e_{m - 1}}} (t) + w_{e_{m}} (t + w_{Π_{e_{1} e_{m - 1}}} ( t ))$

$w_{Π_{e_{1} e_{m}}} (t)$ 的值表示从超弧 $e_{1}$ 到超弧 $e_{m - 1}$ 的旅行时间加上超弧 $e_{m}$ 的延迟。

从上述定义可知，B-路的到达时间为 $f (d)$ 。一条动态限制B-路是指一条动态B-路在时间范围 $[0, T]$ 内可以到达目标节点 $v_{d}$ ，即满足 $f (d) < T$ 。接下来给出在连续时间动态超图网络中限制不交B-路的定义。

定义7 (动态限制k不交B-路) 给定一个连续时间动态超图网络 $H = (V (H), E (H), W, T)$ ，节点 $v_{s}, v_{d} \in V (H)$ 分别为源节点和目标节点，出发时间为t，设 $V_{Π_{i}} (t), E_{Π_{i}} (t)$ 分别为第i条B-路的节点集和超弧集。动态限制k不交B-路是在时间范围 $[0, T]$ 内寻找k条B-路 $H_{Π_{1}} (t), H_{Π_{2}} (t), \dots, H_{Π_{k}} (t)$ ，满足 $\cap_{i = 1}^{k} V_{Π_{i}} (t) = ϕ$ ， $\cap_{i = 1}^{k} E_{Π_{i}} (t) = ϕ$ 。

针对动态B-路的设计，提出的优化问题如下：

问题1 给定一个连续时间动态超图网络 $H = (V (H), E (H), W, T)$ ，源点为 $v_{s}$ ，目标节点为 $v_{d}$ ， $W = {w_{e} (t), e \in E (H)}$ 为超弧的连续时间延迟函数，出发时间为 $t_{s}$ 。在时间范围 $[0, T]$ 内，找一条动态限制B-路 $H_{Π}^{*} (t_{s}) = (V_{Π}^{*} (t_{s}), E_{Π}^{*} (t_{s}))$ 。

问题2 给定一个连续时间动态超图网络 $H = (V (H), E (H), W, T)$ ，源点为 $v_{s}$ ，目标节点为 $v_{d}$ ，出发时间为 $t_{s}$ 。在时间范围 $[0, T]$ 内，找两条动态限制不交B-路 $H_{Π_{1}} (t_{s}) = (V_{Π_{1}} (t_{s}), E_{Π_{1}} (t_{s}))$ ， $H_{Π_{2}} (t_{s}) = (V_{Π_{2}} (t_{s}), E_{Π_{2}} (t_{s}))$ 。

本文中，假设动态超图网络 $H$ 满足FIFO性质，即对任意边e及边e的出发时间 $t, t^{'}$ ，如果 $t < t^{'}$ ，有 $t + w_{e} (t) \leq t^{'} + w_{e} (t^{'})$ 。并且假设动态超图网络 $H$ 中是不存在负圈的。

3. 算法设计

在静态网络中，找不交路最初的方法是先找一条路，然后将这条路经过的节点和弧全部删去，再找另外一条路。但会存在一中情况，就是当删去第一条路之后，会影响到第二条路的构建，而原网络中是存在两条不交路的。这时就出现了“陷阱”问题。针对这种情况，有效的解决办法是在给定一条路的基础上去构造两条不交路 [11]，而不是直接删除该条路。这样，算法可以同时找到两条不交路，而且解决了所谓的“陷阱”问题。在给定连续时间 $[0, T]$ 内，考虑时变的延迟函数，我们结合这种方法在连续动态超图网络中找两条动态限制不交B-路。

3.1. 动态限制B-路算法

在解决找两条动态限制不交B-路问题之前，首先需要在动态超图网络中找到一条动态限制B-路 $H_{Π}^{*} (t_{s}) = (V_{Π}^{*} (t_{s}), E_{Π}^{*} (t_{s}))$ ，其中， $V_{Π}^{*} (t_{s})$ 为B-路的节点集， $E_{Π}^{*} (t_{s})$ 为B-路的超弧集， $t_{s}$ 为出发时间。结合B-树的构造方法 [10]，接下来，我们给出动态限制B-路算法的求解过程。

给定一个动态超图网络 $H = (V (H), E (H), W, T)$ ，集合Q中包含算法每次迭代需要遍历的节点集，集合L中包含已经遍历过的节点集。对于超图中的每条超弧 $e_{j} \in E (H)$ ， $T (e_{j})$ 为超弧 $e_{j}$ 的尾节点集，设 $k_{j}$ 为从集合Q删去的 $T (e_{j})$ 中的节点数，即算法遍历过弧 $e_{j}$ 的尾节点数。

在算法过程中， $t_{s}$ 表示出发时间，节点 $v_{s}, v_{d} \in V (H)$ 分别为源节点和目标节点。 $v_{i}$ 表示每次从集合Q中取的需要遍历的节点，当遍历的尾节点数 $k_{j} = | T (e_{j}) |$ 时，选取尾节点中到达时间最大的t作为超弧 $e_{j}$ 的出发时间， $t = \max {f (x) | v_{x} \in T (e_{j})}$ 。算法第10行中，对于属于 $H (e_{j})$ 的节点 $v_{y}$ 且 $v_{y} \notin L$ ，求得节点 $v_{y}$ 的到达时间 $f (y) = w_{e_{j}} (t) + t$ ，并将节点 $v_{y}$ 放入集合L中，表示该节点已经被遍历过，在下次找超弧头节点时不在查找这个节点，而是继续向后查询。

在满足到达时间 $f (y) < T$ 的情况下，进行算法第13行，标记 $p_{v} (y, f (y)) = e_{j}$ 以记录超路的信息。之后，判断该节点是否被遍历过(第17行)，如果没有，放到集合Q中以便下一次迭代。直到查找到目标节点 $v_{d}$ 时跳出循环(第14行)，求出一条动态限制B-路 $H_{Π}^{*} (t_{s})$ 。

定理1 算法1的复杂度为 $O (n \cdot s i z e (H))$ 。

证明：算法1第5行，在Q集合中节点的个数最多有n个，第6行对于节点 $v_{i}$ 出去的弧 $e_{j}$ ，需要花费 $O (| T (e_{j}) |)$ 的运算时间，算法第10行中探寻弧e的头节点需要花费 $O (| H (e_{j}) |)$ 的运算时间，故算法1的复杂度为 $O (n \cdot s i z e (H))$ 。

当算法1结束后，得出一条动态限制B-路 $H_{Π}^{*} (t_{s})$ 。接下来通过这条已知的B-路来找两条动态限制不交B-路。

3.2. 动态限制不交B-路算法

本节的目标是在动态超图网络 $H = (V (H), E (H), W, T)$ 中找两条动态限制不交的B-路。为了避免陷阱问题，本文的算法思想是在已知一条限制B-路 $H_{Π}^{*} (t_{s})$ 的基础上构造两条动态限制不交B-路 $H_{Π_{1}} (t_{s}) = (V_{Π_{1}} (t_{s}), E_{Π_{1}} (t_{s}))$ ， $H_{Π_{2}} (t_{s}) = (V_{Π_{2}} (t_{s}), E_{Π_{2}} (t_{s}))$ 。

3.2.1. 准备工作

本问题面临的主要挑战是在动态超图中，算法找到的两条路 $H_{Π_{1}} (t_{s})$ ， $H_{Π_{2}} (t_{s})$ 需要满足经过的节点时间对是动态不交的，且两条路所有超弧的经过时间段是不交的。对于一条超弧 $e = (T (e), H (e))$ ，设 $f (T (e))$ 和 $f (H (e))$ 分别为超弧e头节点和尾节点的到达时间，即：

1) 对任意的节点时间对 $(v_{i}, f (i)) \in V_{Π_{1}} (t_{s})$ ， $(v_{j}, f (j)) \in V_{Π_{2}} (t_{s})$ ，有 $(v_{i}, f (i)) \neq (v_{j}, f (j))$ 。

2) 对任意的超弧 $e_{i} \in E_{Π_{1}} (t_{s})$ ， $e_{j} \in E_{Π_{2}} (t_{s})$ ，超弧 $e_{i}$ 经过的时间区间表示为 $I_{1} = [f (T (e_{i})), f (H (e_{i}))]$ ， $e_{j}$ 经过的时间区间表示为 $I_{2} = [f (T (e_{j})), f (H (e_{j}))]$ ，有 $I_{1} \cap I_{2} = ϕ$ 。

故为保证以上两个条件，在找路的过程中需要避开已知路 $H_{Π}^{*} (t_{s})$ 中超弧经过的时间段，我们更新动态超图网络 $H$ 中超弧e的延迟函数 $W^{'} = {{w^{'}}_{e} (t), e \in E (H)}$ 。

首先对已知动态限制B-路 $H_{Π}^{*} (t_{s})$ 上所有超弧的延迟函数进行更新。对所有的 $e \in E_{Π}^{*} (t_{s})$ ，假设弧e的尾节点集 $T (e)$ 中到达时间 $f (T (e))$ 最小的记为a，即 $a = \min {f (T (e)) | e \in E_{Π}^{*} (t_{s})}$ 。头节点集 $H (e)$ 中到达时间 $f (H (e))$ 最大的记为 $t^{″}$ ，即 $t^{″} = \max {f (H (e)) | e \in E_{Π}^{*} (t_{s})}$ 。故有：

$t^{'} = \arg \min_{t \in [0, T]} {a \leq t + w_{e} (t) \leq t^{″}}$

所以，在找两条路的过程中，对于每条在路 $H_{Π}^{*} (t_{s})$ 上的超弧，更新在时间段 $[t^{'}, t^{″})$ 的延迟函数。

${w^{'}}_{e} (t) = {\begin{array}{l} \infty, & t \in [t^{'}, t^{″}) \\ w_{e} (t), & otherwise . \end{array}$

对于动态超图网络 $H$ 中除 $H_{Π}^{*} (t_{s})$ 之外的其他超弧，他们的延迟函数保持不变。即： ${w^{'}}_{e} (t) = w_{e} (t)$ ， $e \in (E (H) - E_{Π}^{*} (t_{s}))$ 。

这样，当我们在找两条不交路时，能避开 $H_{Π}^{*} (t_{s})$ 超弧走过的相应时间段，使找到的超弧满足动态边不交的条件。接下来给出实例说明。

例1 假设弧e为动态限制B-路 $H_{Π}^{*} (t_{s})$ 的一条超弧，弧e的尾节点集 ${(v_{1}, 2), (v_{2}, 2.5)}$ ，头节点集 ${(v_{3}, 3.5)}$ ，延迟函数 $w_{e} (t)$ 见图1。根据以上步骤更新弧e的延迟函数 $w_{e} (t)$ 为 ${w^{'}}_{e} (t)$ ，见图2。

$w_{e} (t) = {\begin{array}{l} 1, & t \in [0, 3) \\ t - 2, & t \in [3, T] . \end{array}$

Figure 1. $w_{e} ( t )$

图1. $w_{e} ( t )$

接下来我们求延迟函数 $w_{e} (t)$ 要更新的区间 $[t^{'}, t^{″})$ 。

$a = \min {f (1), f (2)} = 2.$

$t^{″} = \max {f (3)} = 3.5.$

$t^{'} = \arg \min_{t \in [0, T]} {2 \leq t + w_{e} (t) \leq 3 .5} = 1 .$

${w^{'}}_{e} (t) = {\begin{array}{l} 1, & t \in [0, 1); \\ \infty, & t \in [1, 3.5); \\ t - 2, & t \in [3.5, T] . \end{array}$

Figure 2. ${w^{'}}_{e} ( t )$

图2. ${w^{'}}_{e} ( t )$

3.2.2. 算法设计与实现

在给出动态超图网络中求两条不交路的算法之前，我们先通过示例给出静态网络中基于一条路去找两条不交路的过程，并说明交错点的定义。

例2 如图3所示，给定图 $H (V, E)$ ， $V = {v_{1}, v_{2}, v_{3}, v_{4}}$ ， $E = {e_{1}, e_{2}, e_{3}, e_{4}, e_{5}}$ 。假设静态网络中每条弧e都有一个权值w。节点 $v_{1}$ 和 $v_{4}$ 是源节点和目标节点。给出一条已知超路 $H_{Π}^{*} = ({v_{1}, v_{2}, v_{3}, v_{4}}, {e_{1}, e_{2}, e_{5}})$ ，其中，超路节点集为 $V_{Π}^{*} = {v_{1}, v_{2}, v_{3}, v_{4}}$ ，弧集 $E_{Π}^{*} = {e_{1}, e_{2}, e_{5}}$ 。那么我们可以根据以下步骤获得两条不交路 $H_{Π_{1}}, H_{Π_{2}}$ 。

Figure 3. Hypergraph $H (V, E)$

图3. 超图 $H (V, E)$

首先，我们可以从源节点 $v_{1}$ 出发找到除 $H_{Π}^{*}$ 之外的边 $e_{3} = (v_{1}, v_{3})$ ，由于节点 $v_{3} \in V_{Π}^{*}$ ，记 $v_{3}$ 为交错点。因此，为构造两条不交路，需要反向找节点 $v_{1}$ 和 $v_{3}$ 之间的节点 $v_{2}$ 。从 $v_{2}$ 继续向后探查除 $H_{Π}^{*}$ 之外的边 $e_{4} = (v_{2}, v_{4})$ 。这样，就找到两条不交的路 $H_{Π_{1}} = ({v_{1}, v_{3}, v_{4}}, {e_{3}, e_{5}})$ ， $H_{Π_{2}} = ({v_{1}, v_{2}, v_{4}}, {e_{1}, e_{4}})$ 。

每次探查完交错点之后，我们将该交错点标记为c用于后续路径连接。交错点的个数记为m。

接下来我们在动态超图网络 $H = (V (H), E (H), W, T)$ 中构造不交路。

算法步骤如下：

1) 初始化。源点 $v_{s}$ 的出发时间为 $t_{s}$ ，将源点出发经过的不属于 $V_{Π}^{*} (t_{s})$ 的第一条超弧的头节点 $(v_{i}, f (i))$ 放到候选点集Q中，初始化 $f (i) = t_{s} + w_{s i} (t_{s})$ ， $w_{s i} (t_{s})$ 为弧 $e = (v_{s}, v_{i})$ 的延迟函数。集合L表示算法已经考虑过的节点集，初始化 $L = {v_{s}}$ 。参数m记录交错点的个数， $m = 0$ 。c标记交错点。

2) 求已知路 $H_{Π}^{*} (t_{s})$ 。通过算法1，在动态超图网络 $H = (V (H), E (H), W, T)$ 中求得一条动态限制B-路 $H_{Π}^{*} (t_{s}) = (V_{Π}^{*} (t_{s}), E_{Π}^{*} (t_{s}))$ ， $V_{Π}^{*} (t_{s})$ 和 $E_{Π}^{*} (t_{s})$ 分别为路 $H_{Π}^{*} (t_{s})$ 经过的节点时间对集和超弧集。

3) 运行算法2。首先，当Q不为空时，选择其中的候选点 $(v_{i}, f (i))$ ，然后开始找点 $v_{i}$ 出去的超弧 $e_{j} \in F S (v_{i})$ ，结合B-弧的查找方法 [10]，当遍历完超弧的所有尾节点后(算法第9~10行)，选择到达时间最大的尾节点，并将其到达时间作为超弧 $e_{j}$ 的出发时间，接着当超弧的头节点 $v_{y} \notin L$ 时，求其到达时间 $f (y)$ 。判断 $f (y)$ ，当 $f (y) < T$ 时，说明弧 $e_{j}$ 与 $H_{Π}^{*} (t_{s})$ 的弧是动态不交的，记录路信息并将头节点 $v_{y}$ 放入集合L中，进行算法3判断交错点。否则，算法判断Q是否为空，如果不为空，说明可以继续重新探查下一个节点，返回算法第4步，如果为空，则说明超图中没有满足条件的路径。

4) 运行算法3。当参数m为偶数时，遍历的节点 $(v_{y}, f (y))$ 属于路 $H_{Π_{1}} (t_{s})$ ，m为奇数时，节点 $(v_{y}, f (y))$ 属于路 $H_{Π_{2}} (t_{s})$ 。由于遍历的节点 $(v_{y}, f (y))$ 有两种情况，一种是属于 $V_{Π}^{*} (t_{s})$ ，一种是不属于 $V_{Π}^{*} (t_{s})$ ，需要分类讨论。

a) 当节点 $(v_{y}, f (y))$ 不属于 $V_{Π}^{*} (t_{s})$ 时，将节点放入Q中，然后返回算法2继续查询下一条超弧。

b) 当节点 $(v_{y}, f (y))$ 属于 $V_{Π}^{*} (t_{s})$ 时(算法3第9行)，节点 $(v_{y}, f (y))$ 是一个交错点。设 $V_{Π}^{*} (t_{s}) : c \to (v_{y}, f (y))$ 为 $H_{Π}^{*} (t_{s})$ 路上除c点和 $(v_{y}, f (y))$ 之外的它们之间经过的节点对。从点 $(v_{y}, f (y))$ 沿 $H_{Π}^{*} (t_{s})$ 路反向找 $V_{Π}^{*} (t_{s}) : c \to (v_{y}, f (y))$ 的节点时间对 ${(v_{i}, f (i)) | v_{i} \neq v_{s} \neq v_{y}}$ ，然后需要从节点 $(v_{i}, f (i))$ 继续往后查询，所以令集合 $Q = ϕ$ ，然后将 ${(v_{i}, f (i))}$ 放入集合Q中，并且放入集合L中，避免找路时头节点重复探查，即算法第11~12行。

接下来，当参数m为偶数时，将交错点之间的 $V_{Π}^{*} (t_{s})$ 加入到路径 $H_{Π_{2}} (t_{s})$ 中的节点集 $V_{Π_{2}} (t_{s})$ ，即将 $H_{Π}^{*} (t_{s})$ 路上 $c \to (v_{y}, f (y))$ 之间的路归于 $H_{Π_{2}} (t_{s})$ ， $V_{Π_{2}} (t_{s}) = V_{Π_{2}} (t_{s}) \cup (V_{Π}^{*} (t_{s}) : c \to (v_{y}, f (y)))$ ，m为奇数时，将交错点之间的 $V_{Π}^{*} (t_{s})$ 加入到路径 $H_{Π_{1}} (t_{s})$ 中，即将 $H_{Π}^{*} (t_{s})$ 路上 $c \to (v_{y}, f (y))$ 之间的路归于 $H_{Π_{1}} (t_{s})$ ， $V_{Π_{1}} (t_{s}) = V_{Π_{1}} (t_{s}) \cup (V_{Π}^{*} (t_{s}) : c \to (v_{y}, f (y)))$ 。最后由于节点 $(v_{y}, f (y))$ 是一个交错点，标记 $(v_{y}, f (y))$ 为c，用于之后查找不交路的连接，并更新参数m。接着返回算法2继续向后查询超路。

在算法过程中，当探查的节点为已知路 $H_{Π}^{*} (t_{s})$ 的节点时间对时，我们需要沿着 $H_{Π}^{*} (t_{s})$ 反向寻找交错点之间的节点，然后根据寻找的节点再出发寻求下一条不属于 $H_{Π}^{*} (t_{s})$ 的超弧。算法的具体思路是在探查节点的过程中记录交错点数m，然后根据参数m的奇偶性对交错进行分类，分别对应 $H_{Π_{1}} (t_{s})$ ， $H_{Π_{2}} (t_{s})$ 。

当算法2查询到的节点是目标节点 $v_{d}$ 时，算法结束。根据算法过程得到两条动态限制不交B-路 $H_{Π_{1}} (t_{s})$ ， $H_{Π_{2}} (t_{s})$ 。否则，算法找不到两条动态限制不交的B-路，输出无结果。接下来我们通过一个例子来更直观的理解算法。

例3 假设动态超图网络 $H = (V (H), E (H), W, T)$ 。每条弧都有一个延迟函数 $w_{e} (t)$ 。节点 $v_{s}$ 和 $v_{d}$ 是源点和目标节点，出发时间 $t_{s} = 0$ ， $L = {v_{s}}$ ，时间范围 $T = [0, 50]$ 。假设通过算法1求得一条动态限制B-路 $H_{Π}^{*} (t_{s}) = ({(v_{s}, 0), (v_{1}, 2), (v_{2}, 1), (v_{3}, 4), (v_{5}, 5), (v_{6}, 5), (v_{d}, 7)}, {e_{1}, e_{2}, e_{3}, e_{5}, e_{8}})$ 。接下来我们可以根据以下步骤获得两条动态限制不交B-路 $H_{Π_{1}} (t_{s})$ ， $H_{Π_{2}} (t_{s})$ 。见图4。

Figure 4. Dynamic hypergraph network $H$

图4. 动态超图网络 $H$

算法过程：根据算法2，初始状态 $Q = {(v_{4}, f (4)) | (v_{s}, v_{4}) \in E (H), (v_{4}, f (4)) \notin V_{Π}^{*} (t_{s})}$ ，其中 $f (4) = t_{s} + w_{s 4} (t_{s}) = 3$ ，路 $H_{Π_{1}} (t_{s})$ 的节点集 $V_{Π_{1}} (t_{s}) = {(v_{s}, 0), (v_{4}, 3)}$ ，路 $H_{Π_{2}} (t_{s})$ 的节点集 $V_{Π_{2}} (t_{s}) = {(v_{s}, 0)}$ ，标记源点 $(v_{s}, 0)$ 为c，交错数 $m = 0$ 。

算法2第4步，候选点集 $Q \neq ϕ$ ，在集合Q中选择 $(v_{4}, f (4))$ ，并删除 $(v_{4}, f (4))$ 。选择 $e_{7} \in F S (v_{4})$ ， $k_{7} = k_{7} + 1 = 1$ ，满足 $k_{7} = | T (e_{7}) |$ ，故弧 $e_{7}$ 的出发时间 $t = \max {f (x) | v_{x} \in T (e_{7})} = 3$ 。算法2第11行中， $v_{5} \in H (e_{7})$ 并且 $v_{5} \notin L$ ，所以 $f (5) = w_{e_{7}} (3) + 3 = 5$ ， $f (5) < 50$ ， $p_{v} (v_{5}, 5) = e_{7}$ ， $L = L \cup {v_{5}}$ ，进行算法3。

由于此时 $m = 0$ 为偶数，故将 $(v_{5}, 5)$ 放入 $H_{Π_{1}} (t_{s})$ 中。因为 $(v_{5}, 5) \in V_{Π}^{*} (t_{s})$ ，故进行算法3第9步。从点 $(v_{5}, 5)$ 沿 $H_{Π}^{*} (t_{s})$ 路反向找 $V_{Π}^{*} (t_{s}) : (v_{s}, 0) \to (v_{5}, 5)$ 的节点时间对 ${(v_{i}, f (i)) | v_{i} \neq v_{s} \neq v_{5}}$ ，由图4可知，节点时间对 $(v_{1}, 2), (v_{2}, 1), (v_{3}, 4)$ 满足情况， $Q = {(v_{1}, 2), (v_{2}, 1), (v_{3}, 4)}$ ， $L = L \cup {v_{1}, v_{2}, v_{3}}$ 。将 $V_{Π}^{*} (t_{s}) : (v_{s}, 0) \to (v_{5}, 5)$ 之间的节点 $(v_{1}, 2), (v_{2}, 1), (v_{3}, 4)$ 放入路 $H_{Π_{2}} (t_{s})$ 的节点集中， $V_{Π_{2}} (t_{s})$ 标记 $(v_{5}, 5)$ 为c，令 $m = 1$ 。

返回算法2继续查找下一个Q中的节点。最后，我们找到了两条限制不交的B-路 $H_{Π_{1}} (t_{s})$ ， $H_{Π_{2}} (t_{s})$ ，其节点集为 $V_{Π_{1}} (t_{s}) = {(v_{s}, 0), (v_{4}, 3), (v_{5}, 5), (v_{d}, 7)}$ ， $V_{Π_{2}} (t_{s}) = {(v_{s}, 0), (v_{1}, 2), (v_{2}, 1), (v_{3}, 4), (v_{d}, 7)}$ 。超弧集为 $E_{Π_{1}} (t_{s}) = {e_{6}, e_{7}, e_{8}}$ ， $E_{Π_{2}} (t_{s}) = {e_{1}, e_{2}, e_{3}, e_{4}}$ 。

3.2.3. 算法正确性和复杂性证明

这一节，我们给出定理2说明算法的正确性，并证明算法复杂性。

定理2 算法2输出两条动态限制不交B-路 $H_{Π_{1}} (t_{s})$ ， $H_{Π_{2}} (t_{s})$ 当且仅当超图 $H$ 中存在问题2的解。

证明：算法的目的是为了找两条动态限制不交B-路。当算法2输出 $H_{Π_{1}} (t_{s})$ ， $H_{Π_{2}} (t_{s})$ ，说明超图 $H$ 在时间范围 $[0, T]$ 内可以找到两条动态限制不交B-路。首先，在3.2.1部分的准备工作中，我们更新路 $H_{Π}^{*} (t_{s})$ 上所有超弧 $e_{j}$ 的延迟函数 $w_{e} (t)$ ，对路 $H_{Π}^{*} (t_{s})$ 上超弧经过的所有时间段的函数值赋值为 $\infty$ 。这一操作是为了在找路的过程中，避开路 $H_{Π}^{*} (t_{s})$ 上所有弧的经过时间段，保证了两条路是动态边不交的。并且在算法2第14行，节点的到达时间满足条件 $f (y) < T$ 。对于节点时间对相交，算法提出交错的概念，在探查节点的过程中记录交错点数m，然后根据参数m的奇偶性对探查的超弧进行分类，分别对应 $H_{Π_{1}} (t_{s})$ ， $H_{Π_{2}} (t_{s})$ 。对于每一个探查过的节点，都将其放入集合L中，保证了所找的路不存在圈。故算法所找出来的是两条动态限制不交的B-路。

另外，由于在调用算法3时，算法10~12行考虑了交错点之间所有以 $H_{Π}^{*} (t_{s})$ 上的点为尾节点出去的超弧，即算法遍历了所有满足条件的超弧。所以，当算法2输出不存在时，说明超图 $H$ 在时间范围 $[0, T]$ 内没有满足条件的动态限制不交B-路。否则，如果存在，在运行算法3的第10~12行更新集合Q后，算法2进行第4~16行时一定会找到满足条件的路径。

定理3 算法2的复杂度为 $O (n \cdot α (T) s i z e (H))$ 。

证明：候选点集Q中的元素最多有 $n \cdot α (T)$ 个节点时间对，对于每一个探查过的节点，都将其放入集合L中，所以对于超弧头节点和尾节点的探查总共需要 $s i z e (H)$ 的时间。算法3需要 $O (1)$ 的运行时间。故算法2的复杂度为 $O (n \cdot α (T) s i z e (H))$ 。

3.2.4. 算法的推广

本文考虑的是连续时间动态超图网络中的动态限制不交B-路，相应的我们可以获得动态不交F-路。由于F-弧满足的条件是 $| T (e) | = 1$ ，所以我们在计算路的延迟时，考虑每条超弧的尾节点的到达时间为超弧的出发时间，显然到达头节点的时间都是相等的，并且在探查到交错点时，同样沿 $H_{Π}^{*} (t_{s})$ 路反向找到超弧对应的尾节点，然后从尾节点继续向后探查。可以看出，求动态限制不交F-路的算法与求动态限制不交B-路的算法类似，在这里，我们就不再给出算法。

4. 结语

结合现实中的实际问题，本文提出了一个新的网络环境，连续时间动态超图网络。动态超图网络与传统的网络模型相比应用范围更广，也更有实际意义。本文在连续时间动态超图网络中，通过对超图特殊性的分析，设计了求解动态限制不交B-路问题的算法，证明算法是在多项式时间 $O (n \cdot α (T) s i z e (H))$ 内可解决的。在动态超图网络中还可以进一步研究在其他领域的应用，求解不同方面的问题。

基金项目

山西省自然科学基金(202103021224058)。

参考文献

[1]	Marcotte, P. and Nguyen, S. (1998) Hyperpath Formulations of Traffic Assignment Problems. In: Marcotte, P. and Nguyen, S., Eds., Equilibrium and Advanced Transportation Modelling, Springer, Boston, 175-200. https://doi.org/10.1007/978-1-4615-5757-9_9
[2]	Nguyen, S., Pallottino, S. and Gendreau, M. (1998) Implicit Enumeration of Hyperpaths in a Logit Model for Transit Networks. Transportation Science, 32, 54-64. https://doi.org/10.1287/trsc.32.1.54
[3]	Pretolani, D. (2000) A Directed Hypergraph Model for Random Time Dependent Shortest Paths. European Journal of Operational Research, 123, 315-324. https://doi.org/10.1016/S0377-2217(99)00259-3
[4]	Boley, H. (1977) Directed Recursive Labelnode Hypergraphs: A New Representation-Language. Artificial Intelligence, 9, 49-85. https://doi.org/10.1016/0004-3702(77)90014-5
[5]	Torres, A. and Araoz, J. (1988) Combinatorial Models for Searching in Knowledge Bases. Acta Científica Venezolana, 39, 387-394.
[6]	Ausiello, G., D’Atri, A. and Saccà, D. (1983) Graph Algorithms for Functional Dependency Manipulation. Journal of the ACM (JACM), 30, 752-766. https://doi.org/10.1145/2157.322404
[7]	Carraresi, P., Gallo, G. and Rago, G. (1993) A Hypergraph Model for Constraint Logic Programming and Applications to Bus Drivers’ Scheduling. Annals of Mathematics and Artificial Intelligence, 8, 247-270. https://doi.org/10.1007/BF01530792
[8]	Gallo, G. and Scutella, M.G. (1998) Directed Hypergraphs as a Modelling Paradigm. Rivista di Matematica per le Scienze Economiche e Sociali, 21, 97-123. https://doi.org/10.1007/BF02735318
[9]	Italiano, G.F. and Nanni, U. (1989) Online Maintenance of Minimal Directed Hypergraphs. 3rd Italian Conference on Theoretical Computer Science, Mantova, 2-4 November 1989, 335-349.
[10]	Gallo, G., Longo, G., Palottino, S. and Nguyen, S. (1993) Directed Hypergraphs and Applications. Discrete Applied Mathematics, 42, 177-201. https://doi.org/10.1016/0166-218X(93)90045-P
[11]	Suurballe, J.W. (1974) Disjoint Paths in a Network. Networks, 4, 125-145. https://doi.org/10.1002/net.3230040204
[12]	Suurballe, J.W. and Tarjan, R.E. (1984) A Quick Method for Finding Shortest Pairs of Disjoint Paths. Networks, 14, 325-336. https://doi.org/10.1002/net.3230140209
[13]	Yang, B., Zheng, S.Q. and Katukam, S. (2003) Finding Two Disjoint Paths in a Network with Min-Min Objective Function. Parallel and Distributed Computing and Systems Vol.1, Department of Computer Science, University of Texas at Dallas, Richardson.
[14]	Fleischer, R., Ge, Q., Li, J. and Zhu, H. (2007) Efficient Algorithms for k-Disjoint Paths Problems on DAGs. International Conference on Algorithmic Applications in Management, Portland, 6-8 June 2007, 134-143. https://doi.org/10.1007/978-3-540-72870-2_13
[15]	Fortune, S., Hopcroft, J. and Wyllie, J. (1980) The Directed Subgraph Homeomorphism Problem. Theoretical Computer Science, 10, 111-121. https://doi.org/10.1016/0304-3975(80)90009-2
[16]	Parpalea, M. and Ciurea, E. (2011) The Quickest Maximum Dynamic Flow of Minimum Cost. International Journal of Applied Mathematics and Informatics, 5, 266-274.
[17]	Cai, X., Sha, D. and Wong, C.K. (2001) Time-Varying Minimum Cost Flow Problems. European Journal of Operational Research, 131, 352-374. https://doi.org/10.1016/S0377-2217(00)00059-X
[18]	Ding, B., Yu, J.X. and Qin, L. (2008) Finding Time-Dependent Shortest Paths over Large Graphs. Proceedings of the 11th International Conference on Extending Database Technology: Advances in Database Technology, Nantes, 25-29 March 2008, 205-216. https://doi.org/10.1145/1353343.1353371
[19]	Wang, Y., Li, G. and Tang, N. (2019) Querying Shortest Paths on Time Dependent Road Networks. Proceedings of the VLDB Endowment, 12, 1249-1261. https://doi.org/10.14778/3342263.3342265.

为你推荐

友情链接