最短路径算法

Abstract

This article ism't finished yet...

顶点标号法¶

Dantzig 算法，1959 年，旦捷希(Dantzig)发现了在赋权图中求由点 a 到点 b 的最短路好算法，称为顶点标号法。

和弗洛伊德算法非常非常像... ，在这里补充一下 Floyid 算法对邻接矩阵求最短距离矩阵过程，这个过程和 Dantzig 几乎一致（完全一致好吧，考试可能会考？）：

按顺序一列一列看，看第 $i$ 列时：
按顺序一行一行看，看第 $j$ 行时，若 $a_{j i} \neq \infty$ 则：
- 看第 $j$ 列，看 $a_{j i} + a_{k j}$ 是否是新的 $i$ 到 $k$ 的最短距离

数据结构¶

$t (a_{n})$ :点 $a_{n}$ 的标号值, 表示点 $a_{1} = a$ 到 $a_{n}$ 的最短路长度
$A_{i} = {a_{1}, a_{2}, \dots, a_{i}}$ : 已经标号的顶点集合
$T_{i}$ : $a$ 到 $a_{i}$ 的最短路上的边集合

算法步骤¶

记：
$a = a_{1}$ ,
$t (a_{1}) = 0$ ,
$A_{1} = {a_{1}}$ ,
$T = \emptyset$ ;
若已经得到 $A_{i} = {a, a_{2}, \dots, a_{i}}$ , 且对于 $1 \leq n \leq i$ , 已知 $t (a_{n})$ 对每一个 $a_{n} \in A_{i}$ , 求一点:

$$ b_n^{(i)}\in N(a_n)-A_i=B_n^{(i)} $$

使得:

$$ l(a_n b_n^{(i)})=\min_{v\in B_n^{(i)}}l(a_n v) $$

!!! abstract 这里 $i$ 表示第 $i$ 轮， $N (a_{n})$ 表示与 $a_{n}$ 邻接的点组成的集合，N 表示 Neighbour

:::

设有 $j$ , $1 \leq j \leq i$ , 而 $b_{j}^{(i)}$ 是使 $t (a_{j}) + l (a_{j} b_{j}^{(i)})$ 取最小值 , 令:
$a_{i + 1} = b_{j}^{(i)}$ ；
$t (a_{i + 1}) = t (a_{j}) + l (a_{j} a_{i + 1})$ ；
$T_{i + 1} = T_{i} \cup {a_{j} a_{i + 1}}$ ；
- 若 $a_{i + 1} = b$ , 停止 ;
否则，记 $A_{i + 1} = A_{i} \cup {a_{i + 1}}$ ，转(2)

时间复杂度¶

对第 $i$ 次循环:

步骤 (2) 要进行 $i$ 次比较运算
步骤 (3) 要进行 $i$ 次加法与 $i$ 次比较运算

所以，该次循环运算量为 $3 i$ 。

所以，在最坏的情况下，运算量为 $n^{2}$ 级，是好算法

完备性证明¶

定理 1：算法中的函数 $t (a_{n})$ 给出了 $a$ 与 $a_{i}$ 的距离证明：对 $i$ 作数学归纳法

$i = 1$ 时结论显然成立；
设对所有的 $j$ ， $1 \leq j \leq i$ 时， $t (a_{j}) = d (a, a_{j})$ ；
考虑 $j = i + 1$ ：

$顶点标记法完备性证明$

于是 $d = d (a, a_{i + 1})$

又令 $v_{n}$ 是 P 中第一个不在 $A_{i}$ 中的点。由于 $a_{i + 1} \notin A_{i}$ , 所以这样的点存在

因为 $v_{0} \in A_{i}$ ，所以 $n \geq 1$ ；

记 P 中 $a$ 到 $v_{n + 1}$ 一段长为 $l$ , 而 $a$ 到 $v_{n}$ 的一段长为 $l_{1}$ ；

由归纳假设有: $l_{1} \geq t (v_{n})$ ，进而有：

d = d (a, a_{i + 1}) \geq l = l_{1} + l (v_{n} v_{n + 1}) \geq t (v_{n}) + l (v_{n} v_{n + 1})

算法中，当第 $i$ 轮中已知 $A_{i} = {a_{1}, a_{2}, \dots, a_{i}}$ 要给 $a_{i + 1}$ 标号时，其中要选择 $b_{n}^{(i)}$ ，满足：

l (v_{n} b_{n}^{(i)}) \leq l (v_{n} v_{n + 1})

だから：

d \geq t (v_{n}) + l (v_{n} v_{n + 1}) \geq t (v_{n}) + l (v_{n} b_{n}^{(i)})

又由算法最终对点 $a_{i}$ 的标号值的选择方法知；

d \geq t (v_{n}) + l (v_{n} b_{n}^{(i)}) \geq t (a_{j}) + l (a_{j} a_{i + 1}) \geq t (a_{i + 1})

另一方面，由算法可知存在一条长度为 $t (a_{i})$ 的联结 $a$ 与 $a_{i}$ 的路，所以：

t (a_{i + 1}) \geq d (a, a_{i + 1})

从而得到 $t (a_{i + 1}) \geq d (a, a_{i + 1}) \geq t (a_{i + 1})$ ，即得到： $t (a_{i + 1}) = d (a, a_{i + 1})$

应用举例¶

分酒¶

某两人有一只 8 升的酒壶装满了酒，还有两只空酒壶，分别为 5 升和 3 升，求最少的操作次数能均分酒

解:设 $x_{1}, x_{2}, x_{3}$ 分别表示 8,5,3 升酒壶中的酒量。则

x_{1} + x_{2} + x_{3} = 8, x_{1} \leq 8, x_{2} \leq 5, x_{3} \leq 3

容易算出 $(x_{1}, x_{2}, x_{3})$ 的组合形式共 24 种

每种组合用一个点表示，两点连线，当且仅当可通过倒酒的方式相互变换。若各边赋权为 1，则问题转化为在该图中求 $(8, 0, 0)$ 到 $(4, 4, 0)$ 的一条最短路。结果如下:

(8, 0, 0) \to (3, 5, 0) \to (3, 2, 3) \to (6, 2, 0) \to (6, 0, 2) \to (1, 5, 2) \to (1, 4, 3) \to (4, 4, 0)

Abstract

这个问题给定了初始状态和目标状态，也可以转化为人工智能中的智能规划问题

狼羊过河¶

在一河岸有狼，羊和卷心菜。摆渡人要将它们渡过河去，由于船太小，每次只能载一样东西。由于狼羊，羊卷心菜不能单独相处。问摆渡人至少要多少次才能将其渡过河?

人，狼，羊，菜所有组合形式为:

C_{4}^{0} + C_{4}^{1} + C_{4}^{2} + C_{4}^{3} + C_{4}^{4} = 2^{4} = 16

但是以下组合不能允许出现: 狼羊菜，羊菜，狼羊，人，人狼，人菜，共 6 种；

岸上只能允许出现 10 种组合: 人狼羊菜，人狼羊，人狼菜，人羊，空，菜，羊，狼，狼菜，人羊菜；

每种情况用点表示，两点连线，当且仅当两种情况可用载人(或加一物) 的渡船相互转变，每条边赋权为 1 。于是，问题转化为求由顶点 “人狼羊菜” 到顶点 “空” 的一条最短路问题。结果为:

人狼羊菜 \to 狼菜 \to 人狼菜 \to 狼 \to 人狼羊 \to 羊 \to 人羊 \to 空