总述

• 寻找（明确地、隐含地）寻找一个组合对象

  • 排列
  • 组合（整数规划）
  • 子集

• 这些对象能满足特定条件并具有想要的属性

  • 价值最大化
  • 成本最小化

特点

无论从理论角度、实践角度而言，组合问题是计算领域最难的问题

• 随着问题规模增大，组合对象数量增长极快

• 没有一种已知算法，能在可接受的时间范围内，精确的解决 大部分组合问题，且被普遍认为不存在（未被证实）

• 有些组合问题有高效求解算法，是幸运的例外

从更抽象的角度看，旅行商问题、图填色问题也是组合问题的特例

思路

• exhaustive search：（穷举搜索）是简单的蛮力方法

  • 生成问题域每个元素
  • 选出满足问题约束的元素
  • 最后寻找期望元素

• 因为可能性太多，基本可能从动态规划方向着手

背包问题

给定n个重量为$w_1, w_2, \cdots, w_n$价值为$v_1, v_2, …, vn$ 的物品和承重为$W$的背包，求能够装进背包的最有价值物品子集

蛮力算法

算法

• 考虑所有n个物品的子集
• 计算每个子集重量，找出可行子集
• 找到可行子集中价值最大子集

经典自底向上动态规划

依次求解所有子问题、记录

算法

设$F(i, j)$为由前i个物品、承重量为j的背包得到最优解

• 不包括第i个物品的子集中，最优子集价值为$F(i-1, j)$

• 包括第i个物品的子集中，最优子集是由该物品和前i-1个物品 中能够放进承重量为$j-w_i$的背包的最优子集组成，总价值为 $v_i + F(i-1, j-w_i)$

则递推式为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Knapsack(Ws[1..n], Vs[1..n], W)
	// 动态规划求解背包问题
	// 输入：Ws[1..n]物品重量、Vs[1..n]物品价值，W背包承重
	// 输出：背包能够装载的最大价值
	for i = 0 to n do
		F[i, 0] = 0
	for j = 0 to W do
		F[0, j] = 0
		for i = 1 to n do
			if j >= Ws[i]:
				F[i, j] = max(F[i-1, j], Vs[i] + F[i-1, j-Ws[i])
				// 这里用于比较的F值，在之前的循环中已经确定
			else
				F[i, j] = F[i-1, j]
	return F[n, W]

算法特点

• 算法效率
  • 时间效率$\in \Theta(nW)$
  • 空间效率$\in \Theta(nW)$
  • 回溯求最优解组成效率$\in O(n)$

自顶向下动态规划

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

MFKnapsack(i, j)
	// 背包问题的记忆功能方法
	// 输入：i考虑的物品数量，j背包承重
	// 输出：前i个物品的最优可行子集
	// Ws[1..n]、Vs[1..n]、F[0..n, 0..W]作为全局变量
	for i = 0 to n do
		F[i, 0] = 0
	for j = 0 to W do
		F[0, j] = 0
	if F[i, j] < 0
		if j < Ws[i]
			value = MFKnapsack(i-1, j)
		else
			value = max(MFKnapsack(i-1, j),
				Vs[i] + MFKnapsack(i-1, j - Ws[i]))
		F[i, j] = value
	return F[i, j]

算法特点

• 算法效率
  • 相较于经典自底向上算法，时间效率提升常数因子，但是 效率仍然$\in \Theta(nW)$
  • 相较于自底向上算法空间优化版版本而言，空间效率较低

分支界限法

• 不失一般性认为，物品按照价值重量比$v_i / w_i$降序排列， 可以简化问题

• 第i层节点上界可取$ub = v + (W - w)(v{i+1} / w{i+1})$

  • $v$：已选物品价值
  • $W - w$：背包剩余承重量
  • $v{i+1}/w{i+1}$：剩余物品单位单位最大价值

• 更紧密、复杂的上界 $ub = v + \sum{k=i+1}^K v_k + (W - \sum{k=1}^K w_k)v_K / w_K$

算法

特点

• 分支界限法求解背包问题中，每个中间节点都是给定物品的子集 ，是背包问题的可行解

背包问题近似算法

贪婪算法

算法

• 对物品按照价值重量比$r_i = v_i / w_i, i=1,2,\cdots,n$ 降序排列

• 重复以下直到有序列表中不留下物品

  • 如果列表中当前物品可以装入，则放入背包并处理下个物品
  • 否则忽略，直接处理下个物品

特点

• 原始的贪婪算法解的精确率没有上界

  • 考虑：承重量为$W$背包，如下物品

    |物品|重量|价值|价值/重量| |——-|——-|——-|——-| |1|1|2|2| |2|w|w|1|

  • 则近似解精确率$r(s_a) = W/2$无上界

• 增强版贪婪算法：取贪婪算法解、能装载的价值最大单个物品 价值中较大者

  • 此改进的性能比可以降到2

近似方案

背包问题的存在多项式时间的系列算法，可以调节算法中参数$k$ 得到满足任意预定义精确率的近似解$s_a^{(k)}$

Sahni方案

• 生成所有小于k个物品的子集
• 向贪婪算法一样，向每个能装入背包的子集添加剩余物品中 价值重量比最大者
• 得到最有价值的修改后子集作为结果返回

Fully Polynomial Scheme

完全多项式方案

特点

• Sahni方案理论意义远大于实用价值

  • 其效率$\in O(kn^{k+1})$是n的多项式函数
  • 但是是k的指数函数

• 完全多项式方案更加复杂，但没有效率为参数k指数的缺陷

Bin-Packing Problem

装箱问题：给定n个问题，大小都是不超过1的有理数，将其装进数量 最少的大小为1的箱子中

Graph-Coloring Problem

图着色问题：对给定图，求使得任何两个相邻顶点颜色都不同时， 需要分配给图顶点的颜色数量

划分问题

给定n个正整数${a_i, i=1,2,\cdots}，判定能够将其划分为和相等 的两个子集

Subset-Sum Problem

给定n个正整数${a_i, i=1,2,\cdots}$，求子集$S$和为正整数d

回溯算法

约束

• 其中$s$为考虑考虑第i+1元素时，前i个元素选情况下的和

算法

• 假设集合元素按升序排列

• 根节点为未选择任何元素

• 依次考虑将元素$a_i$添加进子集S中

  • 若满足约束条件、下个元素未考虑，继续考虑
  • 否则回溯，重新考虑父母节点

• 直到找到子集满足和为d，或第二次回溯到根节点

特点

币值最大化

给定一排n个硬币，币值为正整数$c_i, i=1, 2, \cdots, n$（币值 不唯一），在原始位置不相邻的情况下，使得所选硬币总金额最大

动态规划

算法

记最大可选金额为$F(n)$将可行规划分为两组

• 包含最后一枚硬币，最大金额为$c_n + F(n-2)$
• 不包含最后一枚硬币，最大金额为$F(n-1)$

则递推方程为

1
2
3
4
5
6
7
8
9

CoinRow(C[1..n])
	// 在所选硬币不相邻，从一排硬币中选择最大金额
	// 输入：C[1..n]保存n个硬币面值
	// 输出：可选硬币最大金额
	F[0] = 1
	F[1] = C[1]
	for i = 2 to n do
		F[i] = max(C[i] + F[i-2], F[i-1])
	return F[n]

算法特点

• 时间效率$\in \Theta(n)$
• 空间效率$\in \Theta(n)$

找零问题

需找零金额为n，最少需要多少面值为$d_1 < d_2 < \cdots < d_n$ 的硬币，考虑$d_1 = 1$的一般情况

动态规划

算法

记$F(n)$为总金额为n的数量最少的硬币数目，定义$F(0)=0$

• 得到n的途径只能是在$n-d_j$上加入面值为$d_j$的硬币，其中 $j=1, 2, \cdots, m$，且$n \geqslant d_j$

• 考虑所有满足条件$d_j$，选择使得且$F(n - d_j)$最小者

则递推式有

1
2
3
4
5
6
7
8
9
10
11
12
13

ChangeMaking(D[1..m], n)
	// 动态规划法求解找零问题，d_1 = 1
	// 输入：正整数n，币值数组D[1..m]
	// 输出：总金额为n的最少硬币数目
	F[0] = 0
	for i = 1 to n do
		tmp = \infty
		j = 1
		while j <= m and i >= D[j] do
			tmp = min(F[i-D[j], tmp)
			j += 1
		F[i] = tmp + 1
	return F[n]

硬币收集问题

在n * m格木板中存放有硬币，每格硬币最多一个，寻找左上角(1,1) 到右下角(n, m)路径，使得能够收集尽可能多硬币，每次只能向下、 向右移动

动态规划

算法

记$F(i, j)$为截止到第i行、第j列单元格$(i, j)$能够收集到最大 硬币数

• 单元格$(i, j)$只能经由$(i-1, j)$、$(i, j-1)$达到
  • 初值1：假定$F(0, j)=0, F(i, 0)=0$
  • 初值2；递推求解$F[1, j], F[i, 1]$

则递推方程为

1
2
3
4
5
6
7
8
9
10
11
12
13
14

CoinCollection(C[1..n, 1..m])
	// 动态规划算法求解硬币收集问题
	// 输出：矩阵C[1..n, 1..m]表示单元格是否有硬币
	// 输出：在单元格[n, m]能够收集到的最大硬币数
	F[1, 1] = C[1, 1]
	for j = 2 to m do
		F[1, j] = F[1, j-1] + C[1, j]
		// 初始化首行
	for i = 2 to n do
		F[i, 1] = F[i-1, 1] + C[i, 1]
		for j = 2 to n do
			// 先填列
			F[i, j] = max(F[i-1, j], F[i, j-1]) + C[i, j]
	return F[n, m]

算法特点

• 算法效率
  • 计算每个单元格$F[i, j]$花费常量时间，所以算法时间 效率$\in \Theta(nm)$
  • 算法空间效率$\in Theta(nm)$

n皇后问题

将n个皇后放在$n * n$的棋盘上，使得皇后之间不能相互攻击

回溯算法

算法

算法特点

说明

• $n \geqslant 4$的n皇后问题都可以在线性时间内求解，已经 找到一些可选公式，用于计算n皇后的位置

生成排列

生成集合排列问题可以抽象为生成${1,\cdots,n}$所有$n!$个排列的 问题

• 假设$(n-1)!$个排列已经生成
• 则可以把n插入n-1个元素中可能的n个位置中去，得到较大规模 问题的解

最小变化

• 在元素上使用小箭头标记其方向： $\overleftarrow 1 \overleftarrow 2 \overleftarrow 3$
• 如果元素k的箭头指向相邻的较小元素，称在此排列中是移动的

减常量法

1
2
3
4
5
6
7
8
9
10

JohnsonTrotter(n)
	// 生成排列
	// 输入：正整数n
	// 输出：{1..n}所有排列列表
	将第一个排列初始化
	while 存在一个移动元素 do
		求最大的移动元素k
		把k和其箭头指向的相邻元素互换
		调转所有大于k的元素的方向
		将新排列添加到列表中

算法特点

• JsonTrotter是生成排列最有效算法之一，其运行时间和排列 数量成正比，即$\in \Theta(n!)$

字典序

减常量法

• 找到序列中最长递减后缀 $a{i+1} > a{i+2} > \cdots > a_{n}$
• 将$a_i$同序列中大于其的最小元素交换
• 将新后缀颠倒，使其变为递增序列，加入列表中

1
2
3
4
5
6
7
8
9
10
11
12
13

LexicographicPermute(n):
	// 以字典序产生排列
	// 输入：正整数n
	// 输出：字典序下，所有排列列表
	初始化第一个排列为12...n
	while 最后一个排列有两成连续升序元素 do
		找出使得a_i < a_{i+1}的最大的i
			// 即找到最长递减后缀
		找到使得a_i < a_j的最大索引
			// 即在后缀中大于其的最小元素索引
		交换a_i和a_j
		将a_{i+1}和a_{n}的元素反序
		将新排列添加至列表中

生成子集

集合$A[a_1, \cdots, a_n}$的所有子集可以分为两组

• 包含$a_n$：${a_1, \cdots, a_n}$的所有子集
• 不包含$a_n$的子集：把$a_n$添加进${a_1, \cdots, a_n}$子集 获得

• 同样的可以把集合抽象为位串，每个位串表示一个子集

减常量算法

字典序

按生成字典序（位串字典序）生成子集

• 将正序${1..n}$转换为二进制位串
• 依次按照二进制位串生成子集
  • 位串中为1表示对应元素在子集中

挤压序

按照挤压序（位串挤压序）生成子集

• 将倒序{n..1}转换为二进制位串
• 依次按照二进制位串生成子集
  • 位串中为1表示对应元素在子集中

Squashed Order：所有包含$aj$子集必须紧排在所有包含 $a_1, \cdots, a{j-1}$的子集之后

最小变化

每个子集和其直接前趋之间，要么增加一个元素，要么减少一个元素

• 即每个位串和直接前趋之间仅仅相差一位

1
2
3
4
5
6
7
8
9
10
11
12
13

BRGC(n)
	// 递归生成二进制反射格雷码
	// 输入：正整数n
	// 输出：所有长度为n的格雷码位串列表
	if n == 1
		表L包含位串0、位串1
	else
		调用BRGC(n-1)生成长度为n-1的位串列表L1
		表L1倒序后复制给表L2
		把0加到表L1每个位串前
		表1加到表L2每个位串前
		把表L2添加到表L1后得到表L
	return L

球、桶问题

n个球放入m个桶中情况数量

球同、桶不同、无空桶

• 插板法

  $$\left \{ \begin{array}{l} C_{n-1}^{m-1}, & n \geq m \\ 0, & n < m \end{array} \right.$$

球同、桶不同、可空桶

• 插板法：可以假设m个桶中已经放好球，即m+n个相同球放入m个 不同桶、不允许空桶

  $$C_{n+m-1}^{m-1}$$

球同、桶同、可空桶

• 动态规划

  $$dp_4[i][j] = \left \{ \begin{array}{l} dp_4[i][j-1] + dp_4[i-j][j], & i \geq j \\ dp_4[i][j-1], & i < j \\ 1, & i=1,0 or j=1 \end{array} \right.$$

• 球数$i \geq j$桶数时递推式

  • 若有桶均包含球：剩余球可能性$dp[i-j][j]$
  • 若存在桶不包含球：剔除一个桶不影响总数
  • 没有其余情况

球同、桶同、无空桶

• 动态规划：由$dp_4$得到

  $$dp_5[i][j] = \left \{ \begin{array}{l} dp_4[i-j][j], & i \geq j \\ 0, & i < j \end{array} \right.$$

球不同、桶同、无空桶

• 第二类斯特林数

  $$dp[i][j] = \left \{ \begin{array}{l} j*dp[i-1][j] + dp[i-1][j-1], & 1 \leq j < i \\ 1, & i = j \\ 0, & i < j \end{array} \right.$$

• 球数$i>j$桶数时递推式

  • 考虑前$i-1$球已经占满所有桶，则最后球放入任何桶都是 新情况
  • 考虑前$i-1$只占满$j-1$个桶，则最后球必须放入空桶
  • 其他情况不可能

球不同、桶同、可空桶

• 在球不同、桶同、无空桶情况下枚举不空桶数目

  $$dp_2[i][j] = \sum_{k=1}^j dp[i][j]$$

球不同、桶不同、无空桶

• 在球不同、桶同、无空桶情况下对桶排序

  $$dp_3[i][j] = dp[i][j] * (j!)$$

球不同、桶不同、可空桶

• 每个球都有m中选择：$m^n$

总述

在给定的集合、多重集（允许多个元素具有相同的值）中找给定值 （查找键，search key）

• 顺序搜索
• 折半查找：效率高但应用受限
• 将原集合用另一种形式表示以方便查找

评价

没有任何一种查找算法在任何情况下都是最优的

• 有些算法速度快，但是需要较多存储空间
• 有些算法速度快，但是只适合有序数组

查找算法没有稳定性问题，但会发生其他问题

• 如果应用里的数据相对于查找次数频繁变化，查找问题必须结合 添加、删除一起考虑

• 必须仔细选择数据结构、算法，以便在各种操作的需求间达到 平衡

无序线性表查找

顺序查找

算法

• 将给定列表中连续元素和给定元素查找键进行比较
  • 直到遇到匹配元素：成功查找
  • 匹配之前遍历完整个列表：失败查找

1
2
3
4
5
6
7
8
9
10
11
12

SequentialSearch(A[0..n-1], K)
	// 顺序查找，使用**查找键作限位器**
	// 输入：n个元素数组A、查找键K
	// 输出：第一个值为K的元素位置，查找失败返回-1
	A[n] = K
	i = 0
	while A[i] != K do
		i = i + 1
	if i < n
		return i
	else
		return -1

改进

• 将查找键添加找列表末尾，查找一定会成功，循环时将不必每次 检查是否到列表末尾
• 如果给定数组有序：遇到等于（查找成功）、大于（查找失败） 查找键元素，算法即可停止

二叉查找树

算法

• 对数组构建二叉查找树
• 在二叉查找树上进行查找

特点

• 算法效率：参见二叉查找树

• 构建二叉查找树（插入）和查找操作基本相同，效率特性也相同

• 减可变规模 + 输入增强

预排序查找

对线性表预排序，有序表中查找速度快得多

算法

1
2
3
4
5
6
7

PreorderSearch(A[0..n-1])
	// 对数组预排序然后查找
	// 输入：可排序数组A[0..n-1]
	// 输出：元素在数组中的位置
	对B[(数组元素, 索引)]进行预排序
	使用折半查找寻找二元组
	返回二元组中索引

特点

• 算法时间效率：取决于排序算法

  • 查找算法在最差情况下总运行时间$\in \Theta(nlogn)$
  • 如果需要在统一列表上进行多次查找，预排序才值得

• 这种预排序思想可以用于众数、检验惟一性等， 此时算法执行时间都取决于排序算法 （优于蛮力法$\in \Theta(n^2)$）

• 变治法（输入增强）

预排序检验唯一性

1
2
3
4
5
6
7
8
9

PresortElementUniqueness(A[0..n-1])
	// 先对数组排序，求解元素唯一性问题
	// 输入：n个可排序元素构成数[0..n-1]
	// 输出：A中有相等元素，返回true，否则false
	对数组排序
	for i=0 to n-2 do
		if A[i] = A[i+1]
			return false
	return true

预排序求众数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

PresortMode(A[0..n-1])
	// 对数组预排序来计算其模式（众数）
	// 输入：可排序数组A[0..n-1]
	// 输出：数组模式
	对数组A排序
	i = 0
	modefrequency = 0
	while i <= n-1 do
		runlength = 1
		runvalue = A[i]
		while i + runlength <= n-1 and A[i+runlength] == runvalue
			// 相等数值邻接，只需要求出邻接次数最大即可
			runlength = runlength+1
		if runlength > modefrequency
			modefrequency = runlength
			modevalue = runvalue
		i = i+runlength

	return modevalue

有序顺序表查找

• 有序顺序表的查找关键是利用有序减规模

• 但关键不是有序，而是减规模，即使顺序表不是完全有序， 信息足够减规模即可

折半查找/二分查找

二分查找：利用数组的有序性，通过对查找区间中间元素进行判断， 缩小查找区间至一般大小

• 依赖数据结构，需能够快速找到中间元素，如数组、二叉搜索树

• 一般模板：比较中间元素和目标的大小关系、讨论

  1 2 3 4 5 6 7 8 9

  left, right = ... while condition(search_space is not NULL): mid = (left + right) // 2 if nums[mid] == target: // do something elif nums[mid] > target: // do something elif nums[mid] < target: // do somthing

  • 函数独立时，找到target可在循环内直接返回
  • 函数体嵌入其他部分时，为方便找到target应break， 此时涉及跳出循环时target可能存在的位置
    • 找到target中途break
    • 未找到target直到循环终止条件

基本版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

BinarySearchEndReturnV1(nums[0..n-1], target):
	// 非递归折半查找基本版，不直接返回，方便嵌入
	// 输入：升序数组nums[0..n-1]、查找键target
	// 输出：存在返回数组元素下标m，否则返回-1
	left, right = 0, n-1
	while left <= right:
		mid = (left + right) // 2
		if nums[mid] == target:
			break
		elif nums[mid] < target:
			left = mid+1
		else:
			right = mid-1
	else:
		assert(mid == right == left-1)

	# 仅最后返回，方便嵌入，下同
	if nums[mid] == target:
		return mid
	else:
		return -1

• 输入判断：无需判断输入列表是否为空

  • 终止条件保证不会进入，即不会越界

• 初始条件：left, right = 0, n-1

  • 左、右均未检查、需检查
  • 即代码中查找区间为闭区间$[left, right]$，此时 搜索区间非空

• 中点选择：mid = (left + right) // 2

  • 向下取整
  • 对此版本无影响，left、right总是移动，不会死循环

• 循环条件：left <= right

  • 搜索区间为闭区间，则相应检查条件为left <= right， 否则有元素未被检查
  • 在循环内left、right可能重合

• 更新方式：left=mid+1, right=mid-1

  • 为保证搜索区间始终为闭区间，需剔除mid

• 终止情况：right=left-1、mid=left/right

  • 循环条件、循环内部+1保证：上轮循环left==right
  • 越界终止情况：左、右指针均剔除mid，两侧均可能越界
    • mid=right=n-1, left=n
    • mid=left=0, right=-1

• target位置

  • 若存在target：必然在mid处，循环结束只需判断mid
  • 若不存在target
    • target位于[right, left]间
    • left=mid+1=right+1表示小于target元素数量

• 需要和左右邻居（查找结束后）、left、right比较 情况下，容易考虑失误，不适合扩展使用

高级版1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

BinarySearchV2(nums[0..n-1], target):
	left, right = 0, n
	while left < right:
		mid = (left + right) // 2
		if nums[mid] == target:
			break
		elif nums[mid] < target:
			left = mid+1
		else:
			right = mid
	else:
		assert(mid-1 == left == right)

	if nums[mid] == target:
		return mid
	else:
		return -1

• 输入判断：无需判断输入列表是否为空

  • 终止条件保证不会进入，即不会越界

• 初始条件：left, right = 0, n

  • 左未检查、需检查，右无需检查
  • 即代码中查找区间为左闭右开区间$[left, right)$

• 中点选择：mid = (left + right) // 2

  • 向下取整
  • 此处必须选择向下取整，否则left=right-1时进入死循环
  • 即：循环内检查所有元素，取整一侧指针必须移动

• 循环条件：left < right

  • 搜索区间为左闭右开区间，则检查条件为left < right， 此时搜索区间非空
  • 在循环内left、right不会重合

• 更新方式：left=mid+1, right=mid

  • 为保证搜索区间始终为左闭右开区间
    • 移动左指针时需剔除mid
    • 移动右指针时无需剔除mid

• 终止情况：right=left、mid=left/left-1

  • 循环条件、循环内部+1保证：上轮循环
    • left+1=mid=right-1
    • left=mid=right-1
  • 越界终止情况：仅左指针剔除mid，仅可能右侧越界
    • left=right=n=mid+1

• target位置

  • 若存在target：必然在mid处，循环结束只需判断mid
  • 若不存在target
    • left=mid=right：循环过程中target可能已不在 搜索区间中，最终位于(mid-1, mid)
    • mid+1=left=right：(mid, left)
    • left表示小于target元素数量

高级版2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

BainarySearchEndReturnV3(nums[0..n-1], target):
	// 折半查找，保持左右指针顺序、不重合
	// 输入：升序数组nums、查找键target
	// 输出：存在返回数组元素下标m，否则返回-1
	left, right = -1, n
	while left < right:
		mid = (left + right + 1) // 2
		if nums[mid] == target:
			break
		elif nums[mid] < target:
			right = mid-1
		else:
			left = mid

	if nums[mid] == target:
		return mid
	else:
		return -1

• 输入判断：无需判断输入列表是否为空

  • 终止条件保证不会进入，即不会越界

• 初始条件：left, right = -1, n-1

  • 左无需检查，右未检查、需检查
  • 即代码中查找区间为左开右闭区间$(left, right]$

• 中点选择：mid = (left + right + 1) // 2

  • 向上取整
  • 此处必须选择向上取整，否则left=right-1时进入死循环 （或放宽循环条件，添加尾判断）
  • 即：循环内检查所有元素，取整一侧指针必须移动

• 循环条件：left < right

  • 搜索区间为左开右闭区间，则检查条件为left < right， 此时搜索区间非空
  • 在循环内left、right不会重合

• 更新方式：left=mid, right=mid+1

  • 为保证搜索区间始终为左闭右开区间
    • 移动右指针时需剔除mid
    • 移动左指针时无需剔除mid

• 终止情况：left=right、mid=left/left+1

  • 循环条件、循环内部+1保证：上轮循环
    • left+1=mid=right-1
    • left+1=mid=right
  • 越界终止情况：仅右指针剔除mid，仅可能左侧越界
    • left=right=-1=mid-1

• target位置

  • 若存在target：必然在mid处，循环结束只需判断mid
  • 若不存在target
    • left=mid=right：循环过程中target可能已不在 搜索区间中，最终位于(right, right+1)
    • mid+1=left=right：(left, right)
    • left+1表示小于target元素数量

高级版3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

BinarySearchEndReturnV2(nums[0..n-1], target):
	// 折半查找，保持左右指针顺序、不重合
	// 输入：升序数组nums、查找键target
	// 输出：存在返回数组元素下标m，否则返回-1
	left, right = -1, n
	while left < right-1:
		mid = (left + right) // 2
		if nums[mid] == target:
			break
		elif nums[mid] < target:
			left = mid
		else:
			right = mid

	if nums[mid] == target:
		return mid
	else:
		return -1

• 输入判断：无需判断输入列表是否为空

  • 终止条件保证不会进入，即不会越界

• 初始条件：left, right = -1, n

  • 左、右均无需检查
  • 即代码中查找区间为开区间$(left, right)$

• 中点选择：mid = (left + right) // 2

  • 向下取整、向上取整均可

• 循环条件：left < right-1

  • 搜索区间为左开右闭区间，则检查条件为left < right-1， 此时搜索区间非空
  • 在循环内left、right不会重合

• 更新方式：left=mid, right=mid

  • 循环终止条件足够宽泛，不会死循环

• 终止情况：left=right-1、mid=right/right-1

  • 循环条件、循环内部+1保证：上轮循环
    • left+1=mid=right-1
  • 越界终止情况：左右初始条件均越界，则左、右均可能越界
    • mid=left=n-1、right=n
    • left=-1、mid=right=0

• target位置

  • 若存在target：必然在mid处，循环结束只需判断mid
  • 若不存在target
    • target始终在搜索区间(left, right)内
    • 最终位于(left, right)

高级版1-原

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

BinarySearchKeep1(nums[0..n-1], target):
	// 折半查找，保持左右指针顺序、不重合
	// 输入：升序数组nums、查找键target
	// 输出：存在返回数组元素下标m，否则返回-1
	if n == 0:
		return -1

	left, right = 0, n-1

	while left < right - 1:
		mid = floor((left + right) / 2)
		if nums[mid] == target:
			return mid

		elif nums[mid] < target:
			right = mid
		else:
			left = mid

	// post-procesing
	if nums[left] == target:
		return left
	if nums[right] == target:
		return right

	return -1

• 初始条件：left = 0, right = n-1
• 终止情况：left = right - 1
• 指针移动：left = mid, right= mid

• 关键特点

  • n>1时left、mid、right循环内不会重合
  • mid可以left、right任意比较，无需顾忌重合
  • 需要和左右邻居、left、right比较时适合使用
  • 扩展使用需要进行真后处理，对left、right进行判断

• 终止情况：left = right - 1

  • 循环过程中会保证查找空间至少有3个元素，剩下两个 元素时，循环终止
  • 循环终止后，left、right不会越界，可以直接检查

• target位置

  • 若存在target，可能位于mid、left、right

    • mid：因为找到nums[mid]==target跳出
    • left：left=0，循环中未检查
    • right：right=n-1，循环中未检查

  • 不存在target，则target位于(left, right)之间

  • 适合访问目标在数组中索引、极其左右邻居

• 仅仅二分查找的话，后处理其实不能算是真正的后处理

  • nums[mid]都会被检查，普通left、right肯定不会 是target所在的位置

  • 真正处理的情况：target在端点

    • left=0, right=1终止循环，left=0未检查
    • left=n-2, right=n-1终止循环，right=n-1未检查

  • 即这个处理是可以放在循环之前进行处理

高级版2-原

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

BinarySearchKeep0(nums[0..n-1], target):
	// 折半查找，保证左右指针不交错
	// 输入：升序数组nums、查找键target
	// 输出：存在返回数组元素下标m，否则返回-1
	if n == 0:
		return -1

	left, right = 0, n
	while left < right:
		mid = floor((left + right) / 2)
		if nums[mid] == target:
			return mid

		elif nums[mid] < target:
			left = mid + 1
		else:
			right = mid

	// post-processing
	if left != len(nums) and nums[left] == target:
		return left

	return -1

• 初始条件：left = 0, right = n，保证n-1可以被正确处理
• 终止情况：left = right
• 指针移动：left = mid + 1, right = mid
• 中点选择对此有影响，指针移动行为非对称，取ceiling则 终止情况还有left = right + 1

• 关键特点

  • left、right循环内不会重合
  • 由于floor的特性，mid可以right任意比较，无需 顾忌和right重合
  • 需要和右邻居、right比较时适合使用

• 终止情况：left = right

  • 循环过程中会保证查找空间至少有2个元素，否则循环 终止
  • 循环终止条件导致退出循环时，可能left=right=n越界

• target位置

  • 若存在target，可能位于mid、left=right
  • 若不存在target，则target位于(left-1, left)
  • 适合访问目标在数组中索引、及其直接右邻居

• 仅二分查找，甚至无需后处理

• 判断nums长度在某些语言中也可以省略

高级版3-原

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

BinarySearchNoKeep(nums[0..n-1], target):
	// 折半查找，保证左右指针不交错
	// 输入：升序数组nums、查找键target
	// 输出：存在返回数组元素下标m，否则返回-1
	if n == 0:
		return -1

	left, right = -1, n-1
	while left < right - 1:
		mid = floor((left + right) / 2)
		if nums[mid] == target:
			return mid

		elif nums[mid] < target:
			left = mid
		else:
			right = mid - 1

	// post-processing
	if right >= 0 and nums[right] == target:
		return right

	return -1

• 初始条件：left = -1, right = n-1
• 终止情况：left = right、left = right + 1
• 指针移动：left = mid, right = mid - 1
• 中点选择对此有影响，指针移动行为非对称，取ceiling则 同高级版本2

• 终止条件：left = right、left = right - 1

  • 循环过程中保证查找空间至少有3个元素，否则循环 终止

  • 由于floor特性，必须在left < right - 1时即终止 循环，否则可能死循环

  • 循环终止后，left=right=-1可能越界

• target位置

  • 若存在target，可能位于mid、left=right
  • 若不存在target，则target位于(left, left+1)
  • 适合访问目标在数组中索引、及其直接左邻居

• 此版本仅想实现二分查找必须后处理

  • 终止条件的原因，最后一次right=left + 1时未被检查 即退出循环

  • 可能在任何位置发生，不是端点问题

特点

• 前两个版本比较常用，最后两个版本逻辑类似

• 折半查找时间效率

  • 最坏情况下：$\in \Theta(log n)$
  • 平均情况下仅比最差稍好

• 就依赖键值比较的查找算法而言，折半查找已经是最优算法 ，但是插值算法、散列法等具有更优平均效率

• 减常因子因子法

插值查找

Interpolation Search：查找有序数组，在折半查找的基础上考虑 查找键的值

算法

• 假设数组值是线性递增，即数字值~索引为一条直线，则根据 直线方程，可以估计查找键K在A[l..r]所在的位置

  $$x = l + \left \lfloor \frac {(K-A[l])(r-l)} {A[r] - A[l]} \right \rfloor$$

• 若k == A[x]，则算法停止，否则类似折半查找得到规模更小的 问题

特点

• 即使数组值不是线性递增，也不会影响算法正确性，只是每次 估计查找键位置不够准确，影响算法效率

• 统计考虑

  • 折半插值类似于非参方法，只考虑秩（索引）方向
  • 插值查找类似参数方法，构建了秩（索引）和数组值模型， 但是线性关系基于假设
  • 如果模型错误可能会比折半查找效率更差，即在数据分布 分布偏差较大的情况下非参方法好于参数方法

• 所以是否可以考虑取样方法，先取5个点构建模型，然后估计

• 算法效率

  • 对随机列表，算法比较次数小于$log_2log_n+1$
  • 最差情况，比较次数为线性，没有折半查找稳定
  • Robert Sedgewick的Algorithms中研究表明，对较小文件 折半查找更好，大文件、比较开销大插值查找更好

• 减可变规模

子串匹配

蛮力字符串匹配

算法

• 将pattern对齐文本前m个字符，从左向右匹配相应字符
  • m个字符全部匹配，匹配成功，算法停止
  • 遇到不匹配字符则
• 模式右移1位，然后从模式首个字符开始重复以上匹配
• 在n-m位置无法匹配成功，则无足够匹配字符，算法停止

1
2
3
4
5
6
7
8
9
10
11
12

BruteForceStringMatch(T[0..n-1], P[0..m-1])
	// 蛮力字符串匹配
	// 输入：文本T：n个字符的字符数组
	//       模式：m个字符的字符数组
	// 输出：查找成功返回文本第一个匹配子串中第一个字符位置
	for i = 0 to m-m do
		j = 0
		while j < m and P[j] = T[i+j] do
			j = j + 1
			if j = m
				return i
	return -1

特点

• 最坏情况下，算法比较次数属于$O(nm)$
  • 即在移动模式之前，算法需要做足m次比较
  • 但是一般在自然语言中，算法平均效率比最差好得多
  • 在随机文本中，有线性效率

Horspool算法

算法从右往左匹配，在任意位置匹配不成功时只考虑 同模式最后字符匹配的文本字符c，确定安全移动距离，在 不会错过匹配子串的情况下移动最长距离

• 如果c在模式中出现，则模式移动到其最后c至同文本中c 匹配
• 否则移动模式长度m
• 特别的，如果c只在模式最后字符出现，则也应该移动m

算法

• 对给定长度m的模式及文本中用到的字母表，构造移动表t
• 将模式同文本开始对齐
• 重复以下过程直至发了了匹配子串或模式达到了文本字符外
  • 从模式最后字符开始，比较模式、文本相应字符
  • 若m个字符匹配，停止
  • 遇到不匹配字符c，若为当前文本中和模式最后匹配字符 对齐的字符，将模式移动t(c)个字符

1
2
3
4
5
6
7
8
9
10
11

ShiftTable(P[0..m-1])
	// 用Horspool算法、Boyer-Moore算法填充移动表
	// 输入：模式P[0..m-1]、可能出现字符表
	// 输出：以字符表为为索引的数组Table[0..size-1]
	for i=0 to size-1 do
		Table[i] = m
		// 初始化所有字符对应移动距离为m
	for j=0 to m-2 do
		Table[P[j]] = m - 1 - j
		// 对模式中存在的字符重新计算移动距离
	return Table

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

HorspoolMatching(P[0..m-1], T[0..n-1])
	// 实现Horspool字符串匹配算法
	// 输入：模式P[0..m-1]、文本T[0..n-1]
	// 输出：第一个匹配子串最左端字符下标，未匹配返回-1
	Table = ShiftTable(P[0..m-1])
	i = m - 1
	while i <= n-1 do
		k = 0
		while k <= m-1 and P[m-1-k]=T[i-k] do
			k = k+1
		if k == m
			return i-m+1
		else
			i = i+Table[T[i]]
	return -1

特点

• 算法效率

  • 最差情况下模式为相同字符，效率$\in O(nm)$
  • 对随机文本效率$\in O(n)$

• 输入增强

Boyer-Moore算法

• 坏符号移动：模式、文本中相应不匹配字符确定的移动 （不是Horspool中简单根据最后字符确定移动）
• 好后缀移动：模式、文本匹配的后缀确定的移动

算法

• 对给定长度m的模式及文本用到的字母表，构造坏符号移动表t
• 对给定长度m的模式构造后缀移动表
• 将模式与文本开始处对齐
• 重复以下直到找到匹配子串或模式达到文本字符以外
  • 从模式最后字符开始比较模式、文本相应字符
  • 所有m个字符匹配，则停止
  • 若c是不匹配字符，移动坏符号表、后缀移动表决定的 距离较大者

1
2
3
4
5

BadSymbolShift(P[0..m-1])
	// 创建坏符号移动表
	// 输入：模式P[0..m-1]
	// 输出：坏符号移动表

特点

• 算法效率

  • 算法效率最差也是线性的

• 输入增强

KMP算法

算法从左往右匹配，失败时不回溯指针，利用已经得到的 部分匹配结果尽可能将模式滑动一段距离，从模式中间next 字符开始比较

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

KMPShift(P[0..m-1])
	// 计算KMP算法next值
	// 输入：模式P[0..m-1]
	// 输出：模式中各元素next值数组
	i = -1
		// 表示开始比较文本中下个字符
	j = 0
	next[0] = -1
		// 即如果模式首字符都不匹配，比较文本下个字符
	while j < m
		if i == -1 or P[j] == P[i]
			i += 1
			j += 1
			// 当前字符匹配成功，决定下个字符next值
			next[j] = i
		else
			i = next[i]
			// 若当前字符没有匹配成功，不会立即处理下个字符
			// next值，而是反复迭代、查询已匹配部分next值，
			// 以获得最大匹配前缀
	return next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

KMPShiftVal(P[0..m-1])
	// 计算KMP算法next值修正版（考虑next值与当前相等）
	// 输入：模式P[0..m-1]
	// 输出：模式中各元素next_val值数组u
	i = -1
		// 表示开始比较文本中下个字符
	j = 0
	next_val[0] = -1
	while j < m do
		if i == -1 or P[j] == P[i]
			i += 1
			j += 1
			if T[j] != T[i]
				next_val[j] = i
			else
				next_val[j] = next_val[i]
				// 考虑了next值相同时，可以再滑动一次
				// 这里会导致next_val值跳跃
		else
			i = next_val[i]
	return next_val

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

KMPMatching(P[0..m-1], T[0..n-1])
	// 实现KMP字符串匹配算法
	// 输入：模式P[0..m-1]、文本T[0..n-1]
	// 输出：第一个匹配子串最左端字符下标，未匹配返回-1
	i = 0
	j = 0
	while i < m and j < n do
		if i == -1 or P[i] == T[j]
			i += 1
			j += 1
		else
			i = next[i]
	if i >= m
		return j - m + 1
	else
		return -1

特点

• 算法效率

  • 算法时间效率$\in O(m+n)$

• 文本指针不需要回溯，整个匹配过程只需要对文本扫描一次， 对流程处理十分有效，可以边读边匹配

• 输入增强

总述

• 按照升序重新排列给定列表中的数据项
• 为了让问题有意义，列表中的数据项应该能够排序（数据之间 有一种全序关系）
• 键：在对记录排序时，需要选取的、作为排序的依据的一段信息

目的

• 排序可能是所求解的问题输出要求
• 排序能够更方便的求解和列表相关的问题
  • 查找问题
• 在其他领域的重要算法中，排序也被作为辅助步骤

发展

• 排序领域已经有很多不错的算法，只需要做$nlog_{x}^{n}$次 比较就能完成长度为$n$的任意数组排序，且没有一种基于 键值比较（相较于比较键值部分内容而言）的排序算法能 在本质上操作其，

• 但是还是需要不断探寻新的算法虽然有些算法比其他的要好， 但是没有任何算法在任何情况下是最优的

  • 有些算法比较简单，但速度较慢
  • 有些算法适合随机排列的输入，而有些适合基本有序的列表
  • 有些算法适合驻留在快速存储器中的列表，而有些适合存储 在磁盘上的大型文件排序

评价

• 稳定性：排序算法保留等值元素在输入中的相对顺序
  • 一般来说，将相隔很远的键交换位置的算法虽然不稳定， 但往往很快
• 在位性：排序算法不需要额外的存储空间，除极个别存储单元外

线性表排序

选择排序

• 每轮选择出剩余元素中最小值，放在对于位置上

顺序表算法

1
2
3
4
5
6
7
8
9
10

SelectionSort(A[0..n-1]):
	// 选择排序排序数组
	// 输入：可排序数组A[0..n-1]
	// 输出：升序排序数组A[0..n-1]
	for i = 0 to n-1 do
		min = i
		for j = i to n-1 do
			if A[j] < A[min]
				min = j
		swap A[i] and A[min]

• 扫描整个列表找到最小元素，然后和首个元素交换，将其放在 最终位置上
• 从第2个元素开始寻找之后最小元素，和第2个元素交换，将其 放在最终位置上
• 重复n-1次，列表有序

链表算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

SelectionSort(linked):
	// 选择排序排序链表
	// 输入：可排序链表linked头
	// 输出：排序后链表头
	if linked == NULL:
		return NULL
	linked_head = ListNode()
		// 为方便附设头结点
	linked_head.next = linked
	unsorted_head = linked_head
		// 未排序头结点
		// 后续过程中是链表中元素

	while unsorted_head.next != NULL:
		cur_node = unsorted_head
		min_node = unsorted_head
			// 全是链表中元素
		while cur_node.next != NULL:
			if cur_node.next.val < min_node.next.val:
				min_node = cur_node
			cur_node = cur_node.next

		// 若`min_node.next`就是`unsorted_start.next`，以下
			// 代码中的断开、重组链表操作会出现环
		// 完全切开再重组链表，则需要判断`unsorted_start`
			// 是否为空
		if unsorted_start.next != min_node.next:
			_tmp_node = unsorted_head.next
				// 记录原`unsorted_head.next`

			unsorted_head.next = min_node.next
				// `unsorted_head.next`断开、连接`min_node`

			min_node.next = min_node.next.next
				// `min_node.next`断开、跳过`min_node`重连
				// 若`min_node.next`是`unsorted_start.next`
					// 会断开`unsorted_start`和`min_node`

			unsorted_head.next.next = _tmp_node
				// 原`min_node`重连原`unsorted_head.next`

		unsorted_start = unsorted_start.next

	return linked_head.next

特点

• 对任何输入，选择排序键值比较都是$\Theta(n^2)$
• 键交换次数仅为$\Theta(n)$
  • 选择排序此特性优于许多其他排序算法

冒泡排序

• 比较表中相邻元素，如果逆序就交换位置
• 重复多次则最大元素被“沉到”列表最后位置
• 第2轮比较将第2大元素“沉到”其最终位置
• 重复比较n-1轮，列表有序

顺序表算法

1
2
3
4
5
6
7
8

BubbleSort(A[0..n-1]):
	// 冒泡排序排序数组
	// 输入：可排序数组A[0..n-1]
	// 输出：升序排序数组A[0..n-1]
	for i = 0 to n-2 do
		for j = 0 to n-2-i do
			if A[j+i] < A[j]
				swap A[j] and A[j+1]

链表算法

1
2
3
4

BublleSort(head):
	// 冒泡排序排序链表
	// 输入：可排序链表首个元素
	// 输出：排序后列表首个元素

特点

• 对任何输入，冒泡排序键值比较都是$\Theta(n^2)$
• 其交换次数取决于特定输入
  • 最坏情况是遇到降序排列数组，此时键交换次数同比较次数
• 冒泡排序看起来就像是选择排序的一直交换+最大优先版本

改进

• 如果对列表比较一轮后没有交换任何元素，说明列表有序，可以 结束算法

Insertion Sort

插入排序：利用减一技术对数组$A[0..n-1]$进行排序

算法

• 假设对较小数组$A[0..i-2]$排序已经解决
• 从右至左（方便将将元素右移）扫描有序子数组，直到遇到首个 小于等于$A[i-1]$元素，将$A[i-1]$插入其后

1
2
3
4
5
6
7
8
9
10
11
12

InsertionSort(A[0..n-1])
	// 用插入排序对给定数组排序
	// 输入：n个可排序元素构成数组
	// 输出：非降序排序数组
	for i = 1 to n-1 do
		v = A[i]
		j = i - 1
		while j >= 0 and A[j] > v do
			A[j+1] = A[j]
			j = j - 1
		A[j+1] = v
		// 上一步比较元素已经赋值给其后，所以应该覆盖其值

特点

• 插入排序是自顶向下基于递归思想，但是自底向上使用迭代实现 算法效率更高

• 算法时间效率

  • 算法基本操作是键值比较，比较次数依赖于特定输入
  • 最坏情况（递减数组）下：每轮比较次数都到达最大，此时 键值比较次数$\in \Theta(n^2)$
  • 最优情况（递增数组）下：每轮比较次数仅为1，此时键值 比较次数$\in \Theta(n)$
  • 对随机序列：比较次数$\in \Theta(n^2)$
  • 许多应用中都会遇到基本有序的文件，插入排序能保证良好 性能

• 减常量法

Shell Sort

插入排序的扩展，Shell排序基于h有序

H有序

数组中任意间隔为h的元素都是有序的，对应的数组称为h有序数组

• h有序数组：就是h个互相独立的有序数组编织在一起数组
• h有序数组具有分离、局部有序的特点

算法

• 使用插入排序对h子数组独立排序，每次交换相隔h的元素
• h逐渐减小到1，shell排序退化（最后一轮）为插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

ShellSort(A[0..n-1])
	// 用插入排序对给定数组排序
	// 输入：n个可排序元素构成数组
	// 输出：非降序排序数组
	h = 1
	while h < n/3
		h = h*3 + 1
		// 获取初始h值，之后每轮h变为1/3
	while h >= 1:
		for i = h to n-1:
			v = A[i]
			j = i - h
			while j >= 0 and A[j] > v do
				A[j] = A[j-h]
				j = j - h
			A[j+h] = v
		h = h/3

特点

• Shell排序全衡量子数组规模、有序性，更加高效

• h递增序列

  • 子数组部分有序程度取决于h递增序列的选择
  • 不同的h递增序列对算法效率有常数倍的变动，但是在实际 应用中效果不明显

• Shell排序是唯一无法准确描述其对于乱序数组性能特征的排序 方法

• 减常量法

归并排序

Mergesort

• 将需要排序的数组A[0..n-1]均分的
• 对两个子数组递归排序，然后把排序后的子数组合并为有序 数组

1
2
3
4
5
6
7
8
9
10

Mergesort(A[0..n-1]):
	// 递归调用MergeSort对数组排序
	// 输入：可排序数组A[0..n-1]
	// 输出：非降序排列数组A[0..n-1]
	if n > 1:
		copy A[0..floor(n/2)-1] to B[0..floor(n/2)-1]
		copy A[floor(n/2)..n-1] to C[0..ceiling(n/2)-1]
		Mergesort(B[0..floor(n/2)-1])
		Mergesort(C[0..ceiling(n/2)-11])
		Merge(B, C, A)

Merge

• 初始两只指针指向待合并数组首个元素
• 比较两个元素大小，将较小元素添加到新数组中，被复制元素 的数组指针右移
• 重复直到某一数组处理完毕，将未处理完数组复制到新数组尾部

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Merge(B[0..p-1], C[0..q-1], A[0..p+q-1]):
	// 将两个有序数组合并为新的有序数组
	// 输入：有序数组B[0..p-1]、C[0..q-1]
	// 输出：存放有B、C中元素的有序数组A[0..p+q-1]
	while i < p and j < q:
		if B[i] <= C[j]
			A[k] = B[i]
			i = i + 1
		else:
			A[k] = C[j]
			j = j + 1
		k = k + 1
	if i == p:
		copy C[j..q-1] to A[k..p+q-1]
	else:
		copy B[i..p-1] to A[k..p+q-1]

特点

• 算法时间效率

  • 最坏情况下比较次数$\in \Theta(nlogn)$，为 $nlog_2n-n+1$，十分接近基于比较的排序算法理论上能够 达到的最少次数

• 相较于快排、堆排序

  • 合并排序比较稳定，缺点在于需要线性额外空间
  • 虽然能做到在位，但是算法过于复杂，只具有理论上意义

• 算法可以自底向上合并数组的元素对，再合并有序对

  • 这可以避免使用堆栈递归调用时时空开销

• 可以把数组划分为待排序的多个部分，再对其递归排序，最后 合并在一起

  • 这尤其适合对存在二级存储空间的文件进行排序
  • 也称为Multiway Mergesort

• 分治算法

快速排序

相较于合并排序按照元素在数组中的位置进行划分，快速排序按照 元素值对其进行划分

Quicksort

• 对数组中元素重新排列，使得A[s]左边元素均小于A[s]，A[s] 右边元素都大于等于A[s]
  • 此时A[s]已经位于它在有序数组中的最终位置
• 接下来对A[s]左右子数组进行排序

1
2
3
4
5
6
7
8

Quicksort(A[l..]r)
	// 对给定可比较数组进行排序
	// 输入：可比较数组A[0..n-1]子数组A[l..r]
	// 输出：非降序排序的子数组A[l..r]
	if l<r
		s = partition(A[l..r])
		Quicksort(A[l..s-1])
		Quicksort(A[s+1..r])

特点

• 需要选择合适的划分算法J

  • LomutoPartition
  • HoarePartition

• 算法效率

  • 最优情况：分裂点都位于数组中点，算法比较次数为 $nlog_2n$
  • 最差情况：分裂点都趋于极端（逆序输入），算法比较 次数$\in \Theta(n^2)$
  • 平均：比较次数为$2nlnn \approx 1.39nlog_2n$
  • 且算法内层循环效率非常高，在处理随机排列数组时，速度 比合并排序快

• 快速排序缺点

  • 不稳定
  • 需要堆栈存储未被排序的子数组参数，尽管可以先对较短 子数组排序使得堆栈大小降低到$O(logn)$，但是还是比 堆排序的$O(1)$差
  • 仍然存在最差情况出现的可能性，即使有很多巧妙地中轴 选择办法
  • 对随机数组排序性能的好坏，不仅与算法具体实现有关， 还和计算机系统结构、数据类型有关

• 分治算法

算法改良

• 更好的中轴选择方法

  • randomized quicksort：随机快速排序，使用随机元素作为 中轴
  • median-of-three method：三平均划分法，以数组最左边、 最右边、最中间的中位数作为中轴

• 子数组足够小时（5~15），改用插入排序；或者直接不对小数组 排序，而是在快速排序结束后使用插入排序对整个近似有序的 数组进行排序

• 改进划分方法

  • 三路划分：将数组划分为3段，小于、等于、大于中轴元素

比较计数排序

算法

• 遍历待排序列表中每个元素
• 计算、记录列表中小于该元素的元素个数
• 更新大于其的元素的小于元素的元素个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14

ComparisonCountingSort(A[0..n-1])
	// 用比较计数法排序
	// 输入：可排序数组A[0..n-1]
	// 输出：将A中可排序数组按照升序排列数组
	for i = 0 to n-1 do
		count[i] = 0
	for i = 0 to n-2 do
		for j = i+1 to n-1 do
			if A[i] < A[j]
				count[j] += 1
			else
				count[i] += 1
	for i = 0 to n-1 do
		S[count[i]] = A[i]

特点

• 算法效率

  • 算法比较次数为$n(n-1)/2$
  • 占用了线性数量的额外空间

• 算法使得键值的可能移动次数最小化，能够直接将键值放在在 有序数组最终位置

• 输入增强

分布计数排序

• 待排序元素来自于某个已知小集合$[l..u]$

算法

• 扫描列表，计算、存储列表中元素出现频率于数组$F[l..u]$中
• 再次扫描列表，根据值填入相应位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

DistributionCountingSort(A[0..n-1], l, u):
	// 分布计数法排序，对元素来自有限范围整数的数组排序
	// 输入：数组[0..n-1]，数组中整数位于l、u间
	// 输出：A中元素构成非降序数组S[0..n-1]
	for j = 0 to u-l do
		D[j] = 0
	for i = 0 to n=1 do
		D[A[i]-l] += 1
	for j = 1 to u-l do
		D[j] += D[j-1]
		// 存储各元素最后出现索引+1
	for i = n-1 downto 0 do
		j = A[i] - l
		S[D[j]-1] = A[i]
		D[j] -= 1
		// 更新应该存储的位置，类似于压栈
	return S

特点

• 算法效率

  • 如果元素值范围固定，效率为线性（不是基于比较的排序， $nlogn$没有限制）
  • 用空间换时间，其实可以看作是hash
  • 利用了输入列表独特自然属性

• 变治法（输入增强）

应用

• 判断线性表元素是否唯一
• 寻找线性表众数
• 快速查找

线性表顺序统计量

寻找列表中第k小的元素

• 也即：求出给定列表中k个最小元素问题

• 采用partitioning的思路，需要将给定列表根据某个值先行划分

  • Lumuto划分算法

QuickSelect算法

算法

• 对划分完后出数组，s为分割位置
  • 若：s == k-1，则中轴p就是第k小元素
  • 若：s < k-1，则应该是数组右边划分第k-s小元素
  • 若：s > k-1，则应该是数组左边划分第k小元素
• 这样就得到规模更小的问题实例

1
2
3
4
5
6
7
8
9
10
11

QuickSelect(A[l..r], k)
	// 用基于划分递归算法解决选择问题
	// 输入：可排序数组A[0..n-1]的子数组A[l..r]、整数k
	// 输出：A[l..r]中第k小元素
	s = Partition(A[l..r])
	if s = l+k-1
		return A[s]
	elif s > l+k-1
		QuickSelect(A[l..s-1], k)
	else
		QuickSelect(A[s+1..r], l+k-1-s)

特点

• 时间效率：和划分算法有关（对Lomuto算法）

  • 最好情况下只需要划分一次即找到，需要比较$n-1$次
  • 最坏情况下需要比较$n(n-1)/2$次，这比直接基于排序更差
  • 数学分析表明，基于划分的算法平均情况下效率是线性的

• 已经找到复杂算法替代Lomuto算法用于在快速选择中选出 中轴，在最坏情况下仍保持线性时间效率

• QuickSelect算法可以不用递归实现，且非递归版本中甚至 不需要调整参数k值，只需要最后s == k-1即可

• 减可变规模：Lomuto算法性质

线性表有序划分

LomutoPartition

算法

• 考虑子数组A[l..r]分为三段，按顺序排在中轴p之后

  • 小于p的元素，最后元素索引记为s
  • 大于等于p的元素，最后元素索引记为i
  • 未同p比较过元素

• 从左至右扫描A[l..r]，比较其中元素和p大小

  • 若A[i] >= p，扩大大于等于p元素段
  • 若A[i] < p，需要扩大小于等于p元素段

1
2
3
4
5
6
7
8
9
10
11
12

LomutoPartition(A[l..r])
	// 采用Lomuto算法，用首个元素作中轴划分数组
	// 输入：可排序数组A[0..n-1]的子数组A[l..r]
	// 输出：A[l..r]的划分、中轴位置
	p = A[l]
	s = l
	for i = l+1 to r
		if A[i] < p
			s = s+1
			swap(A[s], A[i])
	swap(A[l], A[s])
	return s

HoarePartition

算法

• 选择一个元素p作为中轴（最简单的，首个元素p=A[l]）

• 从数组A[l..r]两端进行扫描，将扫描到的元素同中轴比较

  • 从左至右的扫描忽略小于中轴元素，直到遇到大于等于中轴 元素停止（从第二个元素开始i=l+1）
  • 从右至左的扫描忽略大于中轴元素，直到遇到小于等于中轴 元素停止(j=r-1)

• 若扫描停止后

  • 两指针不相交i < j，交换A[i]、A[j]，i=i+1、j=j-1， 继续扫描
  • 若指针相交i > j，把中轴和A[j]交换即得到数组一个划分 ，分裂点为s=j
  • 如果指针重合i==j，此元素一定等于p，也得到数组的一个 划分，分裂点为s==i==j

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

HoarePartition(A[l..r])
	// 以首元素为中轴，对数组进行划分
	// 输入：可排序数组A[1..n]的子数组A[l..r]
	// 输出：A[l..r]的一个划分，返回分裂点位置
	p = A[l]
	i = l
	j = r+1
	repeat
		repeat i = i+1 until A[i] >= p
			// 这里i有可能越界，可以添加一个限位器
		repeat j = j-1 until j[i] <= p
			// 从左右两端都是遇到等于p的元素就停止扫描
			// 这样可以保证即使数组中有许多和p相等的元素
			// 也能够将数组划分得比较均匀
		swap(A[i], A[j])
			// 这样写没有关系，不需要在这里给调整i、j
			// 因为循环下一步就是调整i、j
	until i >= j
	swap(A[i], A[j])
		// 撤销算法最后一次交换
	swap(A[l], A[j])
	return j

三路划分

算法

总述

• 图的遍历算法：如何一次访问到网络中所有节点
• 最短路线算法：两个城市间最佳路线
• 有向图拓扑排序：课程、预备课程是否有矛盾
• All-Pairs Shortest-Paths Problem：完全最短路径问题，找到 每个顶点到其他所有顶点的距离

遍历算法

Depth-First Search

深度优先查找（DFS）

算法

• 从任意顶点开始访问图顶点，然后标记为已访问

• 每次迭代时，紧接着处理与当前顶点邻接的未访问顶点， 直到遇到终点，该顶点所有邻接顶点均已访问过

• 在终点上，算法沿着来路后退一条边，继续从那里访问未 访问顶点

• 后退到起始点，且起始点也是终点时，算法停止，这样 起始点所在的连通分量的所有顶点均已访问过

• 若存在未访问顶点，则必须从其中任一顶点开始重复上述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

count = 0
	// 全局变量：访问次序（次数）
DFS(G)
	// 对给定图的深度优先查找遍历
	// 输入：图G=<V, E>
	// 输出：图G顶点按照DFS遍历第一次访问到的先后次序，
	//       未访问到标记未0
	for each vertex v in V do
		if v is marked with 0
			dfs(v)
dfs(v)
	// 递归访问所有和v相连接的未访问顶点，赋予count值
	count = count+1
	mark v with count
	for each vertex w in V adjecnt to v do
		if w is marked with 0
			dfs(w)

特点

• 算法效率非常高效，消耗时间和表示图的数据结构规模成正比

  • 邻接矩阵：遍历时间效率$\in \Theta(|V|^2)$
  • 邻接链表：遍历时间效率$\in \Theta(|V|+|E|)$

• 可以方便地用栈跟踪深度优先查找

  • 首次访问顶点，将顶点入栈
  • 当顶点成为终点时，将其出栈
  • 运行时就是实际上就是栈，所以深度优先可以直接利用递归 实现

• Depth-First Search Foreat：参见 algorithm/data_structure/graph

• DFS产生两种节点排列顺序性质不同，有不同应用

  • 入栈（首次访问顶点）次序
  • 出栈（顶点成为终点）次序

应用

• 检查图连通性：算法第一次停止后，是否所有顶点已经访问
• 检查图无环性：DFS是否包含回边
• 拓扑排序：见键值法
  • DFS节点出栈逆序就是拓扑排序的一个解（图中无回边， 即为有向无环图）
  • DAG中顶点v出栈前，不存在顶点u拥有到v的边，否则存在 回边，图不是DAG

Broad-First Search

广度优先查找（BFS）

算法

• 首先访问所有和初始顶点邻接的顶点

• 然后是离它两条边的所有未访问顶点

• 以此类推，直到所有与初始顶点在同一连通分类顶点均已访问

• 若存在未访问顶点，从图其他连通分量任意顶点开始

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

count = 0
	// 全局变量：访问次序（次数）
BFS(G)
	// 给定图广度优先查找变量
	// 输入：图G=<V, E>
	// 输出：图G的顶点按照被BFS遍历第一次访问到次序，
	//       未访问顶点标记未0
	for each vertax v in V do
		if v is marked with 0
			bfs(v)
bfs(v)
	// 访问所有和v相连接的顶点，赋count值
	count = count+1
	whilte queue is not empty do
		for each vertex w in V adjcent to the front vertex do
			if w is marked with 0
				count = count+1
				mark w with count
				add w to the queue
		remove the front vertex from the queue

特点

• 算法效率同DFS

  • 邻接矩阵：遍历时间效率$\in \Theta(|V|^2)$
  • 邻接链表：遍历时间效率$\in \Theta(|V|+|E|)$

• 使用队列可以方便地跟踪广度优先查找操作

  • 从遍历初始顶点开始，标记、入队
  • 每次迭代时，算法查找所有和队头顶点邻接未访问，标记 、入队、将队头顶点出队

• Breadth-First Search Forest：参见 algorithm/data_struture/graph

• BFS只产生顶点的一种排序，因为队列时FIFO结构，顶点入队、 出队次序相同

应用

• 和DFS一样可以检查图的连通性、无环性，但是无法用于比较 复杂的应用

• 求给定两个顶点间最短路径：从一顶点开始BFS遍历，访问到 另一节点结束（难以证明？）

有向图强连通分量

Kosaraju算法

考虑有向图中强连通分量之间不连通的情况

• 强连通分量之间没有边

  • 在任意连通分量中任意结点开始深度优先遍历

  • 访问完所有结点需要DFS次数就是强连通分量数量，每轮 DFS访问的点就是强连通分量中的顶点

• 强连通分量之间只有单向边

  • 将强连通分量视为单个结点，则整个图可以视为一个 靠连通分量间单向边连接的有向无环图

  • 从最底层强连通分量中任选结点开始进行DFS，则此轮DFS 只能访问当前连通分量中结点

  • 逆序依次在各强连通分量中选择结点进行DFS，则每轮DFS只 访问当前连通分量中结点（其下层连通分量已访问）

  • 直至所有结点访问完毕，则得到所有强连通分量，即每轮 进行DFS访问的结点

  • 以下图为例，从图中连通分量B中任意结点开始进行DFS， 则经过两轮DFS即能找所有强连通分量

    

由以上分析

• 只需要保证底层强连通分量进行DFS优先搜索

• 也即在结点搜索优先级中，底层强连通分量中至少有一个结点 在其上层连通分量所有结点之前

• 可以利用原图的反向的DFS逆后序排列得到满足条件 的结点优先级序列

  

  • 若从反向图中最底层强连通分量某结点开始，则只能遍历 自身，反向图中其余连通分量位于其所有结点之前

  • 若从反向图中非最底层强连通分量某结点开始，则能依次 遍历其底层所有强连通分量中结点，且至少该结点位于其余 连通分量所有结点之前

• 逆后序排列参见algorithm/data_structure/graph

算法

• 对原图G每条路径求反，得到反向图$G^R$
• 对反向图$G^R$求解逆后序序列
• 按照逆序序列优先级，对原图G进行DFS，每棵DFS生成树就是 一个强连通分量

特点

• 算法效率
  • 时间效率$\in O(|V| + |E|)$
  • 算法需要对图进行两次DFS，速度较Tanjar算法更慢

Tarjan算法

Tarjan算法：基于图深度优先搜索的算法

• 为每个结点维护两个标记，通过此标记确定是否存在回路

  • DFN：深度优先搜索中搜索到次序
  • Low：通过回边能访问到的前驱被搜索到的次序

  • 还可以维护一个Flag，判断结点是否仍在DFS栈中

• 对图进行深度优先搜索

  • 未处理结点入栈，设置其DFN、Low被搜索到的次序

  • 对已处理结点，考虑到深度优先的搜索、退栈方式

    • 仍然在栈中，则肯定是栈顶元素前驱，连接边为回边， 存在栈顶节点到该前驱结点的回路

    • 不在栈中，该节点不是祖先结点，连接边为交叉边， 该结点已经在其他连通分量中出栈

  • 使用栈中前驱结点Low/DFN次序更新当前（栈顶）结点， 并递归更新，即使用子节点访问先驱次序更新父节点

• DFS回溯、退栈，考虑栈中每个结点DFN、Low

  • 若DFN[u] > Low[u]：结点u和其前驱之间有回路， 即其属于同一个强连通分量

  • 若DFN[u] == Low[u]：结点u和其前驱之间没有通路， 没有更多结点属于其所属强连通分量，以结点u为根子树 是一个强连通分量

    • 则从栈顶元素开始退栈直至结点u退栈，退栈的所有 元素构成强连通分量

• 每个强连通分量为深度优先搜索树中一个子树

• $w, (w, v) \in E$：顶点v的直接前驱
• $k, (v, k) \in E$：顶点v的祖先（即栈中结点）

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

S = initStack()
DFN[MAX_VERTAX], Low[MAX_VERTEX]
index = 0
QList = InitList(Queue())

tarjan(u, E):
	// 比较DFS搜索次序、回边到达次序判断强连通分量
	// 输入：结点u，边集合E
	// 输出：强连通分量队列列表
	DFN[u] = Low[u] = ++ index
	S.push(u)
	for each (u, v) in E:
		if (v is not visited):
			tarjan(v)
			Low[u] = min(Low[u], Low[v])
			// 使用v找到的前驱更新u能找到前驱，递归更新
		else if (v in S):
			// 判断边是否为回边
			Low[u] = min(Low[u], DFN[v])
			// Low[u] = min(Low[u], Low[v])
				// 应该也行
	if(DFN[u] == Low[u]):
		Q = QList.next()
		repeat
			v = S.pop()
			Q.push(v)
		until (u == v)

特点

• 算法效率
  • 时间效率$\in O(|V|+|E|)$

关节点

类Tarjan算法

• 类似Tarjan算法为每个节点维护DFN、Low两个次序
  • 对非根结点v，存在其直接后继w有Low[w] >= DFN[v] ，则v为关节点
  • 对根节点，有两棵以上子树则为关节点

算法

此算法具体实现和Tarjan算法细节有差异

• 此算法中不需要使用栈保存访问过顶点中是前驱者
  • 连通无向图DFS只会有回边，已访问点必然是前驱结点
• 需要对根结点额外判断是否为关节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

DFN[MAX_VERTAX], Low[MAX_VERTEX]
index = 0
Q = InitQueue()

FindArticul(G):
	// 输入：无向连通图G
	// 输出：关节点队列
	vroot = G.V.pop()
	TarjanArticul(vroot, G)
	for(v in G.V if v not visited)
		// 根节点有两棵及以上子树
		TarjanAricul(vroot, G)
		Q.push(vroot)
		// 根节点也是关节点
	return Q

TarjanArticul(u, G):
	// 比较DFS搜索次序、回边到达次序判断关节点
	// 输入：结点u，无向连通图G
	// 输出：关节点队列
	DFN[u] = Low[u] = ++ index
	for each (u, v) in G.E:
		if (v is not visited):
			tarjan(v)
			Low[u] = min(Low[u], Low[v])
			// 使用v找到的前驱更新u能找到前驱，递归更新
		else:
			Low[u] = min(Low[u], DFN[v])
			// Low[u] = min(Low[u], Low[v])
				// 应该也行
	for(v connected by u)
		if(Low[v] <= DFN[u])
			Q.push(u)
	return Q

无权路径

路径数量

图中顶点i到顶点j之间长度为k的不同路径数量为$A^k[i, j]$

• A为图的邻接矩阵
• 可以使用数学归纳法证明
• 对无向、有向图均适用

Warshall算法

Warshall算法：生成有向图传递闭包

• 构造n+1个n阶布尔矩阵$R^{(k)}, k=0,1,\cdots, n$

  • $R^{(k)}_{ij}=1$：顶点i、j直接存在中间顶点编号 不大于k的有效路径

  • $R^{(0)}$：邻接矩阵，顶点直接连接

  • $R^{(k)}, 0<k<n$：路径中间顶点编号最大为k

  • $R^{(n)}$：传递闭包，允许所有类型路径

  • 后继矩阵相对前趋，允许作为路径上顶点增加，可能包含 1数量更多

• 考虑$R^{(k)}$通过直接前趋$R^{(k-1)}$计算得到

  • $R^{(k-1)}$中已有路径在$R^{(k)}$保留

  • 考虑$R^{(k)}$相较于$R^{(k-1)}$新增$r_{ij}=1$

    • 表示顶点i、j之间存在包含k的路径

    • 若k在路径中出现多次，则将删除回路，得到新路径

    • 则存在ik和kj之间路径满足中间顶点编号小于k，即在 $R^{(k-1)}$中有$r{ik}=1, r{kj}=1$

算法

• 若元素$r_{ij}$在$R^{(k-1)}$中为1，则在$R^{(k)}$也是1

• 若元素$r{ij}$在$R^{(k-1)}$中为0，当且仅当存在v使得 $R^{(k-1)}$中$r{iv}=1, r_{vj}=1$

1
2
3
4
5
6
7
8
9
10
11
12

Warshall(A[1..n, 1..n])
	// 计算传递闭包的Warshall算法
	// 输入：A[1..n, 1..n]包含n个顶点的有向图的邻接矩阵
	// 输出：A的传递闭包
	R^0 = A
	for i = 1 to n do
		for i = 1 to n do
			for j = 1 to n do
				if R^(k-1)[i, j] == 1 or
					(R^(k-1)[i, k] == 0 and R^(k-1)[k, j] == 0)
					R^k[i, j] = 1
	return R^n

算法特点

• 算法效率

  • 时间效率$\in \Theta(n^3)$
    • 重新构造最内层循环，可以提高对某些输入的处理速度
    • 将矩阵行视为位串，使用或运算也可以加速
  • 空间效率取决于如何处理布尔矩阵

• 蛮力法：所有点分别作为起点作一次搜索，记录能够访问的顶点

  • 对有向图遍历多次
  • 使用邻接链表表示稀疏图，蛮力法渐进效率好于Warshall算法

最小生成树

Prim算法

Prim算法：求解最小图最小生成树算法

• 每次添加距离当前树距离最近顶点进树
• 不断迭代构造最小生成树

算法

• 从图顶点集V中任选单顶点作为序列中初始子树

• 对图中顶点维护两个标记：树中最近顶点、相应距离

  • 与树不直接相连顶点置：NULL、$\infty$
  • 每次添加新节点更新两个标记
  • 可使用优先队列维护提高效率

• 以贪婪的方式扩张当前生成树，添加不在树中的最近顶点

• 更新顶点和树距离最近的顶点、相应距离

  • 只需考察与新添加顶点直接相连顶点即可

• 不断迭代直到所有点都在树中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

Prim(G):
	// 构造最小生成树Prim算法
	// 输入：加权连通图G=<V, E>
	// 输出：E_T, 组成G最小生成树的边集合
	V_T = {v_0}
		// 使用任意顶点初始化树顶点集合
	E_T = NULL
		// 初始化生成树边为空集

	for i = 1 to |V|
		if i connect V_T
			connect_V[i] = 0
			connect_D[i] = e(0, i)
		else
			connect_V[i] = NULL
			connect_D[i] = \infty
	// 初始化节点和树最近节点列表、节点与树距离列表

	for i = 1 to |V|-1 do
		// 重复n-1次，直到树包含所有顶点
		edge = min(connect_D)
			// 寻找距离树最近的点
		v = vertex(edge)

		V_T = V_T union {v}
		E_T = E_T union {edge}

		connect_V[v] = NULL
		connect_D[v] = \infty
		更新和v相连的顶点两个标记值
	return E_T

算法特点

• 算法时间效率依赖实现优先队列、存储图数据结构

  • 图权重矩阵、优先队列无序数组$\in \Theta(|V|^2)$
  • 图邻接链表、二叉最小堆$\in O(|E|log|V|)$
  • 图邻接链表、Fibonacci Heap $\in O(|E| + |V|log|V|)$

• 对树进行扩展时用到的边的集合表示算法生成树

• 穷举查找构造生成树，生成树数量呈指数增长，且构造生成树 不容易

Kruskal算法

Kruskal算法：把最小生成树看作是具有$|V|-1$条边、且边权重最小 的无环子图，通过对子图不断扩展构造最小生成树

算法

• 按照权重非递减顺序对图中边排序

• 从空子图开始扫描有序列表，试图把列表中下条边加到当前子图 中，如果添加边导致回路则跳过

• 不断添加边直到达到$|V|-1$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Kruskal(G)
	// 构造最小生成树的Kruskal算法
	// 输入：G=<V, E>加权连通图
	// 输出：E_T，组成G的最小生成树边集
	reverse_sort([w(e_i)])
		// 按照边权非递减顺序对边集排序
	E_T = NULL
	ecounter = 0
	k = 0
	while ecounter < |V|-1 do
		k += 1
		if E_T union {e_k} 无回路
			// 常用并查算法检查`e_k`连接的两个顶点是否在
			// 同一棵树（并查集）中
			E_T = E_T union {e_k}
			ecounter += 1
	return  E_T

算法特点

• Kruskal每次迭代都需要检查添加新边是否会导致回路，其实 效率不一定比Prim算法高

• Kruskal算法中间阶段会生成一系列无环子图（树）

  • 子图不总是联通的
  • 可以看作是对包含给定图所有顶点、部分边的森林所作的 连续动作
  • 初始森林由|V|棵普通树构成，包含单独顶点
  • 最终森林为单棵树，包含图中所有顶点
  • 每次迭代从图的边有序列表中取出下条边，找到包含其端点 的树，若不是同一棵树，则加入边生成一棵更大的树

• 算法效率

  • 如果检查顶点是否位于同一棵树算法高效，则算法运行时间 取决于排序算法，时间效率$\in O(|E|log|E|)$

Sollin算法

Sollin算法：Prim算法、Kruskal算法的结合，将图每个顶点视为 子树，每次添加多条边合并子树直至得到最小生成树

算法

• 将图中每个顶点视为一棵树，整个图表示森林$F^{(0)}$
• 为森林$F$中每棵树选择最小代价边合并两棵树
• 重复以上，直至所有树合并为一棵树

1
2
3
4
5
6
7
8
9
10
11
12

Sollin(G):
	// 无向图最小生成树Sollin算法
	// 输入：无向图G
	// 输出：最小生成树边集
	MST_E = NULL
	Forest = G.V
	while |MST_E| < |G.V|:
		for tree in Forest:
			e = find_min(G.E)
			tree_b = get_tree(e)
			MET_E.add(e)
			tree.union(tree_b)

todo

算法特点

• 算法效率
  • 每轮子树数量减少一半，则最多重复log|V|轮算法终止
  • 时间效率$\in O(|E|log|V|)$

最短路径

Dijkstra算法

Dijkstra算法：求解单起点、权值非负最短路径算法

• 按照从给定起点到图中各顶点的距离，顺序求出离起始点 最近的顶点、相应最短路径

• 第i次迭代前，算法已经确定了i-1条连接起点、离起点前i-1近 顶点的最短路径

  • 这些构成了给定图的一棵子树$T_i$
  • 可以在同$T_i$顶点邻接的顶点中找到和起点最接近的顶点 （边权非负）

• 算法类似于Prim算法，两个对代价评价标准不同

  • Dijkstra算法是各条路径长度：有重复边，考虑整个路径
  • Prim算法是评价各边总和：无重复边，只考虑一条边

算法

• 对顶点维护两个标记：起点到该顶点最短路径长度d、路径上 前个顶点pre_v

  • 一般使用优先队列维护最短路径长度
  • 对所有顶点维护：$\infty$、NULL标记不在树中、不与树 邻接顶点
  • 仅对生成树中顶点、邻接顶点维护：每次迭代更新列表

• 根据标记选择邻接顶点中和起始点距离d最小顶点，添加进树

• 更新顶点标记

  • 因为生成树只新添加一个顶点，只需要考虑与新添加顶点 直接相连、未在树中顶点
  • 比较与起始点距离是否改变

• 不断迭代直至所有点均在树中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

Dijkstra(G, s)
	// 单起点最短路径Dijkstra算法
	// 输入：G=<V, E>非负权重加权连通图，顶点s起始点
	// 输出：对V中每个顶点，从s到v的最短路径长度d_v
	Initialize(Q)
		// 将顶点优先队列初始化为空
	for v in V
		d_v = \infty
		p_v = NULL
		Insert(Q, s, d_s)
			// 初始化有限队列中顶点优先级
	d_s = 0
	Decrease(Q, s, d_s)
		// 更新s优先级为d_s
	V_T = NULL

	for i = 0 to |V|-1 do
		u* = DeleteMin(Q)
			// 删除优先级最小元素
		V_T = V_T \union {u*}
		for v in V-V_T 中与u*邻接顶点 do
			if d_u* + w(u*, u) < d_u
				d_u = d_u* + w(u*, u)
				p_u = u*
				Decrease(Q, u, d_u)

算法特点

• 算法时间效率同Prim算法

Bellman-Ford算法

Bellman-Ford算法：求解单节点、权值正负无限制最短距离

• 权值正负无限制意味着贪心策略不再有效
• 要求路径中不存在负权值回路
• 对n个顶点图，路径最长为n-1，否则删除回路路径长度不增加

算法

考虑使用动态规划算法

• 令$dist^{(l)}[u]$表示从起点v到节点u边数不超过l的最短 路径长度

  • 在不允许出现负权值回路的前提下，构造最短路算法过程 最多只需要考虑n-1条边

  • 即$dist^{(n-1)}$是从v到u不限制路径中边数目的最短路径 长度

Floyd算法

Floyd算法：求解完全最短路径问题，有向、无向、加权图均适用 （边距离不为负，否则距离可以任意小）

• 构造n+1个距离矩阵$D^{(k)}, k=0,1,\cdots,n$

  • $D^{(k)}$中元素$d_{ij}$表示顶点i、j之间由编号小于k的 顶点作为中间顶点的距离

  • $D^{(0)}$：初始权重矩阵

  • $D^{(k)}, 0<i<n$：路径中顶点编号最大为k

  • $D^{(n)}$：目标距离矩阵

  • 后继矩阵相对前趋，允许作为路径上顶点增加，各顶点间 距离可能缩短

• 考虑$D^{(k)}$通过直接前趋$D^{(k-1)}$计算得到，其中距离 （路径）分为两类

  • $d^{(k)}{ij} = d^{(k-1)}{ij}$：不包含顶点k作为中间 节点的路径

  • $d^{(k)}{ij} = d^{(k-1)}{ik} + d^{(k-1)}{kj} < d^{(k-1)}{ij}$： 包含顶点k作为中间节点的路径

算法

1
2
3
4
5
6
7
8
9
10

Floyd(W[1..n, 1..n])
	// 计算完全最短路径的Floyd算法
	// 输入：W不包含负距离的距离矩阵
	// 输出：包含最短距离的距离矩阵
	D^0 = W
	for k = 1 to n do
		for i = 1 to n do
			for j = 1 to n do
				D[i, j] = min(D[i, j], D[i, k] + D[k, j])
	return D

算法特点

• 算法效率

  • 时间效率同Warshall算法为立方级
  • 如上伪码的空间效率为平方级（没有创建n+1距离矩阵）

• Floyd算法类似于Warshall算法

• Floyd算法利用最优性原理，即最短路径中子路径也是最短

最大流量问题

Augmenting-Path Method

Shortest-Augmented-Path算法

最短增益路径法（first-labeled first-scanned algorithm）

• 对网络中顶点维护两个标记

  • 从源点到被标记顶点能增加流量数
  • 路径中前个顶点名称
    • +：从前向边访问到当前顶点
    • -：从后向边访问到当前顶点

• 对网络的每条边$(i, j)$，初始化流量为$x_{ij}=0$

• 从源点开始同时沿着前向边、后向边进行广度优先搜索

  • 先更新前向边
  • 只有有增益空间边（顶点）才能被访问
  • 更新搜索到顶点标记

• 源点被标记表明得到一条增量路径，沿着标记反向更新边流量

• 若广度优先搜索无法达到源点，表明不存在流量增益路径，当前 流量值作为最大值返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

ShortestAugmentingPath(G)
	// 最短增量路径算法
	// 输入：流量网络G
	// 输出：最大流量x
	对网络中每条边，设置x[i, j] = 0
	把源点标记为(\infty, -)，加入空队列Q中
		// 使用队列实现广度优先搜索
	while not Empty(Q) do
		i = Front(Q)
		Dequeue(Q)
		for 从i到j的每条边 do
			// 遍历从i出发的边，前向边
			if j未被标记
				r[i, j] = = u[i, j] - x[i, j]
				if r[i, j] > 0
					l[j] = min{l[i], r[i, j]}
					/// 更新从源点到顶点j能增加的流量数
					用l[j], i+标记j
					Enqueue(Q, j)
		for 从j到i的每条边 do
			// 遍历到达i的边，后向边
			if j未被标记
				if x[j, i] > 0
					l[j] = min{l[i], x[j, i]}
					// 更新源点到顶点j能增加的流量数
					用l[j], i-标记j
					Enqueue(Q, j)
		if 汇点被标记
			// 沿着找的增益路径进行增益
			j = n
			while j != 1
				// 反向更新到源点为止
				if 顶点j前个节点为i+
					// 通过前向边访问到顶点j
					x[i, j] = x[i, j] + l[n]
				else
					x[j, i] -= l[n]
				j = i
		去除除源点外所有顶点标记
		重新初始化化队列Q

算法特点

• 算法正确性可以（联合）最大流-最小割定理证明

• 算法时间效率

  • 可以证明最短增益路径算法用到的增益路径数量不超过 $|V||E|/2$
  • 对使用邻接列表表示的网络，用广度优先查找找到一条增益 路径的时间$\int O(|V|+|E|)$
  • 所有算法时间效率$\in O(|V||E|^2)$

• 迭代算法

Preflow推进算法

预流：满足容量约束，但是不满足流量守恒约束

• 把过剩流量向汇点处移动，直到网络所有中间顶点都满足流量 守恒约束为止

算法特点

• 算法时间效率
  • 这类算法中较快者最差效率可以接近$O(|V||E|)$

Dinitz算法

Karzanov算法

Malhotra-Kamar-Maheshweari算法

Goldberg-Tarjan算法

单纯形法

此问题仍然是线性规划问题，可以使用单纯形法等通用解法求解

最大匹配（二分图）

匈牙利算法

算法

• 对U中每个顶点维护一个标记：与其匹配的对偶顶点

• 从V中的一个自由顶点v出发，按广度优先搜索找到U中自由 顶点u，寻找增益路径，搜索过程中

  • V中顶点：按照广度优先搜索，得到不在匹配M中的边

    • 搜索到U中自由顶点，则停止得到增益路径
    • 搜索到U中被标记顶点，则连接上已有匹配

  • U中顶点：直接找到其在V中的对偶顶点，得到在M中边

• 得到一个增益路径，沿着增益路径回溯，奇数边加入匹配

• 未找到自由顶点时，则无法得到增益路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

MaximumBipartiteMatching(G)
	// 用类似广度优先算法遍历求二分图的一个最大匹配
	// 输入：二分图G=<V, U, E>
	// 输出：输入图中一个最大基数匹配
	初始边集合M包含某些合法的匹配（例如空集合）
	初始队列Q包含V的所有自由顶点（任意序）
	while not Empty(Q) do
		w = Front(Q)
		Dequeue(Q)
		if w \in V
			for 邻接w的每个顶点u do
				// 二分图性质保证u一定在U中
				if u是自由顶点
					// 增益
					M = M \union (w, u)
						// 首边进匹配
					v = w
					while v已经被标记 do
						// 从增益路径回溯生成匹配
						u = 以v标记的点
						M -= (v, u)
							// 偶数边出匹配
						v = 以u标记的点
						M += (v, u)
							// 奇数边进匹配
					删除所以顶点标记
					用V中所有自由顶点重新初始化Q
					break
						// 增益后，重新搜索
				else
					// u已经匹配
					if (w, u) not \in M and u未标记
						用w标记u
						Enqueue(Q, u)
		else
			// w \in U，此时w必然已经匹配
			用w标记w的对偶v
				// 将已有匹配添加进增益路径中
			Enqueue(Q, v)
	return M
		// 当前匹配已经是最大匹配

算法特点

• 注意：从自由顶点开始寻求匹配时，无论是否找到增益路径， 路径中中U中节点标记已经更新，匹配仅在得到增益路径才更新

• 算法时间效率

  • 每次迭代花费时间$\in O(|E|+|V|)$，迭代次数 $\in O(|V|/2 + 1)$
  • 若每个顶点的信息（自由、匹配、对偶）能在常数时间内 得到（如存储在数组中）
  • 则算法时间效率$\in O(|V|(|V| + |E|))$

• 算法正确性参见图graph_undirected关于增益路径-最大匹配

• 迭代算法

霍普克罗夫-卡普算法

算法特点

• 对匈牙利算法的改进，把多次迭代在一个阶段完成，然后用一次 查找把最大数量边添加到匹配中

• 算法时间效率：$\in O(\sqrt {|V|}(|V| + |E|))$

稳定婚姻问题

婚姻稳定算法

存在自由男士，任选求婚、回应之一执行，直至不存在自由男士

• 求婚：自由男士m向女士w求婚，w为其优先级最大、之前未拒绝 过其女士（可以是已匹配）

• 回应：若女士w自由则接受男士m求婚，与之配对；女士w不自由 则把m同当前配偶匹配，选择其中优先级较高者

算法

算法特点

• 算法会在$n^2$次迭代内终止：至多每位男士向所有女士求婚

• 性别倾向：总是生成man-optimal的稳定匹配，优先满足 男士偏好

  • 在任何稳定婚姻中，总是尽可能把优先级最高的女士分配给 男性
  • 使用女士进行求婚也只会把性别偏见反向，而不能消除

• 对给定的参与者优先选择集合而言，男士（女士）最优匹配唯一

  • 由性别性别倾向容易证明
  • 所以算法的输出不取决于自由男士（女士）求婚顺序，可以 使用任何数据结构表示参与者集合而不影响结果

• 算法最终输出匹配M为稳定婚姻匹配证明参见graph

分配问题（二分图）

n个任务分配给n个人执行（一人一个），将任务j分配个人i的成本为 $C_{ijd}$，求最小成本分配方案

• 类似问题：最大权重匹配问题

蛮力算法

算法

• 生成整数n的全部排列
• 根据成本矩阵计算每个分配方案总成本
• 选择和最小的方案

特点

• 算法排列次数为$n!$

分支界限法

• 第i层节点下界可取：$lb = c + \sum_{k=i+1}^n min{c_k}$

  • $c$：当前成本
  • $min{c_k}$：成本矩阵第k行最小值

算法

特点

匈牙利算法

算法

特点

Topological Sorting

拓扑排序：按照次序列出有向图的顶点，使得对图中每条边，其 起始顶点总在结束顶点之前

删点法

算法

• 在有向图中求出源（没有输出边的顶点），然后把删除其和所有 从它出发的边
• 不断重复，直到不存在源，如果此时图中还有顶点，则图中存在 环，无解
• 则删除节点顺序即为拓扑排序可行解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

TopologicalSort(G):
	// 从有向图中不断删除入度为0的点、入栈，判断有向图G是否
		// 为DAG，并给出拓扑排序栈
	// 输入：有向图G
	// 输出：拓扑排序栈T
	InitStack(S)
	indgree = [v.indegree for v in G]
	for v in G:
		if v.indgree == 0
			S.push(v)
		// 存储0入度结点栈
	count = 0
		// 删除结点计数
	while(!S.empty())
		v = S.pop()
		T.push(v)
		count++
		for(u connected to v)
			if --indgree.u == 0
				S.push(u)
	if count < |G.V|
		// 结点未删除完毕，但无0入度结点
		// G中有回路，报错
		return ERROR
	return T

特点

• 算法效率
  • 时间效率$\in O(|V|+|E|)$
• 减常数法

DFS逆后序遍历

图中无环时，由某点出发进行DFS

• 最先退出DFS的为出度为0的点，即拓扑有序序列中最后顶点

• 按照DFS退出先后次序得到序列即为逆向拓扑有序序列

  • 使用逆后序方式存储DFS访问顶点，判断是否有环、出栈 次序即为正向拓扑有序序列

应用

• 判断庞大项目中相互关联任务不矛盾，然后才能合理安排，使得 项目整体完成时间最短（需要CPM、PERT算法支持）

Cirtical Path问题

找出使用AOE网表示的工程的中关键路径

• 关键路径由关键活动构成
• 即耗费时间变动对工程整体完成时间有影响的活动

拓扑排序求解

• 最早、最晚开始时间检查是否为关键活动
• 建立活动（边）、事件（顶点）发生事时间关系
• 拓扑排序求解事件发生最早、最晚时间

• 具体参见algorithm/data_structure/graphdi_specials

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

TopologicalOrder(G):
	// 从有向图中不断删除入度为0的点、入栈，判断有向图G是否
		// 为DAG，并给出拓扑排序栈
	// 输入：有向图G
	// 输出：拓扑排序栈T、顶点事件最早发生事件ve
	InitStack(S)
	indgree = [v.indegree for v in G]
	ve[0..|G.V|] = 0
	for v in G:
		if v.indgree == 0
			S.push(v)
		// 存储0入度结点栈
	count = 0
		// 删除结点计数
	while(!S.empty())
		v = S.pop()
		T.push(v)
		count++
		for(u connected by v)
			ve[u] = max{ve[u], ve[v] + len(v, u)}
				// 若有更长路径，更新
			if --indgree[u] == 0
				S.push(u)
	if count < |G.V|
		// 结点未删除完毕，但无0入度结点
		// G中有回路，报错
		return ERROR
	return T, ve

CriticalPath(G, T, ve):
	// 逆序求顶点事件最晚发生时间，求出关键活动
	// 输入：有向无环图G，G拓扑排序
	// 输出：关键活动队列Q
	vl[0..|G.V|] = ve
	Q = InitQueue()
	while(!T.empty())
		v = T.pop()
		for (u connect to v)
			vl[u] = min{vl[u], vl[v] - len(u, v)}
	for(v in G.V)
		for (u connected by v)
			ee = ve[v]
			el = vl[u] - len(v)
			if(el == ee)
				Q.push(G.edge(v, u))
	return Q

• 以上算法中在生成拓扑排序栈时同时得到各顶点事件最早发生 时间

• 可以只获取拓扑排序栈，然后处理其获得顶点事件最早发生时间 ，将两个功能分离，只是处理一遍顶点而已

• 也可以使用其他算法获得拓扑排序栈

  • DFS遍历甚至可以遍历顶点一遍，同时获得顶点事件最早、 最晚发生时间

特点

• 算法效率
  • 时间效率$\in O(|V|+|E|)$

哈密顿回路问题

确定给定图中是否在包含一条哈密顿回路

回溯算法

算法

• 对所有节点维护标记：是否位于当前路径中

• 选择某节点a作为哈密顿回路起点顶点，即回溯状态空间树根

• 从根节点开始处理

  • 若节点周围还有未标记节点，选择下个加入路径、标记
  • 若节点周围没有未标记节点，回溯到之前节点重新处理

• 直到所有节点都被标记，且当前节点和根节点相邻

特点

旅商问题

Traveling Salesman Problem：对相互之间距离已知为正整数的n座 城市，求最短漫游路径，使得在回到出发城市之前，对每个城市只 访问一次

• 即：对权重为正整数的无向完全图寻找最短哈密顿回路

蛮力算法

算法

• 生成n-1个中间城市的组合得到所有旅行线路
• 计算线路长度，求得最短路径

特点

• 算法排序次数为$(n-1)!/2$

改进

• 线路成对出现，只是方向相反，可考虑任意两个相邻顶点，只 考虑包含其某个排序的线路

分支界限法

• 第i层下界可取$lb = \sum{k=i+1}^n d{k1}$

• 更紧密、也不复杂的下界 $lb = \lceil \frac {\sum{k=i+1}^n (d{k1} + d_{k2})} 2 \rceil$

  • $d{k1}, d{k2}$：城市$i+1$到最近的两个城市距离

  • 最短路径为两个端点共享，至多只能有一个端点能够成为 该边起点

  • 若要求所有哈密顿回路中必须包括某些边，则在考虑相应 边端点城市时，使用必须边（若不是节点最短边）替换其中 次短边

• 只需要生成某对节点有序的路径：可以消去状态空间树中部分 分支

算法

特点

旅商问题非精确算法

以下均是讨论TSP问题的欧几里得实例，不对称实例等已经证明更难 解决，对精确算法、启发式算法都是如此

贪婪算法

Nearest-Neighbor算法

• 任意选择城市开始
• 每次访问和当前城市k最接近的城市，直到访问完所有城市
• 回到开始城市

Multifregment-Heuristic算法

求给定加权完全图的最小权重边集合，且每个顶点连通度均为2

• 将边按权重升序排列，将要构造的旅途边集合开始时空集合

• 不断尝试将排序列表中下条边加入旅途边集合

  • 边加入不会使得某节点连通度大于2
  • 不会产生长度小于n的回路
  • 否则忽略这条边

• 返回旅途集合

算法特点

对属于欧几里得类型的旅商问题实例（大部分）

• 此时虽然两个算法的精确性能比无法界定，但是满足 $\frac {f(s_a)} {f(s^{*})} \leqslant \frac 1 2 (\lceil log_2 n \rceil + 1)$

Minimum-Spaning-Tree-Based Algorithm

基于最小生成树的算法

• 哈密顿回路中去掉一条边就能得到一棵生成树$T_h$
• 可以先构造一棵最小生成数$T^{*}$，然后在其基础上构造近似 最短路径

Twice-Around-The-Tree算法

• 对给定实例构造最小生成树$T^{}$（Prim, Kruskal*）
• 从任意顶点开始，（利用深度优先遍历）绕树散步一周，记录 经过顶点
• 扫描顶点列表，消去重复出现顶点（走捷径，直接去新城市）， 除列表尾部重复起点，得到一条哈密顿回路

• 可能是考虑到最小生成树能够选出部分最短路径？？？

特点

对属于欧几里得类型的旅商问题

• 绕树两周算法是2近似算法：$2f(s^{*}) > f(s_a)$

  • $f(s^{} > w(T_h) \geqslant w(T^{})$：最优哈密顿 回路去掉一条边后长度大于等于最小生成树长度
  • $f(s^{}) < 2w(T^{})$：第二次扫描走捷径距离小于绕树 一周距离
  • 这里限定了特点类型实例，并没有找到对所有旅商问题的 优先近似算法

Christofides算法

同样利用问题与最小生成树的出关系，但更复杂

算法

• 对给定实例构造最小生成树$T^{*}$
• 构造包含包含$T^{*}$的欧拉回路
  • 找出最小生成树中所有连通度为奇数的顶点
  • 求出这些顶点的最小权重匹配（匈牙利算法）
  • 将最小权重匹配边加入树中得到多重图欧拉回路
• 使用走捷径方法将欧拉回路转换为哈密顿回路

特点

对属于欧几里得类型的旅商问题

• 绕最小生成树一周得到的路径是多重图的一条欧拉回路，其中 多重图为将当前图每条边重复一遍得到

  • 绕树两周算法：直接原始欧拉回路上走捷径
  • Christofides算法：重新构建更短的欧拉回路，在此基础 上走捷径

• Christofides算法是1.5近似算法

  • 实际应用中，Christofides算法近似解明显好于绕树两周
  • 可以对连通度大于2顶点尝试不同访问次序，即将回路 中邻接顶点分别两两组合，找到访问其的最佳路径

迭代改进算法

Local Search Heuristics：本地查找启发法

• 这类算法从某个初始旅途（随机或简单近似算法生成）开始

• 每次迭代把当前旅途一些边用其他边代替，试图得到和当前旅途 稍有差别的旅途

  • 若能得到优于当前旅途的新旅途，则替换当前旅途，继续 寻找
  • 否则，返回当前旅途，停止

2选算法

删除旅途中2条非临边，把两条边端点用另一对边重新连接

• 此操作称为2改变
• 为保证重连后得到合法哈密顿回路，重连方法只有一种

3选算法

删除3条非临边后重连

• 重连方法有3种
• 事实上可以推广到k选，但是只有3改变被证明有意义

Lin-Kernighan算法

变选算法算法的一种

• 可以视为在3选操作后进行一系列2选操作

算法特点

• 迭代改进算法求得的近似解效果质量非常好
• Lin-Kernighan算法是公认的求解高质量近似解的最佳算法

Held-Karp Bound

Held-Karp下界

• 将TSP描述为线性规划问题求解（忽略整数约束）得到，计算 速度快
• 一般和最优旅途长度非常接近，误差不超过1%
• 可使用其代替最短旅途估计近似算法的精确度

模拟

• 10000个随机点：坐标、距离取整
• Comqaq ES40：500MHz的Alpha处理器、2GB内存

总述

约瑟夫斯问题

n个人围成圈编号{0..n-1}，从1号开始每次消去第m个人直到最后一个 人，计算最后人编号$J(n)$。

减1法

考虑每次消去1人后剩余人的编号情况

• 还剩k人时，消去1人后，以下个人编号为0开始，将剩余人重新 编号，得到每个人在剩k-1人时的编号

• 相较于剩k人时，剩k-1人时每个人编号都减少m，即每个人在剩 k人时编号满足

  $$J_k = (J_{k-1} + m) \% k$$

• 考虑只剩1人时，其编号为0，则可以递推求解

算法

1
2
3
4
5
6
7

Joseph_1(n, m):
	// 减1法求解Joseph问题
	// 输入：人数n、消去间隔m
	// 输出：最后留下者编号
	j_n = 0
	for k from 2 to n:
		j_n = (j_n + m) % k

特点

• 算法效率
  • 时间效率$\in O(n)$

减常因子

剩余人数$k >= m$时考虑所有人都报数一次后剩余人的编号变化情况

• 还剩k人时，报数一圈后消去k//m人，以最后被消去人的下个人 编号为0开始，将剩余人重新编号，得到剩k-k/m人时的编号

• 相较于剩k人时，剩k-k//m人时每个人编号满足

  $$\begin{align*} J_k & = \left \{ \begin{array}{l} J_{k - d} + d * m, & J_{k - d} < n\%m \\ J_{k - d} // (m-1) * m + (J_{k - d} - n\%m) \% (m - 1), & J_{k - d} > n\%m \end{array} \right. \\ & = \left \{ \begin{array}{l} s + n, & s < 0 \\ s + s // (m-1), & s >= 0 \end{array} \right. \end{align*}$$

  • $d = k // m$
  • $s = J_{k - d} - n\%m$

• $k < m$时，使用减1法计算

  • m很大时，以$k < m$作为调用减1法很容易使得递归超出 最大值
  • 另外$m < k <= d * m$时，每轮也不过消去$d$个人，而 递推式复杂许多、需要递归调用
  • 所以具体代码实现中应该选择较大的$d$值，如5

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16