注:本学期刘老师上课内容知识点整理。

<>贪心算法

贪心不一定正确,需要证明

<>活动安排问题

算法正确性证明:

贪心算法的基本要素:
贪心选择性质和最优子结构性质
贪心选择性质
对比: 矩阵连乘, 0-1背包 vs 分数背包,活动安排
贪心算法第一基本要素, 与DP主要区别
==自顶向下计算 ==
OSP: 最优策略的子策略也是最优 //动规, 贪心
== 正确性证明一般过程: ==
贪心选择+OSP+数学归纳法
条件: 子问题与原问题类似, 相对独立 //不类似? 则需要另外方法
子问题的最优解和贪心选择联合得整体最优解

一般设计过程:

* 将问题描述为贪心选择和一个待解决子问题的形式
* 贪心选择性质: 证明贪心选择是正确的
* 最优子结构性质:
确保若将子问题的最优解和贪心选择结合, 则能得到原问题的最优解.
活动安排问题
贪心选择: 最早结束的活动
子问题: T1 = { 开始时间晚于f1的活动 }
<>最优编码问题(Huffman编码)

确定解的结构: 二叉树

好的编码:
大频率编码短
小频率编码长
正则二叉树
相对平衡

贪心选择性质:
 存在最优解其频率最小两叶节点深度最大
 存在最优解其频率最小两叶节点是兄弟

最优编码问题
贪心选择: 频率最小的两个字母是兄弟. 子问题?
原问题: 6个符号待编码
子问题: 5个符号待编码

输入C[1:n], f[1:n] //字母集C和频率f 1. Q=C //建优先队列Q, O(n) 2. 对 i = 1:n-1 //循环n-1次 3.
分配新节点z4. 取Q中f最小x作为z的左孩子//O(log n) 5. 取Q中f最小y作为z的右孩子//O(log n) 6. f[z] = f[x] + f
[y] 7. 将z插入Q中 //O(log n) 8. 取出Q中节点作为树根 //?
<>最短路问题

* 全点对最短路(APSP)
DP:

1. D[i,j][0] = w[i,j], 不存在的边值取无穷大 2. 对k=1:n 3. 对i=1:n, 对j=1:n 4. 若D[i,k][k-1]+D
[k,j][k-1] < D[i,j][k-1] 5. 则 D[i,j][k] =D[i,k][k-1]+D[k,j][k-1]; 6. 否则 D[i,j][k
] = D[i,j][k-1]
Floyd-Warshall算法

减少存储? D[i,k][k]=D[i,k][k-1]?
任何最短路径至多经过k一次
0. 若w[i,j]<无穷大, 则p[i,j]=i 1. D[i,j] = w[i,j] 2. 对k=1:n 3. 对i=1:n, 对j=1:n 4. 若 D
[i,k]+D[k,j] < D[i,j] 5. 则 D[i,j] = D[i,k]+D[k,j]; 6. p[i,j] = p[k,j]; //解标记
原因.== 构造解.== O(n3).
p[i,j]: 在i到j的最短路上j的前驱

* 单源最短路
函数d和松弛操作

Bellman-Ford(含负权[C])
初始d[s]=0, 其它点d[u]=INF, 1. 对i =1: |V|-1 //松弛|V|-1遍 2. 对每条边(u,v), 松弛(u,v) 3. 对每条边
(u,v), //检查负回路 4. 若d[v]>d[u]+w(u,v), 返回假 5. 返回真
时间 O(|V| |E|)
非动态规划, 非贪心
设s连通所有点
负回路: 边权和<0
正确性证明:

Dijktra(无负权)
1. 初始d[s]=0, 其它点d[u]=INF, S空, Q=V 2. 当Q非空 3. 取出Q中d[u]最小的u, 加入S 4. 对u的每个邻居v, 松弛(
u,v) 记u的邻居为N(u): vN(u)

使用累计法估计时间复杂度。
(1)
Q用一般数组存储。累计所有第5步:每条边都会松弛一次,合计O(|E|);累计所有第3步,执行一次找最小d[u]需要O(|V|)时间,共|V|次。总计O(|V|2
+ |E|)
(2)
Q用最小堆存储。累计所有第5步:每条边都会松弛一次,松弛后添加一个点到最小堆中,维护一次最小堆的时间O(log|V|),合计O(|E|log|V|);累计所有第3步,执行一次O(log|V|),共|V|次。总计O((|V|+|E|)log|V|)=O(|E|log|V|).仅当边数没有达到c|V|
2,才有必要用最小堆。

Dijkstra贪心算法正确性证明

<>最小生成树(MST)

无向连通带权图G=(V,E,w).
G的生成树是G的包含所有顶点的一颗子树
若G的生成树T在所有G的生成树中各边权总和最小,
则T称为G的最小生成树(MST, minimum spanning tree)

这里的MST性质证明不太懂(贪心选择+归纳)
昨天看不懂 今天看懂了。。。就是假设一个MST不含(u,v)但若如此它不是MST

MST算法正确性证明

Prim算法:
用一般数组
key[u]记u到U的最小距离, p[u]记u与U最小距离对应点 1. 初始p[u]=NIL, key[r]=0, 其它key[u]=INF, Q=V, U空
2. 当Q非空 3. 取出Q中u使得key[u]最小, 加入U 4. 对u的每个邻居v, 5. 若 vQ 且 w[u,v] < key[v] 6. 则 key
[v] = w[u,v], p[v] = u Q一般数组O(|V|^2+|E|) = O(|V|^2)
使用累计法估计时间复杂度。
Q用一般数组存储。累计所有第456步:每条边都会处理一次,合计O(|E|);累计所有第3步,执行一次O(|V|),共|V|次。总计O(|V|2+ |E|)
用优先队列:
key[u]记u到U的最小距离, p[u]记u与U最小距离对应点 1. 初始p[u]=NIL, key[r]=0, 其它key[u]=INF, Q={r},
U空2. 当优先队列(最小堆)Q非空 3. 删除Q堆顶元素u. 若u在U中,则continue; 否则加入U. 4. 对u的每个邻居v, 5. 若 w[u,v]
< key[v] 6. 则 将v按键值key[v]=w[u,v]插入Q, p[v] = u Q优先队列O(|E|log|V|+|E|log|E|) = O(|E
|log|V|)

Q用最小堆存储。累计所有第456步:每条边都会处理一次,处理后添加一个点到最小堆中,维护一次最小堆的时间O(log|V|),合计O(|E|log|V|);累计所有第3步,执行一次O(log|V|),共|V|次。总计O((|V|+|E|)log|V|)=O(|E|log|V|).仅当边数没有达到c|V|2,才有必要用最小堆。

Kruskal算法
1. A为空, Q=E按边权升序排列 2. 当Q非空 3. 顺序取Q中边(u,v) 4. 若u,v在A的不同连通分支(检查), 5. 则添(u,v)到A, (
且合并u,v所在连通分支) 6. 输出A 并查集算法处理连通分支, O(|E|log|E|+|E|log*|V|)
运用并查集算法(查了别人的解析才懂…)

1. A为空, Q=E按边权升序排列, x Make(x) 2. 当Q非空 3. 顺序取Q中边(u,v) 4. 若Find(u)Find(v), 则添(u
,v)到A, Union(u,v), 5. 输出A
这是一般人能看懂的???
反正我看不懂
[刘]n个节点, m次操作, O((n+m)log*n)

<>多机调度问题

最优化课上学了随机化算法解决,但不一定得到最优解。

技术
©2019-2020 Toolsou All rights reserved,
Python学习笔记(一)Linux【shell】 shell编程创建一个线程——— Javaweb (3)evo工具使用问题——Degenerate covariance rank, Umeyama alignment is not possibleVMware 16安装centos 7详细教程C语言做一个简易的登陆验证(功能)界面C语言——qsort函数Spring Boot面试必问:自动配置原理Android EditText密码显示隐藏Qt入门教程【基础控件篇】QCalendarWidget日历控件