导图社区 算法导论
算法导论、若对于某常数e>0,有f(n)=O(n^log_b(a-e)),则有T(n)=/Theta(n^log_b(a))、若f(n)=/Theta(n^log_b(a)),则有T(n)=/Theta(n^log_b(a)logn)。
编辑于2022-11-10 10:24:33时间管理-读书笔记,通过学习和应用这些方法,读者可以更加高效地利用时间,重新掌控时间和工作量,实现更高效的工作和生活。
本书是法兰教授的最新作品之一,主要阐明了设计史的来源、设计史现在的状况以及设计史的未来发展可能等三个基本问题。通过对设计史学科理论与方法的讨论,本书旨在促进读者对什么是设计史以及如何写作一部好的设计史等问题的深入认识与反思。
《计算机组成原理》涵盖了计算机系统的基本组成、数据的表示与运算、存储系统、指令系统、中央处理器(CPU)、输入输出(I/O)系统以及外部设备等关键内容。通过这门课程的学习,学生可以深入了解计算机硬件系统的各个组成部分及其相互之间的连接方式,掌握计算机的基本工作原理。
社区模板帮助中心,点此进入>>
时间管理-读书笔记,通过学习和应用这些方法,读者可以更加高效地利用时间,重新掌控时间和工作量,实现更高效的工作和生活。
本书是法兰教授的最新作品之一,主要阐明了设计史的来源、设计史现在的状况以及设计史的未来发展可能等三个基本问题。通过对设计史学科理论与方法的讨论,本书旨在促进读者对什么是设计史以及如何写作一部好的设计史等问题的深入认识与反思。
《计算机组成原理》涵盖了计算机系统的基本组成、数据的表示与运算、存储系统、指令系统、中央处理器(CPU)、输入输出(I/O)系统以及外部设备等关键内容。通过这门课程的学习,学生可以深入了解计算机硬件系统的各个组成部分及其相互之间的连接方式,掌握计算机的基本工作原理。
算法导论
最大流问题
流网络
结点表示城市
有向边表示运输路径和物流的方向
权重表示流量限制
网络约定
流量守恒
无限资源,只受路径流量限制
标准流网络
没有反向边/反平行边
只有单一的源点和汇点
非标准流网络可以转换成标准形式
具有反平行边
多个源点/汇点
相关定义
实际流量f(u,v)
容量函数c(u,v)
算法实现
Ford-Fulkerson方法
残存网络
未使用的流量标记为正向边
已使用的流量标记为反向边
在残存网络中将流量发送到反向边上等同于在原来的网络中缩减流量,这称之为抵消操作
增广路径
一条增广路径上能增加的最大流量成为该路径的残存容量
残存容量等于路径上所有边残存容量的最小值
不断在新的残存网络中寻找增广路径,增加残存容量
最大流最小切割定理
流网络的切割
切割容量c
计算:只考虑正容量
流量f
计算:正流量减去反流量
最小切割
对于流网络的任何切割,截面上的净流量就等于网络的流量
流网络G中任意流f的值不能超过G的任意切割的容量
最大流值就等于最小切割的容量
等价描述
不再有增广路径(残存网络中汇点t不可到达)
证明:反证法
算法实现
初始化:每条边的初始流量设为0(自带容量函数c)
寻找增广路径:DFS/BFS
找到增广路径后找到最小边进行操作
增加正向边
减少反向边
时间复杂度
Edmonds-Karp算法
时间复杂度
应用:最大二分匹配
匹配
最大匹配
转化为流网络
在原图的左侧加上源点,并把源点和左侧所有点相连
在原图的右侧加上汇点,并把汇点和右侧所有点相连
定义每条边上的容量为单位容量1
求解最大流问题
利用Ford-Fulkerson算法求得G' 中的最大流
流值大于0且在原图中的边将构成最大匹配,而最大匹配的边数就是最大流的流值
证明
证明原图和转化后的流网络中匹配和流一一对应,并且匹配的边数对应于流值(|f|=|M|)
二分图是一个二分切割,M中的边恰好是横跨该切割的边,其上是一个单位的流量。所以该切割的净流值就是f的流值,而切割的净流值等于匹配的边数
证明在容量是整数前提限制下,Ford-Fulkerson方法产生的流是整值流,从而保证算法计算的流可以还原到原图的匹配
证明最大流的流值等于最大匹配的基数
Johnson 算法
总结:不同最短路径算法
Floyd-Warshall 算法:n^3
执行|V|次单源最短路径算法
Dijkstra算法
Bellman-Ford算法
Johnson算法
工作原理
Johnson算法使用Dijkstra算法和Bellman-Ford算法作为自己的子程序,可以处理带有负权重的图
如果没有负边,则对每个结点运行一次Dijkstra算法
如果有负边但没有负环,则通过重赋权重构造出一组新的非负权重值后用Dijkstra算法
新赋的权重必须满足以下两个性质
路径等价性
非负性
赋值方法
新建一个结点s,其到其他顶点的权值均为0(均为出度,没有入度)
定义新权重(u,v)=(u,v)+h(u)-h(v)
Floyd-Warshall算法
操作步骤
最优子结构性
若添加后不发生改变(k不属于最短路径),则原路径不变
若添加后发生改变,最短路径变成了i->k->j,其中i->k和k->j都是中间节点取自1...k-1的最短路径
构造递归式
计算递归式
实际操作
1. 先关注权值矩阵D,只看添加节点的入度相连节点(序号为i)到出度相连节点(序号为j)
2. 若有必要则更新权值和前驱节点(注意前驱节点为上一个前驱矩阵第k行第j列元素)
3. 重复上述步骤直至得到包括所有节点
时间复杂度:n^3
计算矩阵传递闭包
1
2
所有结点对的最短路径
基础设定
成本邻接矩阵
最短路径矩阵
前驱结点矩阵
在i=j或不存在路径时为NIL
矩阵乘法算法
最优子结构性
构造递归式
当i=j时,则路径不包含任何边,权重为0
当i!=j时,则把路径分为起点到终点前驱(路径为p`,至多包含m-1条边,一定是最短路径)+终点前驱到终点两部分
以两点之间路径包含的最多边数作为遍历条件(加一条边就加一个中间点,类似于松弛操作)
计算递归
自顶向下(递归)
自底向上(迭代)
与矩阵乘法的关系
改进:重复平方技术(每次都平方)
单源最短路径
前置知识
最优子结构性
负权值的边
最短路径应该是简单路径(不包含环路)
最短路径的表示:记录前驱
前驱子图
解决步骤
初始化
对于每个顶点v有
d=该点v到源点s的最短距离
pi=该点的前驱(用于恢复最短路径)
初始化后每个顶点的初始值为
d=∞
pi=null
松弛(Relax u,v,w)操作
输入被操作结点v和一个中间结点u,若s->u->v比s->v的权值短,则更新v的权值为新路径和前驱为u
性质
三角不等式性质
上界性质
非路径性质
收敛性质
路径松弛性质
没有负环的情况下,进行N次松弛后必定收敛
松弛性质的成立与松弛操作顺序无关
算法实现
Bellman-ford算法
理论操作
执行N-1次大循环,每个大循环内对图中每条边都进行松弛操作,直接对象是图中的每一条有向边(u->v)
进行N-1次松大循环后,若没有负环,根据收敛性质,d表应该已经稳定;因此若再进行一次循环后d表不变则说明没有负环,返回True
实际图中操作(参考Dijkstra思想)
松弛顺序不重要
盯着上次操作中结点值改变(包括初始化的∞->0)的点,看他出度相连的结点权值是否发生改变
(结点数为N)发生N-1次RELAX操作后D表应该稳定,最后一次用于检测
Dijkstra算法
实际&理论操作
数据设置
初始化
迭代
理论证明
利用循环不变式来证明
时间复杂度分析
差分约束系统
性质
向量x是某差分约束系统的一个解,则加上一个常数d后仍是该系统的解
若约束图不包括权值为负的回路,则对应结点权值就是该系统的一个可行解;若包含权值为负的回路,则该系统没有可行解
约束图
获得方式
将mxn的矩阵A看成n个结点和m条边的邻接矩阵的转制
目的是让自变量对应结点,限制条件对应边
每条有向边对应一个不等式
新增一个结点v0,其与所有结点相连,且距离为0
处理方式:Bellman-Ford算法
最小生成树
生成方法
MST(Minimum-Span-Tree)性质(贪心算法)
每一步都加入一条安全边(加入后不改变循环不变式)
切割的定义
横跨切割:对某一条边而言
尊重
轻量级边
轻量级边可能不是唯一的
扩大化定义:满足某一性质的权重最小的边都是该性质的轻量级边
选择安全边的原则
划定一个边集A包含于全集E,且已知A包含于某棵最小生成树中
任意给出一尊重A的切割,找出E中横跨该切割的一条轻量级边,该边一定是安全的
Kruskal算法
执行步骤
1. 初始化时,集合A是一个森林,就是G的结点集
2. 将连接A的两个不同分量/结点的权重最小的边作为安全边合并两个分量/结点
3. 直到A中包含了n-1条边为止
时间复杂度:O(ElgE)
Prim算法
执行步骤
1. 初始化时,集合A只包含一个指定的根结点
2. 每次将集合A外中结点和集合A内结点相连的权值最小的边作为安全边添加进来
3. 直到A中包含了n-1条边为止
时间复杂度:O(ElgV)
算法基础知识
算法的五个重要特性
确定性
能行性
输入
输出
有穷性
满足确定性、能行性、输入和输出的一组规则称为计算过程,如操作系统就是典型的计算过程
算法是“可以终止的计算过程”
限界函数
上界函数
下界函数
渐进紧确界函数
时间复杂度计算
算法时间复杂度分类
多项式时间算法:O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)
指数时间算法:O(2^n)<O(n!)<O(n^n)
循环不变式
初始化
保持
终止
分治算法
求解递归式(分治算法)
预处理
运行时间函数T(n)假设n为正整数
忽略递归式的边界条件(n较小时的情况)
忽略上下取证函数
代换技巧
去掉低阶项
变量代换:设为指数与对数形式或者互换
求解方法
代换法
常用公式
T(n)=2T(n/2) => T(n)=O(nlogn)
解题步骤
猜测解形式,然后设常数得到初始不等式形式
假设第n-1个递推式成立并得到对应不等式
将第n-1个不等式代入化简后的原式,得到目标式
将目标式化为初始不等式的形式+额外项的形式,处理额外项即可得到成立条件
分析边界条件,如果不成立则独立出来设置新的边界条件
递归树法
每个结点表示一个单一子问题的代价,子问题对应某次递归调用
根结点表示顶层调用的代价,子结点分别表示各层递归调用的代价
所有结点的代价之和就是总代价(一般化为等比数列求和问题)
取上界函数后用代换法证明
主方法
若对于某常数e>0,有f(n)=O(n^log_b(a-e)),则有T(n)=/Theta(n^log_b(a))
若f(n)=/Theta(n^log_b(a)),则有T(n)=/Theta(n^log_b(a)logn)
若对于某常数e>0,有f(n)=/Omega(n^log_b(a+e)),且对所有足够大的n都有af(n/b)<=cf(n),则有T(n)=/Theta(f(n))
最大子数组问题
解决步骤
1. 将A[low…high]尽量分成两个规模相等的子数组
2. 分别递归地求解两个子数组
最大子数组在左侧
最大子数组在右侧
最大子数组横跨两侧
动态规划
背景知识
最优化问题
分类
线性规划
非线性规划
整数规划
动态规划
子问题图
特点
有向图,箭头表示依赖关系,箭头指向被依赖项
每个顶点与子问题一一对应
递归树中相同子问题的节点在子问题图中收缩为一个顶点
自底向下处理顺序:在其依赖的所有子问题都求解后才会求解该子问题
估算时间复杂度
子问题的数目等于顶点数
将该部分解从原问题解中去掉,换成更优解
子问题的求解时间与对应顶点的出度成正比
通用步骤
1. 刻画一个最优解的结构特征
最优子结构性
证明:反证法(剪切-粘贴法)
假设某个部分解不是最优解,存在更优解
得到的新解比原“最优解”更优,矛盾
子问题无关性
如:最长简单路径子问题相关,不能用DP;但最短路径子问题不相关,可以用DP
2. 递归地定义最优解的值
3. 计算最优解的值
通常采用自底向上方法求最优解
4. 利用计算出的信息,构造一个最优解
如果只需要求值可忽略第四步
在计算过程中存储步骤
例题
钢条切割问题
思维过程
1. 决定最优解结构
2. 转化为递归形式
3. 求解,得到最优数
4. 重构解(得到获取最优解的方案/过程)
利用动态规划优化递归过程
问题:递归树中出现了大量重复子问题的计算
动态规划方法将仔细安排求解顺序,对每个子问题只求解一次,并将结果保存下来
动态规划保存子问题的解需要额外的空间成本,是一种典型的时空权衡
求解方法
带备忘的自顶向下法
自底向上法
先将子问题按规模从小到大排序
按照顺序依次求解子问题,每次都直接调用已经解决的子问题
最后的结果是所有子问题(包括原问题)的最优解
对比
通常情况下,自顶向下和自底向上具有相同的渐进运行时间
矩阵链乘法
背景知识
矩阵乘法满足结合律,不满足交换律
不同运算顺序(加括号方式)带来显著的运算次数差异
求最优的加括号方式是一种最优解问题
定义
最小运算次数m[i,j]
记录分界点s[i,j]
解决步骤
1. 构建最优解
p是n哥矩阵的维数表示
2. 递归求解
画图分析
最长公共子序列(LCS)
解决步骤
1. 构造最优解
2. 构造递归
3. 求解递归
实际操作(画图分析)
对于长为m的序列X和长为n的序列Y,构造一个mxn的二维表格
在最上方和最左方生成一个0序列,在其后再表示串
表格第i行第j列的意思就是截止目前Xi和Yj的最大公共子序列
通过比较新元素是否相等决定继承方式
如果新加入的元素不等,就继承上边或者右边最大的那个
如果新加入的元素相等,就赋值为左上角值➕1
图案表示(用于记录每一步的操作,还原LCS)
⬆️/⬅️:表示继承最大值
↖️:表示最大公共子序列增加的地方(用于还原)
最优二叉搜索树
背景知识
伪关键字di
概率qi
期望搜索代价
一次搜索的代价等于结点的深度(根节点深度为0)+1
总代价就是所有关键字和伪关键字的代价之和
递归公式
构造
定义
代价数组e[1..n+1,0..n]
根节点记录数组root[1...n]
结点概率和w[1..n+1,0..n]
贪心算法
一般步骤
1. 确定问题的最优子结构
2. 优化最优子结构
3. 证明贪心选择的正确性
证明做出贪心选择后,原问题总是存在最优解(贪心选择是安全的)
证明满足贪心选择性质(可以通过局部最优的贪心选择来构造最优解)
证明方法:剪切-粘贴法
理论基础
贪心选择性质
贪心算法不像动态规划需要先求解子问题(自底向上)才能进行第一次选择,贪心算法不需要解决任何子问题,通常直接自顶向下进行计算,一步步减小问题规模
最优子结构性
例题
活动选择问题
可以使用动态规划求解,但贪心算法可以转化成更简单的迭代问题
解决步骤
最优子结构和递归式
将子集简化为填入一个活动
利用动态规划方法应该遍历所有活动后建立备忘,并选择最优的填入
贪心算法优化动态规划的方法是将两个子问题的一个转为空问题
证明正确性
假设现有一个最大兼容子集
因为子集中最早的活动aj结束时间fj一定大于等于全集中最早活动am的结束时间fm,且子集中的活动一定不相交
因此将子集中的最早活动替换为全集中的最早活动后子集规模不变
因此全集中最早活动一定在最大兼容活动子集中
Huffman 编码
离散数学中有详细介绍
解决方法
1. 最开始所有单词是独立的叶子结点
2. 选出词频最小的两个结点成树,根结点为词频之和(词频较大的为右孩子)
3. 重复上述步骤直到成树
时间复杂度:nlgn
图算法
基础知识
一个图通常用G=(V,E)表示
V:G中结点的集合,|V|表示结点数
E:G中边的集合,|E|表示边数
通常用|V|和|E|两个参数表示算法输入的规模
图的表示
邻接表:表示边的链表
邻接矩阵:表示顶点之间相邻关系的01矩阵
无向图邻接矩阵是对称的,因此可以用上/下三角矩阵表示
图的遍历
BFS(Broad-First-Search)广度优先检索
生成树
BFT(Broad-First-Traverse)广度优先遍历
若BFS调用次数多于1,则G不是连通图
每次BFS都会生成一个连通子图
改进:深度检索
DFS(Depth-First-Search)
直接搞递归
规划算法
常用思路
分治思想
动态规划
贪心算法
回溯
分支-限界
相关概念
用于求解问题的一组特定性质的解或满足某些约束条件的最优解
对问题的要求
解可以用一个n元组向量表示,且维度量取自某个有穷集
问题的求解目标是求一个使某个规范函数取极值或其他条件的向量(或一组向量)
约束条件
显式约束条件
隐式约束条件
解空间
解空间的组织
状态空间树
相关概念
问题状态
状态空间
解状态
答案状态
同一个问题可能有不同形式的状态空间树
每一层的边代表一组Xi的取值
构造
以问题的初始状态作为根结点,然后系统地生成其他问题状态的结点
结点类型
活结点
E-结点
死结点
构造策略
DFS策略
BFS策略
优化策略
限界函数
回溯法(backtracking)
分支限界法(branch-and-bound)
回溯法
基础概念
什么是回溯
例题
八皇后问题
用[x1,…, x8]的8元组表示解,其中i表示行号,xi表示列号
显式条件
隐式条件
任意两个xi不能相同
两个皇后不能在同一对角线上
解空间组织
限界函数
在原DFS树的基础上剪枝,不改变结点编号
子集和数问题
表示方法
直接用元素表示
k元组(用元素下标表示)
显式条件
隐式条件
没有两个xj是相同的
和必须为M
满足单调递增(避免重复迭代)
n元组(用01向量表示)
显式条件
元祖具有固定大小
取值只能是0或1
隐式条件:和为M
解空间:2^n
分支-限界法
活结点表
数据结构
队列(FIFO,用于BFS)
栈(LIFO,用于D-Search)
例题
n-皇后问题
FIFO/BFS
LC(Least Cost)检索(A*算法)
LIFO/FIFO剪枝存在的问题
解决方案
结点成本函数
标准成本函数C(X)
若X是答案结点,则取根结点到X的层数
若X不是但其子树包含答案结点,则取子树中具有最小成本的答案结点的成本
若X不包含任何答案结点,则为∞
问题:计算成本的复杂度和解问题相同
成本估计函数:估计成本+已发生成本
估计函数g(x)
问题:会导致E结点的选择偏向DFS
已发生成本函数h(x)
效果:使算法优先检索更靠近答案结点又离根较近的结点
实例
特例(用LC检索描述其他检索)
BFS
估计函数=0
成本函数=级数
效果:优先检索同层
D-Search
成本函数=0
15-谜问题
LC分支-限界检索
状态空间树的构造
剪枝策略
成本估计函数
估计函数应表示从X到答案状态的最短路径的估计值
成本估计函数是最小成本的下界,作为启发性函数减少E-结点选取的盲目性
具体表示
已发生成本
最小成本的上界(限界函数)
法1:初始值
法2:得到新答案后更新该答案为上界