算法分析与设计课件

问题求解的方法
硬性处理法
– 列出所有候选解，逐个检查是否为所需要的解 – 理论上，候选解数量有限，并且通过检查所有或部分
候选解能够得到所需解时，上述方法可行
– 实际中则很少使用，因为候选解的数量通常都非常大 （比如指数级，甚至是大数阶乘），即便采用最快的 计算机也只能解决规模较小的问题。
回溯或分枝限界法
这种以深度优先方式搜索问题的解的方法称为 回溯法
回溯法思想
第一步：为问题定义一个状态空间(state space)。这 个空间必须至少包含问题的一个解
第二步：组织状态空间以便它能被容易地搜索。典型 的组织方法是图或树
第三步：按深度优先的方法从开始结点进行搜索
– 开始结点是一个活结点（也是 E-结点：expansion node） – 如果能从当前的E-结点移动到一个新结点，那么这个新结点将
权衡：限界函数生成结点数和限界函数 本身所需的计算时间
效率分析
效率分析中应考虑的因素
– （1）—（3）与实例无关 – （4）与实例相关
有可能只生成O(n)个结点，有可能生成 几乎全部结点
最坏情况时间
– O(p(n)2n)，p(n)为n的多项式 – O(q(n)n!)，q(n)为n的多项式
Monte Carlo效率估计（1）
解空间
隐式约束描述了xi必须彼此相关的情况， 如0/1背包问题中的背包重量M
回溯法求解的经典问题（1） 8-皇后问题
在一个8*8棋盘上放置8个皇后，且使得每两个 之间都不能互相“攻击”，也就是使得每两个 都不能在同一行、同一列及同一条斜角线上。
8皇后问题的解可以表示为8-元组(x1,…,x8) ， 其中其中xi是第i行皇后所在的列号。
回溯法求解的经典问题（2） 子集和数问题

7
如何描述算法
通常，描述算法用类Pascal的结构化编程语言。
8
算法的证明技巧
反证法(proof by contradication)/间接证明(indirect proof)： 为了证明命题的正确性，转而证明该命题的反 命题能导致矛盾。
例子： [欧几里德] 定理：存在无穷多个素数。
证明：假设P为有限素数集，那么显然 P 。 P 且有限， 将P中所有元素相乘，X表示积
王晓东. 算法设计与分析.（电子工业出版社） Sara Baase等. 计算机算法：设计与分析导论
（第3版），高教出版社影印本。
3
第一章 预备知识
学习要点:
理解算法的概念。 理解什么是程序，程序与算法的区别和内在联
系。 掌握算法的计算复杂性概念。 掌握算法渐近复杂性的数学表述。 掌握用C++语言描述算法的方法。
序列给出：递归形式 f0 0; f1 1
f
n
fn1
fn2,
n2
序列以0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …
Fibonacci序列的算法：
Function Fibonacci(n)
if n<2 then return n;
else return Fibonacci(n-1)+Fibonacci(n-2);
对于 d 0 ，可以同时整除连续整数是不可能。
否则 Y modd 1
10
[欧几里德]证明
矛盾
因此，P为无限集合。 [证毕] 下面衍生出找素数的一个算法：
11
派生出算法
function Newprime(P:整数集)
{变量P为一非空有限的素数集} XP中所有元素的乘积; YX+1;

常见的贪心算法包括最小生成树算法 、Prim算法、Dijkstra算法和拓扑排 序等。
贪心算法的时间复杂度和空间复杂度 通常都比较优秀，但在某些情况下可 能需要额外的空间来保存状态。
动态规划
常见的动态规划算法包括斐波那契数列、背包 问题、最长公共子序列和矩阵链乘法等。
动态规划的时间复杂度和空间复杂度通常较高，但通 过优化状态转移方程和状态空间可以显著提高效率。
动态规划算法的时间和空间复杂度分析
动态规划算法的时间复杂度通常为O(n^2)，空间复杂度为O(n)。
04 经典问题与算法实现
排序问题
冒泡排序
通过重复地遍历待排序序列，比较相邻元素的大小，交换 位置，使得较大的元素逐渐往后移动，最终达到排序的目 的。
快速排序
采用分治策略，选取一个基准元素，将比基准元素小的元 素移到其左边，比基准元素大的元素移到其右边，然后对 左右两边的子序列递归进行此操作。
动态规划是一种通过将原问题分解为若干个子 问题，并从子问题的最优解推导出原问题的最 优解的算法设计方法。
动态规划的关键在于状态转移方程的建立和状态 空间的优化，以减少不必要的重复计算。
回溯算法
01
回溯算法是一种通过穷举所有可能情况来求解问题的算法设计方法。
02
常见的回溯算法包括排列组合、八皇后问题和图的着色问题等。
空间换时间 分治策略 贪心算法 动态规划
通过增加存储空间来减少计算时间，例如使用哈希表解决查找 问题。
将问题分解为若干个子问题，递归地解决子问题，最终合并子 问题的解以得到原问题的解。
在每一步选择中都采取当前状态下最好或最优（即最有利）的 选择，从而希望导致结果是最好或最优的。
通过将问题分解为相互重叠的子问题，并保存子问题的解，避 免重复计算，提高算法效率。

4
5
C
C
n=5, m=3的GCP： 解形式(x1,x2, x3, x4, x5) xi =1(红色), 2(绿色), 3(蓝色)
X3=3
D
9
5.6 图的m着色问题
GCP示例
1
A
AA
A
A X1=1
2
3
X1=1
X1=1 X1=1
B
B
B
B X2=2
4
5
X2=2
C
X2=2
C
C X3=3
n=5, m=3的GCP： 解形式(x1,x2, x3, x4, x5) xi =1(红色), 2(绿色), 3(蓝色)
7
5.6 图的m着色问题
GCP示例
1
AA
A
2
3
X1=1
X1=1
B
B
X2=2
4
5
C
n=5, m=3的GCP： 解形式(x1,x2, x3, x4, x5) xi =1(红色), 2(绿色), 3(蓝色)
8
5.6 图的m着色问题
GCP示例
1
AA
A
A
2
3
X1=1
X1=1 X1=1
B
B
B
X2=2 X2=2
A
X1=1
2
3
B
X2=2 X2=3
4
5
C
X3=3
G
X3=2
n=5, m=3的GCP： 解形式(x1,x2, x3, x4, x5) xi =1(红色), 2(绿色), 3(蓝色)
D
X4=1
E
X5=3
F
H
X4=1

边界条件
1
n0
F
(n)
1
n 1
F (n 1) F (n 2) n 1
递归方程
第n个Fibonacci数可递归地计算如下： int fibonacci(int n)
{ if (n <= 1) return 1; return fibonacci(n-1)+fibonacci(n-2);
}
分治算法总体思想
环被执行了O(logn) 次。
if (x < a[m]) r = m-1;
循环体内运算需要O(1)
else l = m+1; } return -1; }
时间，所以整个算法在最 坏情况下旳计算时间复杂 性为O(logn) 。
合并排序
基本思想：将待排序元素提成大小大致相同旳2个子集合，分 别对2个子集合进行排序，最终将排好序旳子集合合并成为所 要p求{ub旳lic排s复t好a杂t序ic度旳vo分集id析合Tm(。en)rgeS2Tor(nt(/CO2o()1m) Opa(nra) bnnlea11[], int left, int right)
多项式时间算法：可用多项式（函数）对其计 算时间限界旳算法。
常见旳多项式限界函数有：
Ο(1) < Ο(logn) < Ο(n) < Ο(nlogn) < Ο(n2) < Ο(n3)
指数时间算法：计算时间用指数函数限界旳算 法。
常见旳指数时间限界函数：
Ο(2n) < Ο(n！) < Ο(nn)
阐明：当n取值较大时，指数时间算法和多项式
线性时间选择问题
问题描述：给定线性集中n个元素和一种整数
k,要求找出这n个元素中第k小旳元素，即假如 将这n个元素依其线性序排列时，排在第k个位 置旳元素即为我们要找旳元素。 当k=1时，即找最小元素；当k=n时，即找最大 元素；当k=(n+1)/2时，称为找中位数。

算法设计与分析
1
第八章 NP完全性理论
目录
8.1 异解问题和难解问题
8.2 P类问题和NP类问题
8.3
NP完全问题
8.4 NP完全问题的近似算法
2
8.3 NP完全问题
问题变换：
➢ NP类问题在最坏情况下的时间复杂性一般都是快速增长的指数函 数。希望能够在NP类问题内部找到一种方法，比较两个问题的计 算复杂性。
❖该近似算法的相对误差定义为=
cc* c*
。若对问题的输
入规模n，有一函数ε(n)使得 c c* ≤ε(n)，则称ε(n)
c*
为该近似算法的相对误差界。
13
8.4 NP完全问题的近似算法
NPC问题的近似算法示例 - TSP：
➢ 给定一个完全无向图G=(V,E)，其每一条边(u,v)∈E有一非 负整数费用c(u,v)。要找出G的最小费用哈密顿回路。如果 TSP满足三角不等式性质，即对于任意3个顶点u,v,w∈V有 ：c(u,w)≤c(u,v)+c(v,w)，则称该TSP为欧几里得TSP，否 则称为一般TSP。
12
8.4 NP完全问题的近似算法
NPC问题的近似算法的性能：
❖若一个最优化问题的最优值为c*，求解该问题的一个近 似算法求得近似最优解相应的目标函数值为c，则将该近 似近≤似算ρ比法(是n的)问。近题ρ似输(比n入)定为规义1模时为n，的求=一m得a个x的c函c*近, c数c*似 ρ。解(在为n)通最，常优即情解m况a。x 下cc* ,，cc*该
➢ 传递性：设P1、P2和P3是3个判定问题。若P1∝τ(n)P2，且P2∝τ(n)P3 ，则P1∝τ(n)P3。
4
8.3 NP完全问题
多项式时间变换示例：

6
4.5 最小生成树问题
◼ Prim算法思想：
❖Prim算法利用了最小生成树的上述性质。 ❖ 算法的关键是如何找出连接U和V-U所有边中的权值 最小的边(u, v)，并将v加入到U中。循环执行上述操作， 直至U=V为止。
7
4.5 最小生成树问题
◼ Prim算法设计：
❖ 设G=(V，E)是具有n个结点的无向连通带权图；设最 小生成树T=(U，TE)，算法结束时U=V，TE包含于E
点的无向连通带权图，U是
V的一个非空子集。最小生
成树的一个很重要的性质：
✓ (u, v)是一条具有最小权 值 的 边 ， 其 中 u∈U ， v∈V-U，则必存在一棵包
假设最小生成树T不包括(u,v)。 将(u,v)添加到T上产生回路， 将回路中另外一条边(u’,v’)去 掉得到另外一个树T’
含 边 (u ， v) 的 最 小 生 成 树 。
◼ Prim算法的求解示例：
18
4.5 最小生成树问题
◼ Prim算法的求解示例：
19
4.5 最小生成树问题
◼ Prim算法的求解示例：
20
4.5 最小生成树问题
◼ Prim算法的求解示例：
21
4.5 最小生成树问题
◼ Prim算法的求解示例：
22
4.5 最小生成树问题
◼ Prim算法的求解示例：
◼ Prim算法空间复杂性：
❖定义了辅助变量Q，其占用空间为|V|，从而空间复 杂度为O(|V|)。
27
4.5 最小生成树问题
◼ Prim算法的正确性证明：
❖最优子结构性质：假设最小生成树为T，从V-U集合中 添加到集合U中的结点顺序为< u0, …, ui, …, un-1, un>， 需要证明： 顺序< u0, …, ui, …, un-1>亦为图G’=(V\{un}， E\{e})最小生成树T’ ，其中e={原图G中与结点un相连 的边}。

❖ 计算任务由计算机的中央处理器完成，打印输出任务 由打印机完成。
❖ 计算机处理器是机器1，打印机是机器2。
5
5.4 作业调度问题
tmi 作业J1 作业J2 作业J3
机器m1 2 3 2
机器m2 1 1 3
调度一：1, 2, 3
F11=2 F21=3 F12=5 F22=5+1=6 F13=7 F23=7+3=10 f = F21+F22+F23 = 19
cf<bestf，限界条件满 K L
足，扩展生成的结点
J成为活结点。
24
5.4 作业调度问题
tmi 机器m1 机器m2
作业J1
2
1
作业J2
3
作业J3
2
1
A
3
x1=1 x1=2
B
C
x1=3 D
◼ 沿着结点 J 的x3=1 x2=2 x2=3 x2=1 x2=3 x2=1 x2=2
的分支扩展：
E
FG
H
//更新完成时间之和
if (f < bestf)
//判断与当前最优解之间的关系
Swap(x[i], x[j]);
//将j位置上的任务序号与i位置上的互换
backtrack(i+1);
//递归进行下一层的调度
Swap(x[i], x[j]);
//回溯，还原，执行第i层的下一个任务
f1 f1 - M[x[j]][1]; //出栈要回溯到父亲节点，先恢复数据；
K
L
❖此 时 ， 找 到 比 先 前 更 优 的 一 种 调 度 方 案 (1,3,2) ， 修 改 bestf=18 。
14

17
近似算法的性能
若一个最优化问题的最优值为c*，求解该问题的一个 近似算法求得的近似最优解相应的目标函数值为c，则将 c * c max , 该近似算法的性能比定义为= c 。在通常情况 c* 下，该性能比是问题输入规模n的一个函数ρ(n)，即 c * c max , ≤ρ(n)。 c c* 该近似算法的相对误差定义为= c * 。若对问题 cc* 的输入规模n，有一函数ε(n)使得 c * ≤ε(n)，则称 ε(n)为该近似算法的相对误差界。近似算法的性能比 ρ(n)与相对误差界ε(n)之间显然有如下关系： ε(n)≤ρ(n)-1。
4
这种问题的答案，是无法直接计算得到的，只能通过间 接的“猜算”来得到结果。这也就是非确定性问题。而这些 问题的通常有个算法，它不能直接告诉你答案是什么，但可 以告诉你，某个可能的结果是正确的答案还是错误的。这个 可以告诉你“猜算”的答案正确与否的算法，假如可以在多 项式时间内算出来，就叫做多项式非确定性问题。而如果这 个问题的所有可能答案，都是可以在多项式时间内进行正确 与否的验算的话，就叫完全多项式非确定问题。
2
10
接受该语言CLIQUE的非确定性算法：用非确定性选择指令选 出包含k个顶点的候选顶点子集V，然后确定性地检查该子集是否 是团问题的一个解。算法分为3个阶段： 算法的第一阶段将输入串w#v分解，并计算出n= | w | ，以及 用v表示的整数k。若输入不具有形式w#v或|w|不是一个平方数就 2 拒绝该输入。显而易见，第一阶段可 O ( n ) 在时间内完成。 算法的第三阶段是确定性地检查V’的团性质。若V’是一个团 则接受输入，否则拒绝输入。这显然可以在 O ( n 4 ) 时间内完成。 4 因此，整个算法的时间复杂性为O ( n ) 。

2.3 分治策略
n设计思想
• 将原问题划分成若干个相同的子问题分而治之，若子问题仍然
较大，则可以反复递归应用分治策略处理这些子问题，直至子 问题易求解。
n求解步骤
• 将输入划分成若干个规模相等的子问题； • 同时(并行地)递归求解这些子问题； • 并行地归并子问题的解成为原问题的解。
n示例
• SIMD-SM模型上的FFT递归算法
Parallel Algorithms 3 / Ch2
2.1 平衡树方法
n算法2.1 SIMD-SM上求最大值算法
Begin for k=m-1 to 0 do for j=2k to 2k+1-1 par-do A[j]=max{A[2j], A[2j+1]} end for end for
end
时间分析 t(n)=m×O(1)=O(logn) p(n)=n/2 c(n)=O(nlogn) 非成本最优
2023/10/19
Y.Xu Copyright
USTC
Parallel Algorithms 4 / Ch2
2.1 平衡树方法
前缀和
n 问题定义
n个元素{x1,x2,…,xn}，前缀和是n个部分和： Si=x1*x2*…*xi, 1≤i≤n 这里*可以是＋或×
for j=1 to n/2h par-do B[h,j]=B[h-1,2j-1]*B[h-1,2j]
end for end for
时间分析:
(3)for h=logn to 0 do //反向遍历
for j=1 to n/2h par-do (i) if j=even then //该结点为其父结点的右儿子 C[h,j]=C[h+1,j/2]